Counting Bits

March 2026 · 26 min read

The popcount (population count) problem: given an integer, how many bits are set to 1? This seemingly simple question has surprisingly deep algorithmic solutions.

Method 1: Naive Loop

int count_bits_naive(uint32_t n) {
    int count = 0;
    while (n) {
        count += n & 1;   // check last bit
        n >>= 1;          // shift right
    }
    return count;
}
// Time: O(32) — always checks all 32 bits
// Even for n = 1, it loops 32 times (if n is nonzero at any position)

Method 2: Brian Kernighan's Algorithm

This elegant algorithm only iterates as many times as there are set bits. For sparse numbers (few 1-bits), it is much faster than the naive loop.

int count_bits_kernighan(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);   // clear the lowest set bit
        ++count;
    }
    return count;
}
// Time: O(k) where k = number of set bits
// For n = 0b10000000, only ONE iteration!

Why it works: n & (n - 1) clears exactly the lowest set bit each time. When all bits are cleared, n becomes 0 and the loop ends. We count how many clearing operations it took.

Method 3: Lookup Table

// Precompute popcount for all 8-bit values (256 entries)
uint8_t table[256];
void build_table() {
    table[0] = 0;
    for (int i = 1; i < 256; ++i) {
        table[i] = table[i >> 1] + (i & 1);
    }
}

int count_bits_table(uint32_t n) {
    return table[n & 0xFF]
         + table[(n >> 8) & 0xFF]
         + table[(n >> 16) & 0xFF]
         + table[(n >> 24) & 0xFF];
}
// Time: O(1) — four table lookups
// Space: 256 bytes for the table

Method 4: Parallel Bit Counting (SWAR)

This mind-bending technique counts bits in parallel using a divide-and-conquer approach within a single integer. It is how __builtin_popcount is often implemented:

int popcount_parallel(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);           // count pairs
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333); // count nibbles
    n = (n + (n >> 4)) & 0x0F0F0F0F;           // count bytes
    return (n * 0x01010101) >> 24;              // sum bytes
}
// Time: O(1) — fixed number of operations
// No branching, no memory access — pure arithmetic

Why the magic constants? Read each constant in binary and the trick becomes pair-wise addition:

• 0x55555555 = 0101…0101 — selects the odd-position bits. Step 1 collapses each pair of bits into a 2-bit count (0,1,2). The clever identity n - ((n>>1) & 0x55..) computes that sum without an addition.
• 0x33333333 = 0011…0011 — masks even/odd nibbles. Step 2 sums adjacent 2-bit counts into 4-bit counts (0–4 per nibble).
• 0x0F0F0F0F — isolates each byte. Step 3 sums two nibbles into one byte (0–8 per byte).
• 0x01010101 multiplication — sums all four byte-counts into the top byte; >> 24 reads it. The total fits in 8 bits because max popcount is 32.

Method 5: Compiler Built-ins

// GCC / Clang:
int count = __builtin_popcount(n);      // 32-bit
int count = __builtin_popcountll(n);    // 64-bit

// MSVC:
#include <intrin.h>
int count = __popcnt(n);                // 32-bit
int count = __popcnt64(n);              // 64-bit

// C++20:
#include <bit>
int count = std::popcount(n);           // standard!

Hamming Distance

The Hamming distance between two integers is the number of positions where their bits differ. It equals the popcount of their XOR:

int hamming_distance(uint32_t a, uint32_t b) {
    return __builtin_popcount(a ^ b);
}
// XOR gives 1 at every position where a and b differ
// Popcount counts those differing positions

// Example: hamming_distance(0b1011, 0b1101)
// XOR = 0b0110 → popcount = 2

Counting Bits from 0 to n (LeetCode 338)

Two equivalent O(N) DP recurrences — both are CP staples:

// Recurrence A: drop the lowest set bit
vector<int> countBits(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i & (i - 1)] + 1;
        // i & (i-1) clears the lowest set bit
        // So dp[i] = dp[i with one fewer bit] + 1
    }
    return dp;
}

// Recurrence B: shift right and add the parity bit
//   bits[i] = bits[i >> 1] + (i & 1)
// Reads "popcount(i) = popcount(i/2) + last bit of i".
vector<int> countBits2(int n) {
    vector<int> bits(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        bits[i] = bits[i >> 1] + (i & 1);
    return bits;
}
// Time: O(n), Space: O(n). Both compile to ~2 ops per i.

Other Useful Built-ins

// Count leading zeros (position of highest set bit):
int clz = __builtin_clz(n);      // undefined for n=0
int highest_bit = 31 - clz;      // index of MSB

// Count trailing zeros (position of lowest set bit):
int ctz = __builtin_ctz(n);      // undefined for n=0
int lowest_bit_idx = ctz;        // index of LSB

// Find first set bit (1-indexed):
int ffs = __builtin_ffs(n);      // 0 if n=0

// 64-bit variants: __builtin_clzll / __builtin_ctzll / __builtin_ffsll

// C++20 standard versions (defined for n=0):
#include <bit>
int lz = std::countl_zero(n);
int tz = std::countr_zero(n);
int hb = std::bit_width(n) - 1;  // index of MSB; 0 → -1

// Lowest set-bit VALUE (not index): isolate the bit itself
int lsb_val = n & -n;             // works on two's-complement
// Example: n = 0b01101100 → n & -n = 0b00000100
// Pair with ctz to get the index, or with n -= (n & -n) to peel bits.

Lookup Table on 16-bit Chunks

The 8-bit table is fine, but a 16-bit table cuts lookups in half (two instead of four) at a 64 KB cost — cheap if you call popcount in a hot inner loop on machines without POPCNT:

uint8_t T16[1 << 16];
void build16() {
    for (int i = 1; i < (1 << 16); ++i)
        T16[i] = T16[i >> 1] + (i & 1);
}
int popcount16(uint32_t n) {
    return T16[n & 0xFFFF] + T16[n >> 16];
}
// 64 KB table, 2 lookups, 1 add. Beats the 8-bit version on memory-warm code.

Complexity Tradeoffs

Summary

• Naive loop: O(32), checks every bit.
• Kernighan's: O(k) where k = set bits. Uses n &= n - 1.
• Lookup table: O(1) with 256-byte precomputation.
• Parallel (SWAR): O(1) with pure arithmetic.
• Built-in: __builtin_popcount(n) compiles to one instruction.
• Hamming distance: popcount(a ^ b).
• Count bits 0..n: DP with dp[i] = dp[i & (i-1)] + 1 or dp[i] = dp[i>>1] + (i&1).
• Lowest set-bit value: n & -n. Index: __builtin_ctz(n).
• Highest set-bit index: 31 - __builtin_clz(n) (or std::bit_width(n) - 1).

Practice Problems

Drill these in order — the first three are warm-ups, the rest exercise the full popcount toolbox.

1. LC 191 · Number of 1 Bits Easy — basic popcount drill; try Kernighan and the builtin.
2. LC 338 · Counting Bits Easy — the canonical DP recurrence bits[i] = bits[i>>1] + (i&1).
3. LC 461 · Hamming Distance Easy — popcount of a ^ b.
4. LC 477 · Total Hamming Distance Medium — column-wise counting; sum k · (n-k) per bit.
5. LC 762 · Prime Number of Set Bits Easy — popcount + small-prime lookup.
6. LC 1356 · Sort Integers by Number of 1 Bits Easy — pair sort key with popcount.
7. LC 401 · Binary Watch Easy — enumerate hours/minutes by total popcount.
8. CSES · Bit Strings / Codeforces 484A · Bayan Bus / Bit++ family CP — popcount-style enumeration.