Necessary and Sufficient

Question: Given an unbiased PRNG which returns values in the range 0-5, how could you use this function to produce unbiased random numbers in the range 0-7.

Answer: Most people immediately think that they could run the Rand5() twice and return the sum mod 8 however this doesn't produce unbiased results. To get unbiased results every possible result needs to have the same probability.

Consider what the numbers 0-5 look like in binary:

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
 

Notice that we have 6 values in total. This is nice and even and will help us no doubt. Now look at the least-significant bits (LSB) of these 6 values. Three have a one and three have a zero. i.e. 0s and 1s have an equal likelihood of appearing in the LSB of the returned random number.  The same cannot be said of the other 2 columns.

Now let us add 6 and 7 to our binary table:

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

This table shows the binary representation of all possible values that could be returned from the function we need to produce - Rand7(). Examining the distribution of zeros and ones in each column we can see that every column have an even distribution of 0s and 1s.  So we can produce Rand7() as follows:

        static uint Rand7()
        {
            return (uint)(((Rand5() & 1) << 2) + ((Rand5() & 1) << 1) + (Rand5() & 1));
        }

What this is doing is calling the Rand5() function 3 times, masking off the LSB which we know will be evenly distributed between 0s and 1s, and shifting them into each of the 3 bit positions, then converting the resulting binary representation to an unsigned integer. The result is an unbiased pseudo-random drawing from the range 0-7 inclusive.

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.

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

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