find if a number is divisible by 8 - using bit shifting operators

Question

I was recently asked during an interview, using just bit shift operators, write some code that would tell you if a number is divisible by 8, apparently the code is very short - does anyone have a clue?

Note: if you aren't required to use shifts, you'd test the low n bits for being all-zero with a mask like x&7 == 0, or more generally x & ((1UL << n) - 1) == 0. How can I tell if a number is a multiple of four using only the logic operator AND?

Answer 1

With any integer represented in binary the remainder of division by any power of two is simply the value of the bits of lower order so 0b11001110 divided by 0b1000 has remainder 0b110. So in order to check for divisibility by 8 you need to check if the three low order bits are all zero:

if (((x >> 3) << 3) == x)
  divisibleBy8 = true;

Right shifting clears the bottom three bits before the left shift restores the magnitude and then compare to the original number.

As others have pointed out, if you know the bit width of the integer you can do this

if (!(x<<29))
  divisibleby8 = true;

Replace that 29 by 61 for 64-bit integers, etc. Apparently in Java you can do this:

if ((x << -3) != 0)
  divisibleby8 = true;

Because negative shifts such as -3 are interpreted as bit_width - 3 and it will work with both 32- and 64-bit integers.

(You don't need all the brackets, I've included for clarity)

Just for completeness

These are all pretty bad ways to test for divisibility by 8. Doing if !(x & 7) is clearer and almost certainly as fast or faster.

Answer 2

int num;

if(!(num & 7)) {
     // num divisible by 8
}

or

if(! (num << 29) ) { // assuming num is 32 bits
    // num divisible by 8
}