Explain ((n & (n-1)) == 0)

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/explain-n-n-1-0/#problem.

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.