Geek Answers Handbook

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

I found some source code example where the author seems to use the bitwise & operator instead of the % operator. However, when I tried x & 4 , it did not return the same value as x % 5 .

+4
source share
2 answers

This only works for grades 2.

Generally:

 x MOD 2^n

is equivalent to:

 x AND (2^n - 1)

Note that this may only be true for x >= 0 , depending on your MOD definition 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 division by 2 ^ n, we actually simply shift the binary value to the right by n bits and discard any least significant bits that are shifted, for example. for 8 bit binary number

 abcdefgh

if we divide by 4 = 2 ^ 2, then we will shift 2 bits to the right:

 0 0 abcdef

The remainder ( gh ) was discarded as a result of integer division.

If we wanted to know the remainder, we could just extract the gh bits by applying the mask 0 0 0 0 0 0 1 1 :

  abcdefgh AND 0 0 0 0 0 0 1 1 = 0 0 0 0 0 0 gh

Note that the value has a value of 3, which is generally 2 ^ n - 1.

Try this with some real numbers. Suppose we want to calculate 42/4 and get both the quotient and the rest:

 42 = 0 0 1 0 1 0 1 0

To get the ratio, we shift 2 bits to the right:

  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.

+16
source

The answer is quite simple, try thinking in binary format.

 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

... etc.

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

+4
source

More articles:


All Articles