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

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

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.