## Sunday, March 23, 2014

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

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.