Source

1
2
3
4
5
6
7
8

# Assume v is 32-bit long
def popcount(v)
    v = v - ((v >> 1) & 0x55555555)
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333)
    ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
end

puts popcount(8)

Analysis

For example, let v = 01001110 (lowest 8 bits, others are all 0, in binary)

Step 1

v = v - ((v >> 1) & 0x55555555)

This step count 1’s appearance in each 2bits.

0x5 = 0101

In binary,
00 - 00 & 01 = 00 (0 1s in 00)
01 - 00 & 01 = 01 (1 1s in 01)
10 - 01 & 01 = 01 (1 1s in 10)
11 - 01 & 01 = 10 (2 1s in 11)

01001110 -> 01001001

Step 2

v = (v & 0x33333333) + ((v >> 2) & 0x33333333)

This step mask high 2 bits to 0 in each 4 bits, then add low 2 bits in each 4 bits.

In binary,
0100 -> 0000 + 0001 -> 0001
1001 -> 0001 + 0010 -> 0011

01001110 -> 00010011

Step 3

((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24

This step (v + (v >> 4) & 0xF0F0F0F) add high 4 bits to low 4 bits, then & 0xF0F0F0F mask high 4 bit to 0 in each 8 bits.

* 0x1010101 can be treaded as * (0x01000000 + 0x00010000 + 0x00000100 + 0x00000001).

* 0x0100000 means left shift 24 times.

* 0x0001000 means left shift 16 times.

* 0x0000010 means left shift 8 times.

* 0x0000000 do nothing.

Then we add them up. Now we have the sum of 1s’ count in each 8 bits, stored in a 32-bits data’s highest 8 bits.

>> 24 outputs the sum.