Imagine you're standing in front of a massive control panel with 64 toggle switches. Some are flipped up (ON), and some are flipped down (OFF). Your boss wants to know exactly how many switches are currently ON. Now, you could walk down the line and inspect every single switch one by one—even the ones that are OFF—but that's tedious. Or, you could use a "magic" tool that allows you to instantly snap the next ON switch to OFF, counting them as they click. If there are only three switches ON, you only perform three actions, regardless of whether the panel has 64 or 1,000 switches.

In C, "counting set bits" (also known as the population count or popcount) is exactly this. A "set bit" is just a bit with a value of 1. Depending on how sparse your data is, you can choose between a brute-force approach, a clever algorithmic shortcut, or a hardware-accelerated instruction.

The Slow Walk Down the Line

The most intuitive way to do this is the naive approach. You loop through every bit position, mask it, and increment a counter if the result is non-zero. It's the equivalent of checking every single switch on that panel.

int naive_popcount(uint32_t n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n >> i) & 1) {
            count++;
        }
    }
    return count;
}

This works, but it's inefficient. If you're processing a number like 1 (which only has one bit set), you're still performing 32 iterations. In a tight loop within a high-performance system, this is a waste of cycles.

Kernighan's Clever Shortcut

This is where the "magic tool" comes in. There's a legendary trick called Brian Kernighan’s algorithm. The core of the trick is the expression n & (n - 1). In binary, subtracting 1 from a number flips all the bits after the rightmost set bit, including that set bit itself. When you AND that with the original number, the rightmost set bit vanishes.

Mapping this back to our analogy: instead of checking every switch, you're jumping straight to the next "ON" switch and flipping it "OFF" until there are no "ON" switches left.

int kernighan_popcount(uint32_t n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1); // Clear the least significant set bit
        count++;
    }
    return count;
}

I love this method because its time complexity is proportional to the number of set bits, not the total number of bits. If you have a 64-bit integer with only 2 bits set, this loop runs twice. Period.

Letting the Compiler Do the Heavy Lifting

In the real world, if you're using GCC or Clang, you shouldn't actually write your own loop for this. Modern CPUs have a dedicated instruction (like POPCNT on x86) that can count the bits in a single clock cycle. The compiler provides a "builtin" function that maps directly to this hardware instruction if the CPU supports it, or falls back to a highly optimized library function if it doesn't.

uint32_t count = __builtin_popcount(n);

It's a one-liner. It's faster than any loop you could write. Whenever I'm reviewing code and I see a manual loop for popcount, my first suggestion is always to use the builtin unless the project specifically forbids compiler-specific extensions.

The Bit-Hacker's Parallel Approach

Sometimes you'll see some truly bizarre-looking code in low-level libraries that looks like a series of magic numbers and shifts. This is "SWAR" (SIMD Within A Register). It treats the integer as a vector of smaller integers and sums them in parallel.

uint32_t parallel_popcount(uint32_t i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Don't try to memorize this. This approach uses divide-and-conquer to sum adjacent bits, then adjacent pairs, then adjacent quads. It's constant-time, meaning it takes the same number of operations regardless of whether the number is 0 or 0xFFFFFFFF. It's an engineering marvel, but for 99% of your C projects, Kernighan's or the builtin is the way to go.

📋 Practical Task

Building a Hamming Distance Calculator

The Hamming Distance between two integers is the number of positions at which the corresponding bits are different. This is a fundamental concept in error detection and genetic sequencing (comparing DNA strands). To calculate it, you XOR the two numbers together—which results in a bitmask where only the differing bits are set to 1—and then perform a popcount on that result.

Your Task: Write a program that:

1. Defines a function int calculate_hamming_distance(uint32_t a, uint32_t b).
2. Inside that function, use Brian Kernighan’s algorithm to count the set bits of the XOR result.
3. In main, test your function with the following values and print the results:
   • a = 0x12345678, b = 0x12345678 (Expected: 0)
   • a = 0x00000000, b = 0xFFFFFFFF (Expected: 32)
   • a = 0x00000001, b = 0x00000002 (Expected: 2)