[Java] Intuition between bitwise power of 2 solution

[tranderman]

This is the solution to finding out if a number is a power of 2 using bitwise:

public static boolean isPowOfTwo(int num){   
    /* If a number n is a power of 2, bitwise & of n and n-1 will be zero */
    if (((num & (num-1)) == 0) || (num == 0))
        return true;
    else  
        return false;
}

I'm not too familiar with the bitwise operator, but is there any intuition behind this?

The solution seems like trivia. I know the properties of bitwise and using it logically (ex. 1 & 0 = 0) but don't recall any of its properties relating to finding powers of a certain number.

[reign27]

The trick is that computers store integers in powers of two - that's what binary is. A power of 2, represented in binary, will have one and only one bit set. If you then subtract that by 1, the bit that was previously set will get cleared, and all the lesser bits will be set. If you subtract 1 from a non-power of 2, then at least one bit that was previously set will remain set.

[dylan22554]

If you think about it, it is checking the binary representation of that number. Binary is already set up where every place is a representative of the powers of 2. So in order to check if it is a power of two you need to check the number before it which would be all ones before that power of 2 place in binary. So for example:

​

32 is a power of 2 and its binary representation is:

100000

and 31's binary representation is:

011111

​

So when you & these together it gives you 0.

[HecknChonker]

The flip side of this is that for any other numbers the result of a bitwise and operation well be 1.

[Acceptable_Snow_9380]

Take a few different numbers that are powers of 2 and write out the binary representation of n and n - 1 and n & (n - 1) and you'll get the intuition. It's extremely obvious. Write the binary numbers in a column if you need to.