4

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?

Community
  • 1
  • 1
chrisapotek
  • 6,007
  • 14
  • 51
  • 85
  • @Blender: the "possible duplicate" question asks about numbers that are _not_ powers of 2, so it's (very) slightly different. – Adam Liss Dec 09 '12 at 05:08
  • @AdamLiss: Some of the answers outline why that happens. – Blender Dec 09 '12 at 05:09
  • 1
    So they're duplicate answers, but it's not a duplicate question. :-) Perhaps better to link to one of them in your comment? – Adam Liss Dec 09 '12 at 05:11
  • The effect of `x & 63` is to keep the lowest 6 binary digits of `x` and throw the rest away. If we were working in decimal, notice how keeping the last 6 decimal digits of some number `x` would be the same as `x % 1000000`. – j_random_hacker Dec 09 '12 at 06:07

3 Answers3

10

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.

Adam Liss
  • 47,594
  • 12
  • 108
  • 150
3

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.

Vaughn Cato
  • 63,448
  • 5
  • 82
  • 132
0

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.

Anoop Vaidya
  • 46,283
  • 15
  • 111
  • 140