# BitCount Method

2

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;
}
``````
java
bit-manipulation
asked on Stack Overflow May 26, 2015 by (unknown user)

3

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.

1

Why don't you add some logging code to display i in binary at each step and see if you can work out what's happening?

Or reduce it to a smaller numebr of bits (8, say) and work through it on paper.

It'll give you a much better feel for the code than someone simply explaining it to you.

0

This algorithm dates back at least to HAKMEM item 169

``````    LDB B,[014300,,A]      ;or MOVE B,A then LSH B,-1
AND B,[333333,,333333]
SUB A,B
LSH B,-1
AND B,[333333,,333333]
SUBB A,B               ;each octal digit is replaced by number of 1's in it
LSH B,-3