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:
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:
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 Problem.