BitCount Method

Can anyone Explain this bitcount method.

public static int bitCount(int i) {
        // Hacker's Delight, Figure 5-2
        i -= (i >> 1) & 0x55555555;
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = ((i >> 4) + i) & 0x0F0F0F0F;
        i += i >> 8;
        i += i >> 16;
        return i & 0x0000003F;
    }

It's based on three observations,

1. The bitcount of a single bit is that bit itself.
2. The bitcount of the concatenation of two bitstrings is the sum of their bitcounts.
3. The bitcount of any string takes no more bits than that string itself.

The first two points together give you a simple recursive algorithm, split the string in two halves, recurse on both, return the sum. The base case is a single bit which you return. Simple so far.

The third observation is very important, it means that if you replace each substring with its bitcount, it will always fit in the space available to it. It means that if you give every count twice as much space (by separating the odd and the even groups), you can sum them and there will be no carry from one group into the next. Then you can rewrite it to this form:

i = (i & 0x55555555) + ((i >> 1) & 0x55555555); // sum groups of 1
i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // sum groups of 2
i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f); // sum groups of 4
...

And so on. What happens here is that on the left side of the + we take the even groups (0th, 2nd, 4th etc) and on right side we take the odd groups and align them with their corresponding even groups. For example, summing groups of 2:

[10 01 00 01 00 01 10 10]  // note that 11 cannot occur
split
even:  [0001 0001 0001 0010]
odd:   [1000 0000 0000 1000]
align: [0010 0000 0000 0010]
sum:   [0011 0001 0001 0100]

Then Hacker's Delight uses various tricks to optimize some operations out, for example groups of 4 can be summed using only the masking at the end, because the counts go up to 4 at most so summing them directly gives 8 at most, which still fits in the 4 bits available to it.