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

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.

Advertisements

1 Comment (+add yours?)

  1. AndroidResearch
    Mar 09, 2012 @ 17:39:29

    One of those tricky questions you might get on an interview… 🙂

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: