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
“, __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; }.

Leave a Reply