Count set bits

Overview

Counting how many bits are set — the population count — turns up everywhere from cardinality of a set to error-detection codes. The naive way tests each of the 32 positions in turn. The better way uses one remarkable identity: x & (x - 1) clears the lowest set bit and leaves everything else alone. Loop that until the value reaches zero and the number of iterations is the popcount, so the cost is proportional to the number of set bits rather than the width of the type. The same identity answers a second question for free: a power of two has exactly one set bit, so x && !(x & (x - 1)) is a one-line power-of-two test.

Why it matters

Population count is the workhorse of set-like data: how many features are enabled, how many squares a chess engine's bitboard occupies, how many errors a parity check found. And the power-of-two test guards the fast paths in allocators and hash tables, where x % n can be replaced by the much cheaper x & (n - 1) only when n is a power of two. Getting the zero case wrong here silently corrupts both.

Core concepts

Subtracting one flips a suffix. In binary, x - 1 turns the lowest set bit into 0 and turns every 0 below it into 1. Everything above the lowest set bit is untouched.

x & (x - 1) clears the lowest set bit. ANDing the original with that modified value keeps the untouched high part and zeroes the whole low suffix — the net effect is exactly one set bit removed. 0b1011 & 0b1010 = 0b1010.

Kernighan's loop. while (x) { count++; x &= x - 1; } runs once per set bit, so a value with three set bits costs three iterations regardless of where they sit. The simple shift-based loop always costs 32.

Power-of-two test. A power of two has exactly one set bit, so clearing it yields zero: (x & (x - 1)) == 0. But zero also satisfies that, and zero is not a power of two — hence the mandatory x && guard.

Unsigned matters. On unsigned types 0 - 1 wraps to all-ones by definition; on signed types the equivalent reasoning drags in implementation-defined behaviour. Keep these algorithms on unsigned/uint32_t.

Syntax notes

/* count set bits — cost is proportional to the number of set bits */
int popcount(unsigned x) {
    int c = 0;
    while (x) { c++; x &= x - 1u; }   // clear lowest set bit each pass
    return c;
}

/* exactly one bit set? (zero must be excluded explicitly) */
int is_power_of_two(unsigned x) {
    return x != 0u && (x & (x - 1u)) == 0u;
}

Key points:

• x &= x - 1u is the whole trick; memorise it.
• The x != 0 guard in the power-of-two test is not optional — 0 & (0-1) == 0 would otherwise report true.
• GCC/Clang offer __builtin_popcount, but it is a compiler extension; write the portable loop when portability matters.

Lesson

The population count is the number of 1 bits. The simplest method adds x & 1 and shifts right until zero; Kernighan's trick (x &= x-1) loops once per set bit. A value with exactly one bit set is a power of two — detected by x && !(x & (x-1)).

The demo counts bits and flags powers of two.

Code examples

#include <stdio.h>
static int popcount(unsigned x){ int c=0; while(x){ c+=(int)(x&1u); x>>=1; } return c; }
static int is_power_of_two(unsigned x){ return (x && !(x&(x-1u)))?1:0; }
int main(void){
    unsigned vals[] = {0u, 1u, 7u, 1024u, 0xFFu, 0xAAAAAAAAu};
    for(int i=0;i<6;i++)
        printf("0x%08X: %2d set bits%s\n", vals[i], popcount(vals[i]),
               is_power_of_two(vals[i])?"  (power of two)":"");
    return 0;
}

Line by line

Common mistakes

Signed-shift infinite loops; forgetting 0 is not a power of two.

Debugging tips

Compiler errors and warnings:

• warning: comparison of integer expressions of different signedness — you mixed a signed loop counter with an unsigned value. Keep the value unsigned and the counter int, and cast at the point of use.
• implicit declaration of __builtin_popcount on a non-GNU compiler — that intrinsic is an extension; use the portable loop.

Runtime symptoms:

• is_power_of_two(0) returns true. You dropped the x != 0 guard — the single most common bug in this lesson.
• The loop never terminates. You wrote x & (x-1) without assigning back. It must be x &= x - 1u.
• The count is always 32 or 0. You are testing x & 1 but shifting the wrong variable, or shifting a signed negative value (which sign-extends and keeps feeding in 1s).
• Counts are wrong for large values. You used int and hit bit 31; switch to unsigned.

Technique: test against the exhaustive brute-force version (loop 32 times counting (x>>i)&1) over a few thousand random values — the two must agree for every input.

Memory safety

No allocation is involved, but the same value-level hazards apply:

• Signed right shift. A shift-based popcount on a signed negative value sign-extends, feeding 1s in from the left, and the loop may never terminate. Always count on unsigned.
• The zero case. x - 1u on x == 0 wraps to 0xFFFFFFFF. That is well defined for unsigned, and Kernighan's loop never executes for zero, so it is safe — but the power-of-two test must still exclude zero explicitly.
• Modulo replacement. Substituting x & (n - 1) for x % n is only valid when n is a power of two. Assert it; a non-power-of-two silently produces wrong indices, which shows up much later as corrupted hash-table lookups.

Real-world uses

Concrete uses: Chess and Go engines store boards as 64-bit bitboards and use popcount to evaluate material. Databases use it on bitmap indexes to estimate result-set sizes. Error-correcting codes count differing bits. Memory allocators and hash tables assert their sizes are powers of two so they can mask instead of divide. Linux's CPU-affinity masks count how many cores are in a set.

Professional best practices:

Beginner:

• Learn x &= x - 1 as a single idea; it appears constantly.
• Never forget the zero guard in the power-of-two test.

Intermediate:

• Prefer the portable loop in library code; reach for __builtin_popcount (or a popcnt intrinsic) only in a hot path, behind a feature check.
• If you rely on power-of-two sizing for masking, assert it at construction time rather than trusting the caller.
• For a large bitset, count word by word rather than bit by bit.

Practice tasks

1. (Beginner) Portable popcount. Implement int popcount(unsigned x) with Kernighan's loop. Requirements: no compiler intrinsics. Example: popcount(0xFF) → 8; popcount(0) → 0. Concepts: x &= x-1.

2. (Beginner) Power-of-two test. Implement int is_power_of_two(unsigned x). Requirements: 0 must return 0. Example: 1024 → 1, 1000 → 0, 0 → 0. Concepts: single-set-bit property, the zero guard.

3. (Intermediate) Verify against brute force. Write a test that compares your popcount with a 32-iteration reference over 10,000 pseudo-random values and reports any mismatch. Concepts: oracle testing, exhaustive edge cases (0, 1, 0xFFFFFFFF).

4. (Intermediate) Sparse vs dense timing. Count bits for 0x1 and for 0xFFFFFFFF with both the shift loop and Kernighan's loop, printing iteration counts. Concepts: why the cost is proportional to set bits, not width.

Summary

x & (x - 1) clears the lowest set bit — that single identity gives you a population count whose cost scales with the number of set bits rather than the width of the type, and a one-expression power-of-two test. Loop x &= x - 1 while x is non-zero and count the passes; test x != 0 && (x & (x - 1)) == 0 for exactly one set bit, never omitting the zero guard. Keep the value unsigned so the wrap-around and shifting behaviour stays well defined.

Practice with these exercises

• Count set bits (popcount)
• Is it a power of two?