How does this code work to count number of 1-bits?

Question

I found the following code to count the number of 1-bits in binary representation for given integer. Can anyone explain how it works? And how are the bit masks chosen for such task? Thanks.

int count_one(int x)
{
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Answer 1

This algorithm uses x as both the source of the computation and as memory. First, think about what the bitmasks are:

0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111

Let's go with an 8 bit example: a = 01101010

a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101 

If we add these two together, we get the bit count of each two bit pair. This result is at most 0x10, as the mask has only one bit set for each addition.

Now, we use the 0x33 mask, remember each consecutive 2 bits contain the result from the first operation. With this mask, we mask out consecutive 4 bits and add them. This result is at most 0x100. This goes on with the other masks, until we have the result in x.

Try it on paper, it will be pretty clear after a few steps.

Answer 2

It's a divide and conquer approach. Note that the first line will give you the sum on subsequent pairs, next the sum on subsequent quadruples,... and finally the number of bits.

Example (16 bit so consider your code without the last line)

1011001111000110

In the fist line we take & with even bits and odd bits shifted by one. Then we add.

For even bits:

num:  10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res:  00 01 00 01 01 00 01 00

For odd bits:

num>>1: 01 01 10 01 11 10 00 11
mask:   01 01 01 01 01 01 01 01
res:    01 01 00 01 01 00 00 01

We add those results and get sums in subsequent pairs

01 10 00 10 10 00 01 01

We repeat the same with following masks and corresponding shifts

2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111

And we get:

2nd: 0011 0010 0010 0010  // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100  // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001  // 9 bits in total