Donnie’s Blog

This is an interview question I had at Microsoft, from when I was interviewing for my very first internship. That would have been way back in early 1996.

“You are given an integer n, and you need to write a function to count how many bits in n are set to 1.”

As most reasonably savvy programmers would do, I wrote a function that shifts n to the right, counting the times that the least-significant bit is set to 1, until n is 0. Something like this:

  int countBits(int n) {
    int count = 0;
    while (n != 0) {
      if (n & 1)
        count++;

      n = n >> 1;
    }

    return count;
  }

In general, this function will take O(b) time to complete, where b is the bit-width of n. This is fine; it’s a constant, so we are all happy with that.

But it turns out that there’s a faster way!

Question 1: Do you know what the faster way is?

Question 2: Do you know how it works?

I will admit up front that my interviewer showed me, way back in 1996, the faster way. But I just figured out how it works this weekend.

It turns out that there is a very interesting expression (n & (n - 1)), which has the unique characteristic that it has exactly one less bit set to 1 than n does. So, you can rewrite the above function as follows:

  int countBits(int n) {
    int count = 0;
    while (n != 0) {
      n = n & (n - 1);
      count++;
    }

    return count;
  }

Now the function will only require as many iterations as there are bits actually set to 1. If you assume that on average this will be half the bits, then you have reduced your average running time to b / 2. In addition, you have eliminated an if-statement so your loop will run faster than before. Yee haw!

So probably the more important question is, Why does this even work? Because if it only works sometimes then we can still run into trouble. It’s easiest to start with a simple case, where there is only one bit set in n. For instance, n = 16. This means that n = 00010000 in binary. Of course, n - 1 will then be 00001111 in binary (15 in decimal). And of course, when you compute (n & (n - 1)), it’s obvious that the result will be 00000000. So clearly this works when n is a power of two!

Now, when n is not a simple power of two, there will be multiple bits set to 1 in n. The key is that only the least significant bit set to 1 will be affected when you compute n - 1; other more significant 1-bits will not be changed in the result. For example, if n = 45, you have 00101101, and n - 1 = 00101100. Only the least significant 1-bit was changed. Thus, when you compute (n & (n - 1)), this clears the least significant 1-bit from n.

Taking this example one step further, you end up with n = 44, which is 00101100. The value of n - 1 is 00101011, which if you bitwise-and it with n, again clears the least significant 1-bit from n: (n & (n - 1)) = 00101000.

This is a pretty neat trick, and it provides a really easy way to tell if a number is a power of two. I’m glad that I finally figured it out, after all these years!

This entry was posted on Monday, July 16th, 2007 at 7:45 am and is filed under Hacking. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.