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

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.

Let’s look at ((n & (n-1)) == 0).

- n == 1. n – 1 == 0. 1 & 0 == 0.
- n == 2. n – 1 == 1. 10 & 01 == 0.
- n == 3. n – 1 == 2. 11 & 10 != 0.
- n == 4. n – 1 == 3. 100 & 011 == 0.
- n == 5. n – 1 == 4. 101 & 100 != 0.
- n == 6. n – 1 == 5. 110 & 101 != 0.
- n == 7. n – 1 == 6. 111 & 110 != 0.
- n == 8. n – 1 == 7. 1000 & 0111 == 0.

Looking at those n that satisfies ((n & (n-1)) == 0), we find n == 1, 2, 4, 8, i.e. power of 2.

If we think about a general case, let’s say we have a binary number abcde1xxx.

Let think about 1xxx first, after subtracting 1, they have to share not common 1: therefore n-1 must be like 0yyy, which means you must ”borrow” 1 from the most significant bits. That indicates you must have 1xxx as 1000 and 0yyy as 0111. So we have the number n in the form abcde1000.

Now let us look at abcde part. n-1 is abcde0111. To make ((n & (n-1)) == 0), we must have abcde as 0000.

To sum up, n must be in the form of 00…010…0, i.e. the power of 2.

### Like this:

Like Loading...

*Related*

AndroidResearch

Mar 09, 2012@ 17:39:29One of those tricky questions you might get on an interview… 🙂