Possible Duplicate:
Bitwise and in place of modulus operator
Can someone explain the rationale that makes both expressions equivalents? I know it only works because 64 is a power of two, but how can I logically or mathematically go from division to bitwise and?
The operation x % 64 returns the remainder when x is divided by 64, which (assuming x>0) must be a number between 0 and 63. Let's look at this in binary:
63dec = 0011 1111b
64dec = 0100 0000b
You can see that the binary representation of any multiple of 64 must end with 6 zeroes. So the remainder when dividing any number by 64 is the original number, with all of the bits removed except for the 6 rightmost ones.
If you take the bitwise AND of a number with 63, the result is exactly those 6 bits.
Each time you do a bit-shift this is the same as dividing by two. This is because a binary representation is base 2. It is the same way that removing the 3 from 123 in base 10 gives you 12, and that is like dividing 123 by 10.
% is the mod operator, which means the remainder of a division. 64 is 2 to the sixth power, so dividing by 64 is like shifting out six bits. The remainder of the division is those six bits that you shifted out. You can find the value of the six bits by doing a bitwise-and with only the lower six bits set, which is 63.
first one gives the remainder.
second one is short-circuit ( bit wise AND).
in bit wise AND, 63(in binary is 111111) so whatever is on LHS (x) is anded, resulting in same except the MSB. Ans so is the case with % with 64( binary 100000), divides and MSB remains the same.
