How do you count the set bits in an integer?
Short answer: Use Brian Kernighan's loop, which runs once per set bit because x & (x - 1) clears the lowest set bit. In production use __builtin_popcount (a single CNT/VCNT or POPCNT instruction where the CPU has one).
unsigned popcount(uint32_t x)
{
unsigned n = 0;
while (x) {
x &= x - 1; /* drop lowest set bit */
n++;
}
return n;
}
Three approaches compared
| Method | Loop count | Notes |
|---|---|---|
Test every bit: n += x & 1; x >>= 1; |
32 | simplest; fine for a first answer |
Kernighan: x &= x - 1 |
number of set bits | good when few bits are set |
| SWAR (parallel add) | 0 (constant time) | best general-purpose software method |
Simple version and its trap. Many people write this:
int a = 255, count = 0;
while (a) { count += a & 1; a >>= 1; }
It works for positive values, but for a negative int the arithmetic right shift keeps copying the sign bit, so a never becomes 0 and the loop never ends. Use unsigned/uint32_t.
Constant-time SWAR version (adds bits in pairs, then nibbles, then bytes):
unsigned popcount_swar(uint32_t x)
{
x = x - ((x >> 1) & 0x55555555u); /* 2-bit sums */
x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u); /* 4-bit sums */
x = (x + (x >> 4)) & 0x0F0F0F0Fu; /* 8-bit sums */
return (x * 0x01010101u) >> 24; /* add the 4 bytes */
}
Lookup table: a 256-entry table and four lookups is fast on a microcontroller without a multiplier, at the cost of 256 bytes of flash.
Follow-ups: "Count the bits that differ between a and b" is popcount(a ^ b) (the Hamming distance). "Count set bits for every number 0..n" uses bits[i] = bits[i >> 1] + (i & 1).