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 to check if number n is power of 2 or not:
bool isPowerOfTwo(int n)
{
return (n > 0) && ((n & (n - 1)) == 0);
}
Though there are other ways to check that as discussed here.