## [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;
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);
count = ((count >> bits) & masks) + (count & masks);
count = ((count >> bits) + count) & masks;
count = ((count >> bits) + count) & masks;
count = ((count >> bits) + count) & masks;
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):

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;
}


### 3 response to "[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)"

1. By: Tong Posted: 2016/12/31

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):”

• By: liuchao Posted: 2017/01/02

just fixed. thanks.