</>EmbeddedInterview

How do you count the set bits in an integer?

MediumBit Manipulation

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).