CODEWITHSUNDEEP
bitwise-operatorsbit-shift
godzilla
godzilla

Reputation: 3125

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

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?

Upvotes: 9

Views: 21240

Answers (9)

kaviya sri Bathrachalam
kaviya sri Bathrachalam

Reputation: 9

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

This would fail for the input 0 (zero)

Upvotes: 0

marcuss
marcuss

Reputation: 31

For simplicity's sake

If you want to find out if any given integer N is multiple of X, being X a power of 2, just do:

    public static boolean isMultipleOfpowerOf2(int n, int x) {
    if((n&(x-1))==0){
       return true;
    }else {
        return false;
    }
}

Why this work?

Consider X = 8;

8:        1000*
9:        1001
10:       1010
11:       1011
12:       1100
13:       1101
14:       1110
15:       1111***
16:      10000*
17:      10001
18:      10010
19:      10011
20:      10100
21:      10101
22:      10110
23:      10111***
24:      11000*

Now you can see clearly, that any multiple of 8 doesn't use the 3* right bits, and this is true for all power of 2. You can see that X-1, 7, uses all of those bits***.

Now the rest is easy you can just mask out all the other bits using &(X-1), and if the answer is zero then you have a multiple.

N & (X-1) with  N = 9, X=8

N(9)    = 1001
X(8-1)  = 0111
N&(X-1) = 0001  this case is != 0

N(16)   = 10000
X(8-1)  = 00111
N&(X-1) = 00000  this time is == 0, it is a multiple.

More on this can be found in this really good article: Using Bitwise Operators to Work With Colors

Upvotes: 0

vishal
vishal

Reputation: 261

The most simple way to check for n’s divisibility by 9 is to do n%9. Another method is to sum the digits of n. If sum of digits is multiple of 9, then n is multiple of 9. The above methods are not bitwise operators based methods and require use of ‘%’ and ‘/’. The bitwise operators are generally faster than modulo and division operators. Following is a bitwise operator based method to check divisibility by 9.

you should check this link http://www.firmcodes.com/check-number-multiple-9-using-bitwise-operators/

Upvotes: 1

Jack Aidley
Jack Aidley

Reputation: 20107

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.

Upvotes: 24

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147164

x << (32-3) == 0 for an int; x << (64-3) == 0L for a long.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533720

In Java, without knowing if the type is long or int you can do this trick

if((x << -3) != 0)

This will shift by 29 or 61 bits as appropriate for that type. It will only be true if the lower three bits are 0.

Upvotes: 4

Mats Petersson
Mats Petersson

Reputation: 129484

if (x & ((1 << 3)-1) == 0)

Or, if you really want to use shifs:

if (x == ((x >> 3) << 3))

Upvotes: 2

Sergey L.
Sergey L.

Reputation: 22552

int num;

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

or

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

Upvotes: 9

T-Bull
T-Bull

Reputation: 2146

static boolean divisibleBy8(int num) {
    return (number & 7) == 0;
}

Upvotes: -4

Related Questions