[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)

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:
- Construct lookupTable with size 256(8-bit);
- Calculate the lower 8 bits of n, find calculated result in lookupTable and add to count;
- 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 (log232):
- right shift 1 bit, & 01010101 01010101 01010101 01010101 (0x55555555 in HEX);
- right shift 2 bits, & 00110011 00110011 00110011 00110011 (0x33333333 in HEX);
- right shift 4 bits, & 00001111 00001111 00001111 00001111 (0x0F0F0F0F in HEX);
- right shift 8 bits, & 00000000 11111111 00000000 11111111 (0x00FF00FF in HEX);
- 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; }
I think you meant i & 1 in this line:
“Lookup table stores count for each number, and lookupTable[i] can be calculated by lookupTable[i >> 1] + (i & i):”
just fixed. thanks.