Popcount: counting 1’s in a bit stream

Sometimes you need to count the number of 1's in a stream of bits. The most direct application would be summarizing yes/no data packed into bits. It's also useful in writing efficient, low-level bit twiddling code. But there are less direct applications as well. For example, three weeks ago this came up in a post I wrote about Pascal's triangle.

The number of odd integers in the nth row of Pascal's triangle equals 2b where b is the number of 1's in the binary representation of n.

The function that takes a bit stream and returns the number of 1's is commonly called popcount, short for population count.

Formula using floor

Here's an interesting formula for popcount taken from Hacker's Delight:

The sum is actually finite since after a certain point all the terms are zero. For example, if x = 13 (1101 in binary), then the right side is

13 - 6 - 3 - 1

which of course is 3.

Computing with gcc extensions

The gcc compiler has a function __builtin_popcount that takes an unsigned integer x and returns the number of bits in x set to 1. If the target platform has a chip instruction for computing popcount then compiler will generate code to call this instruction. Otherwise it uses library code.

For example, the following code prints 6, 1, and 2.

 #include <stdio.h> int main() { for (unsigned int x = 63; x < 66; x++) printf("%d\n", __builtin_popcount(x)); }

There are also functions __builtin_popcountl and __builtin_popcountll for unsigned long and unsigned long long arguments.

Computing in C

If you want to use your own C code to compute popcount rather than relying on compiler extensions, here are a couple possibilities taken from Hacker's Delight. First, one that only requires unsigned ints.

 int pop1(unsigned x) { x -= ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; x += (x >> 8); x += (x >> 16); return x & 0x0000003F; }

And here is a more elegant version that uses an unsigned long long.

 int pop2(unsigned x) { unsigned long long y; y = x * 0x0002000400080010ULL; y = y & 0x1111111111111111ULL; y = y * 0x1111111111111111ULL; y = y >> 60; return y; }