How does this bitwise operation check for a power of 2?

Question

I'm looking at some code which should be trivial -- but my math is failing me miserably here.

Here's a condition that checks if a number if a power of 2 using the following:

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

My question is, how does using a bitwise AND between num and num - 1 determine if a number is a power of 2?

Answer 1

Well,

if you have X = 1000 then x-1 = 0111. And 1000 && 0111 is 0000.

Each number X that is a power of 2 has an x-1 that has ones on the position x has zeroes. And a bitwise and of 0 and 1 is always 0.

If the number x is not a power of two, for example 0110. The x-1 is 0101 and the and gives 0100.

For all combinbations within 0000 - 1111 this leads to

   X  X-1 X && X-1  
0000 1111 0000   
0001 0000 0000 
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110

And there is no need for a separate check for 1.

Answer 2

Any power of 2 minus 1 is all ones:

2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

Take 8 for example. 1000 & 0111 = 0000

So that expression tests if a number is NOT a power of 2.

Answer 3

Explained here nicely

Also the expression given considers 0 to be a power of 2. To fix that use !(x & (x - 1)) && x; instead.

Answer 4

Well, the first case will check for 2⁰ == 1.

For the other cases the num & (num - 1) comes into play:

That's saying if you take any number, and mask off the bits from one lower, you'll get one of two cases:

1. if the number is a power of two already, then one less will result in a binary number that only has the lower-order bits set. Using & there will do nothing.

   • Example with 8: 0100 & (0100 - 1) --> (0100 & 0011) --> 0000

2. if the number is not a power of two already, then one less will do this, which returns the highest power of two not greater than num:

   • Example with 3: 0011 & (0011 - 1) --> (0011 & 0010) --> 0010

So the actual expression finds everything that isn't a power of two, including 2⁰.