a cool algorithm for counting ones in a bitstring

The question: "Given a 32-bit unsigned integer, how do you count how many 1s are in it ?" is one of favorite interview quizzes. Naturally, the candidate is expected to code the "trivial" solution correctly - shifting right 32 times, counting when 1 "was shifted", etc. There are other techniques of doing it, up to a constant-time cool bit-fiddling trick. This is a nice topic, I think I should write an article about it once...

Anyway, lately I've heard of a new tehcnique to do it, which is also very cool, and has a curious complexity bound. It's O(b) where 'b' is the actual number of 1s in the given number.

Consider an unsigned integer num. What is: num & (num - 1) ? Without trying a lot, it's hard to come up with the answer. What it actually does, is "clear the rightmost 1 in the bit representation of num". Weird, huh ? It is rather simple to prove, though:

Consider a num whose lsb (rightmost bit) is 1 (i.e. an odd number). num - 1 is then the same number with that rightmost 1 becoming 0. So, obviously num & (num - 1) is "num with the rightmost bit cleared". So far so good.

Now lets consider even numbers (lsb = 0). Lets even generalize: num's binary representation ends with 10...0 (1 and, say, N 0s). Clearly, for such a number, num - 1 ends with 01...1 (0 and N 1s). So, num & (num - 1) again cleared that rightmost 1.

Only one special case left: whe "all 0" number. But since num is 0, whatever it is &-ed with, the result is 0.

Thus we have proved that for each num, num & (num - 1) clears its rightmost 1. So, the code for counting the amount of 1s is:

unsigned count_ones(unsigned num)
{
    unsigned count = 0;

    while (num)
    {
        num &= num - 1;
        ++count;
    }

    return count;
}

On each iteration, the rightmost 1 of num is cleared. count takes notice of how many times it happens until num becomes 0. If num has five 1 bits, the loop will iterate 5 times, etc.

An additional piece of trivia: num & (num - 1) can be useful for another "binary trick". How would you quickly check if a number is a power of 2 ? Answer: If num & (num - 1) is 0, num is a power of 2. Powers of 2 have a single 1 in their binary representation, so the num & (num - 1) operation clears it and leaves 0 as the result. For all other numbers it won't work because other 1s will be left.