Archive for June, 2008

Uncategorized

Convert a String to a Signed Integer

There are of course numerous functions to do this but without resorting to those here's how this can be done in C++. Note that we are assuming the input is well formatted and includes no commas or spaces. If that's not the case, it's trivial to amend this function to cater for those variations. The only real "cleverness" in this puzzle is line 14 where we subtract two characters to get an integral value of the digit.

   1:  #include <iostream>
   2:  #include <string>
   3:   
   4:  using namespace std;
   5:   
   6:  int toInt(string s)
   7:  {
   8:      int ans = 0, exp = 1;
   9:      for(int pos=s.length()-1; pos >= 0; --pos){
  10:          if (s[pos] == '-'){
  11:              ans = ans * -1;
  12:              break;
  13:          }
  14:          ans = ans + (s[pos] - '0')*exp;
  15:          exp = exp * 10;
  16:      }
  17:      return ans;
  18:  }
  19:   
  20:  int main(int argc, char* argv[])
  21:  {
  22:      cout << toInt("-678") << endl;
  23:      cout << toInt("21140") << endl;
  24:      cout << (toInt("21140") + toInt("-678")) << endl;
  25:      cout << toInt("0") << endl;
  26:      cout << toInt("") << endl;
  27:   
  28:      return 0;
  29:  }

Uncategorized

Shift it Baby

C# provides the bitwise shift operators << and >>. These are extremely useful operators to do fast, parallel operations on bit maps and flag enumerations. But there are several subtleties that you should be aware of:

  • This operator is defined for int/uint/long/ulong data types, however because of numeric promotion it can also be used on short/ushort/byte/sbyte. The 2 operands are in fact promoted separately and the result type is the promotion type of the first operand. The following code snippet demonstrates a common issues that leaves developers scratching their head. The cause is implicit number promotion from byte to int and a type mismatch on the assignment operation after shifting.  

                byte b = 3;
                byte c = b << 2; // this produces a "Cannot convert int to byte" compiler error 
                byte d = (byte)(b << 2);    // this is OK 
  • The operator uses infix notation where the left hand operand is the number being shifted, and the right hand operand is the number of bits to shift. Be aware that the right hand side operand is masked so only the rightmost 5 bits are used for int/uint LHS values, and the rightmost 6 bits are used for longs/ulongs. This effectively means that the RHS operand is evaluated modulo 32 or 64 dependent on the type of the RHS. In the example below all RHS operands are treated as zero!
      

                Console.WriteLine(UInt32.MaxValue << 32);       // gives UInt32.MaxValue
                Console.WriteLine(UInt32.MaxValue << 64);       // gives UInt32.MaxValue
                Console.WriteLine(UInt32.MaxValue << 128);      // gives UInt32.MaxValue
                Console.WriteLine(UInt32.MaxValue << 0);        // gives UInt32.MaxValue
  • Curiously, the RHS operand must be an int. It cannot be a uint/long/ulong despite the fact that the above mentioned 5/6 bit masking would make this trivial to implement.
  • There is no circular shift operator (sometimes called bitwise rotation) in C#. You have to write it yourself. Here's what it would look like:
      

            public static uint CircularShiftLeft(uint value, int shiftCount)
            {
                shiftCount &= 31;
                return ( (value << shiftCount) | (value >> (32-shiftCount)));
            }
    
            public static uint CircularShiftRight(uint value, int shiftCount)
            {
                shiftCount &= 31;
                return ((value >> shiftCount) | (value << (32 - shiftCount)));
            }
  • C# does not use a different operator to differentiate between logical shifting and arithmetic shifting for right shifts. Java and JavaScript use ">>" for arithmetic right shift and ">>>" for logical right shift. (No such differentiation is needed for left shifts since arithmetic left and logical left shifts produce identical results.) According to this article by Microsoft, the ">>>" operator is the only Java operator not supported by C#, because - according to Microsoft - there is no need for such an operator in a language which supports both signed and unsigned integers, which C# does. In C and C++, the unsigned modifier can be added to a integer variable declaration. It tells the compiler to treat the value of the variable as an unsigned value in arithmetic operations. In Java, there is no "unsigned" keyword and, with the exception of char, all integer primitive data types are signed. It is because of this that theJava language needs both the ">>" and ">>>" operators, as the developer has no other way of telling the compiler that s/he wants to work with logical or arithmetic shifts.
  • Since C# doesn't use a different symbol to differentiate right shift behaviour, the internal implementation of right shifting (>>) is dependent on the data type of the LHS operand. If it is a signed number then arithmetic shifting is used. If it is unsigned then logical shifting is used. To see this, consider the following code. Since the LHS operand is a signed integer an arithmetic shift is done and therefore the sign bit is preserved and the result is a negative number. Had it been a logical shift the MSB would have been a zero which would indicate a positive number
     

                Console.WriteLine(Int32.MinValue);          // gives -2147483648
                Console.WriteLine(Int32.MinValue >> 1);     // gives -1073741824 
  • Signed numbers are represented internally using two's complement form in C# so if you use a negative number for the RHS operand, it will have the lower 5 or 6 bits masked off (depending on whether the LHS operand is a 32 or 64 bit integer) from the two's complement representation of the number which produces some rather unexpected results.
     

                Console.WriteLine(Int32.MinValue >> -1);    // gives -1
                Console.WriteLine(Int32.MaxValue << 1);     // gives -2
  • Lastly, left shift operations never cause overflows which is kinda nice!

All in all, the shift operators in C# are very useful to the resourceful programmer, and not to dissimilar to how shift operators work in other languages such as C++ and Java, but you just need to be aware of these subtleties.

References

http://msdn.microsoft.com/en-us/library/aa691377(VS.71).aspx

http://msdn.microsoft.com/en-us/library/xt18et0d.aspx

Uncategorized

Creating a String Representation of an Integer

Question: Without using any system-provided function [eg. Int32.ToString() ], write a function that takes an integer and returns a string of the value.

Answer: This is fairly trivial but a seemingly common question to throw at programmers. All you need to do is apply some modular arithmetic to iterate over each digit fetching the string value as you go. The edge cases for negative numbers and 0 still seem to catch many people out! It's trivial to extend this algorithm to bases other than 10.

Here's some code in C# to do it:

public static string ConvertInt(int i)
{
    var digits = new[] { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
    var result = "";
 
    if (i == 0) return "0";
 
    bool isNegative = (i < 0);
 
    if (isNegative)
        i = i * -1;
 
    while (i != 0)
    {
        result = digits[i % 10] + result;
        i = (i - i % 10) / 10;
    }
 
    if (isNegative)
        result = "-" + result;
 
    return result;
}