Why is ( x & 3 ) identical to ( x mod 4 )?

Question

I found some example source code where the author seems to use bitwise & operator instead of % operator. However when I tried x & 4 it doesn't produce the same value as x % 5.

Answer 1

This only works for powers of 2.

In general:

x MOD 2^n

is equivalent to:

x AND (2^n - 1)

Note also that this may be true only for x >= 0, depending on your definition of MOD for x < 0.

---

To understand why this works, consider what MOD really is - it's just the remainder after performing integer division. In the case of a division by 2^n, we are effectively just shifting a binary value right by n bits and discarding any low order bits that get shifted out, e.g. for an 8 bit binary number

a b c d e f g h

if we divide by 4 = 2^2 then we shift right by 2 bits:

0 0 a b c d e f

The remainder (g h) has been thrown away as a result of the integer division.

If we wanted to know the remainder then we could just extract the bits g h by applying a mask of 0 0 0 0 0 0 1 1:

    a b c d e f g h
AND 0 0 0 0 0 0 1 1
  = 0 0 0 0 0 0 g h

Note that the has has value 3, which in the general case is just 2^n - 1.

Let's try this with some real numbers. Suppose we want to calculate 42 / 4 and get both the quotient and the remainder:

42 = 0 0 1 0 1 0 1 0

To get the quotient we shift right by 2 bits:

  42 / 4 (decimal)
= 0 0 1 0 1 0 1 0 >> 2
= 0 0 0 0 1 0 1 0
= 10 (decimal)

  42 MOD 4 (decimal)
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1
= 0 0 0 0 0 0 1 0
= 2 (decimal)

So 42/4 = 10 remainder 2.

Answer 2

The answer quite simple, try to think in binary.

0000 = 0 AND 11 = 0000 = 0
0001 = 1 AND 11 = 0001 = 1
0010 = 2 AND 11 = 0010 = 2
0011 = 3 AND 11 = 0011 = 3
0100 = 4 AND 11 = 0000 = 0
0101 = 5 AND 11 = 0001 = 1
0110 = 6 AND 11 = 0010 = 2
0111 = 7 AND 11 = 0011 = 3

... and so on.

This have the same result as reminder (% is remainder, formally, not modulus). It works only with powers of 2 and only for zero and positive numbers.