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

3 Answers


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
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.

answered on Stack Overflow May 26, 2015 by harold

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.

This page may help.

answered on Stack Overflow May 26, 2015 by Phil Anderson

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
    ADD A,B
    AND A,[070707,,070707]
    IDIVI A,77             ;casting out 63.'s

These ten instructions, with constants extended, would work on word lengths up to 62.; eleven suffice up to 254..

answered on Stack Overflow May 26, 2015 by ddyer

User contributions licensed under CC BY-SA 3.0