Problem

Explain what the following code does: ((n & (n-1)) == 0).

Solution

When we have A & B == 0, it means that A and B have no common 1s, i.e. any two bits at the same positions of A and B are either different from each other, or two 0s.

It works because a binary power of two is of the form 1000…000 and subtracting one will give you 111…111. Then, when you AND those together, you get zero, such as with:

1
2
3
4

   1000 0000 0000 0000
&   111 1111 1111 1111
   ==== ==== ==== ====
=  0000 0000 0000 0000

Any non-power-of-two input value will not give you zero when you perform that operation. For example, let’s try all the 3-bit combinations:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

n   n-1   n    n-1   n&(n-1)
---  ---  ---   ---   -------
0   -1   000   111     000 *
1    0   001   000     000 *
2    1   010   001     000 *
3    2   011   010     010
4    3   100   011     000 *
5    4   101   100     100
6    5   110   101     100
7    6   111   110     110

This can be used in Power of Two.