How do you count the number of set bits (popcount) in an integer?

Either loop testing one bit at a time, use Brian Kernighan's x &= x-1 trick to loop once per set bit, or call a compiler builtin like __builtin_popcount(x).

* x & (x−1) zeroes the lowest set bit, so looping it runs exactly once per set bit — Brian Kernighan's popcount. *

Simple loop method:

int popcount(unsigned int x) {
    int count = 0;
    while (x) {
        // Add lowest bit
        count += x & 1;
        // Shift right
        x >>= 1;
    }
    return count;
}

Brian Kernighan's trick (faster - only loops for set bits):

int popcount(unsigned int x) {
    int count = 0;
    while (x) {
        // Clear lowest set bit
        x &= (x - 1);
        count++;
    }
    return count;
}

Why x & (x-1) clears the lowest set bit:

x     = 01011000
x-1   = 01010111  (borrows from lowest 1)
x&x-1 = 01010000  (lowest 1 is gone!)

Compiler builtin (fastest - uses CPU instruction):

// GCC/Clang
int count = __builtin_popcount(x);
// MSVC
int count = __popcnt(x);

Use case in RE: Counting flags, Hamming distance, parity checks.

Go deeper:

• Hamming weight — Wikipedia — popcount algorithms, Kernighan's trick, and hardware instructions.