Tools Matter

Function int bitCount(int n) returns how many “1”s does the number n have expressed in the binary form. For example, 0b101 is the binary form of number 5, so bitCount(5) returns 2.

the naive way

Check if each bit equals 1 and return the sum:

int bitCount(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

the optimized naive way

Consider the number 0b1. After the first right shift, 31 “0”s’ left and the function can return count immediately: there is no need adding to count when n becomes “0” after one certain right shift. The optimized code is as follows:

int bitCount(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Brian Kernighan’s way

n & (n – 1) will clear the last significant bit set, e.g. n = 112

Hence loop will go through as many iterations as there are set bits, and when n becomes zero, count is exactly the answer.

int bitCount(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

Lookup Table

int bitCount(int n) {
    int[] lookupTable = new int[256];
    for (int i = 0; i < 256; i++) {
        lookupTable[i] = lookupTable[i >> 1] + (i & 1);
    }

    return lookupTable[n & 0xFF]
            + lookupTable[(n >> 8) & 0xFF]
            + lookupTable[(n >> 16) & 0xFF]
            + lookupTable[n >> 24];
}

Lookup table stores count for each number, and lookupTable[i] can be calculated by lookupTable[i >> 1] + (i & 1):

However, Integer.MAX_VALUE is too large for an array, and we cannot afford the O(n) space complexity.

A divide and conquer way would be better:

1. Construct lookupTable with size 256(8-bit);
2. Calculate the lower 8 bits of n, find calculated result in lookupTable and add to count;
3. right shift n with 8 bits, and continue (2) until n equals zero.

Parallel

int bitCount(int n) {
    int bits[] = {1, 2, 4, 8, 16};
    int masks[] = {
            0b01010101010101010101010101010101,  // 0x55555555
            0b00110011001100110011001100110011,  // 0x33333333
            0b00001111000011110000111100001111,  // 0x0F0F0F0F
            0b00000000111111110000000011111111,  // 0x00FF00FF
            0b00000000000000001111111111111111,  // 0x0000FFFF
    };

    int count = n - ((n >> 1) & masks[0]);
    count = ((count >> bits[1]) & masks[1]) + (count & masks[1]);
    count = ((count >> bits[2]) + count) & masks[2];
    count = ((count >> bits[3]) + count) & masks[3];
    count = ((count >> bits[4]) + count) & masks[4];
    return count;
}

Shift-and-add is another divide and conquer way for this problem, the algorithm can be explained by this gragh:

And this gragh is for the same number(8-bit) in binary form:

For a 32-bit number, we have to do this 5 times (log₂32):

1. right shift 1 bit, & 01010101 01010101 01010101 01010101 (0x55555555 in HEX);
2. right shift 2 bits, & 00110011 00110011 00110011 00110011 (0x33333333 in HEX);
3. right shift 4 bits, & 00001111 00001111 00001111 00001111 (0x0F0F0F0F in HEX);
4. right shift 8 bits, & 00000000 11111111 00000000 11111111 (0x00FF00FF in HEX);
5. right shift 16 bits, & 00000000 00000000 11111111 11111111 (0x0000FFFF in HEX);

And this algorithm can be optimized as follows(AKA int Integer.bitCount() which implemented by JDK, as the title picture shows up):

int bitCount(int n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

MIT HAKMEM

Consider a 3-bit binary number “abc”( a, b, c ∈ {0, 1} and value of “abc” equals a * 4 + b * 2 + c):

Hence abc - (abc >> 1) - (abc >> 2) == a + b + c, which is count of 3-bit binary number “abc”. For a 32-bit number, we need one more step: mask the high bits.

Next, like Parallel algorithm, we will calculate every 6-bit count:

But we don’t need calculate every-12bit of result anymore, result % 63 is exactly the answer. Here is proof:

\begin{aligned}
result &= a\cdot 64^{5} + b\cdot 64^{4} + c\cdot 64^{3} + d\cdot 64^{2} + e\cdot 64 + f \\ \\

result \% 63 &= \left ( a\cdot 64^{5} + b\cdot 64^{4} + c\cdot 64^{3} + d\cdot 64^{2} + e\cdot 64 + f \right ) \%63 \\
 &= \left ( a\cdot 64^{5} \% 63 + b\cdot 64^{4} \% 63 + c\cdot 64^{3} \% 63 + d\cdot 64^{2} \% 63 + e\cdot 64 \% 63 + f \% 63 \right ) \% 63 \\
 &= \left ( a \% 63 + b \% 63 + c \% 63 + d \% 63 + e \% 63 + f \% 63 \right ) \% 63 \\
 &= \left ( a + b + c + d + e + f \right ) \% 63
\end{aligned}

∵ a + b + c + d + e + f ≤ 32
∴ (a + b + c + d + e + f) % 63 = a + b + c + d + e + f
∴ count = result % 63 = a + b + c + d + e + f

Here is our code:

int bitCount(int n) {
    int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
    return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}