BitsAlgorithmaka popcount, Hamming weight, Brian Kernighan's algorithm, bit count

Count Set Bits (Popcount)

Count the 1-bits of an integer with Kernighan's loop, a byte lookup table, a hardware popcount, or a DP over all numbers up to n.

▶ Visualize Pattern: Dynamic Programming Practice (3)

Progress

Overview

The population count of x is the number of 1-bits in its binary form: popcount(13) = popcount(1101b) = 3. It is the size of a Bit Masks set, the Hamming distance when applied to a ^ b, and the parity check when reduced mod 2.

Four standard methods. Naive: shift and test each of the w bits, O(w). Kernighan: repeat x &= x - 1, which clears the lowest set bit, so the loop runs exactly popcount(x) times. Lookup table: precompute counts for all 256 byte values and sum four (or eight) table reads. Hardware: __builtin_popcount, Integer.bitCount, bits.OnesCount, int.bit_count(), all compiled to a single POPCNT instruction where available.

For "count bits of every number from 0 to n" a DP does it in O(n) total: bits[i] = bits[i >> 1] + (i & 1) or bits[i] = bits[i & (i - 1)] + 1.

popcountHamming weightKernighanlookup tableO(k)

Intuition

A mental model before the formal terms.

Imagine a row of coins, some heads (1) some tails (0). Naive counting walks the whole row. Kernighan's trick is a magnet that picks up exactly one heads coin per pull and lands on tails only when none remain — so it takes as many pulls as there are heads, never more. A lookup table is having memorized the count for every possible group of 8 coins.

How it works

Kernighan: while x != 0: x = x & (x - 1); count++. Each iteration removes the lowest 1 (see Set, Clear, Toggle & Test a Bit).
Lookup: table[b] for b in 0..255 computed as table[b] = table[b >> 1] + (b & 1). Then popcount(x) = table[x & 0xFF] + table[(x >> 8) & 0xFF] + table[(x >> 16) & 0xFF] + table[(x >> 24) & 0xFF].
Parallel (SWAR) method: x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; return (x * 0x01010101) >> 24. It sums pairs, then nibbles, then bytes, in 12 operations with no branches.
Range DP: bits[0] = 0; for i in 1..n: bits[i] = bits[i >> 1] + (i & 1) — dropping the low bit gives a smaller number already solved.

Why it works

Kernighan: x - 1 flips the lowest set bit and all zeros below it; ANDing with x leaves higher bits unchanged and zeroes that lowest bit. So each step reduces popcount by exactly one, giving termination after popcount(x) iterations and a correct count.

Lookup and SWAR rely on popcount being additive over disjoint bit groups: popcount(x) = Σ popcount(byte_i). The SWAR steps compute counts for 2-bit, then 4-bit, then 8-bit fields, each field wide enough to hold its maximum count.

Range DP: i >> 1 is i without its lowest bit, so popcount(i) = popcount(i >> 1) + (i & 1), and i >> 1 < i guarantees it is already computed.

Recognition

How to tell a problem wants this.

"Number of 1 bits", "Hamming weight", "Hamming distance", "how many bits differ".
"For every integer from 0 to n compute…" over bits — the O(n) DP.
Any bitmask DP or subset enumeration where the size of the current set is needed, e.g. "exactly k elements chosen".

“number of ways” → Dynamic Programming “parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

n — Integer between 0 and 255

= 180

1/14n = 180 (10110100). Instead of testing all 8 bits, Kernighan's trick loops once per set bit.

Lowest set bit about to be clearedBit cleared by n & (n-1)Set bits still remaining

PseudocodeLearn Count Set Bits (Popcount) →

1count = 0
2while n != 0:
3  n = n & (n - 1)   # clears the lowest set bit
4  count += 1
5return count

Variables

n180

count0

Complexity

best O(1)

avg O(k)

worst O(w)

space O(1)

Speed

Pseudocode

1// Kernighan
2count = 0
3while x != 0:
4  x = x & (x - 1)
5  count += 1
6return count
7// Range DP for 0..n
8bits[0] = 0
9for i in 1..n: bits[i] = bits[i >> 1] + (i & 1)

Implementations

11 · Kernighan's loop: one iteration per set bit
2def popcount_kernighan(x: int) -> int:
3    count = 0
4    while x:
5        x &= x - 1   # clear lowest set bit
6        count += 1
7    return count
8 
9 
102 · Byte lookup table
11_TABLE = [0] * 256
12for _b in range(1, 256):
13    _TABLE[_b] = _TABLE[_b >> 1] + (_b & 1)
14 
15 
16def popcount_table(x: int) -> int:
17    """32-bit lookup-table popcount (x must be non-negative)."""
18    return (_TABLE[x & 0xFF] + _TABLE[(x >> 8) & 0xFF]
19            + _TABLE[(x >> 16) & 0xFF] + _TABLE[(x >> 24) & 0xFF])
20 
21 
223 · Built-in / intrinsic
23def popcount_builtin(x: int) -> int:
24    return x.bit_count()   # 3.10+, counts |x|; bin(x).count("1") on older versions
25 
26 
274 · Popcount of every number up to n in O(n)
28def count_bits_upto(n: int) -> list[int]:
29    bits = [0] * (n + 1)
30    for i in range(1, n + 1):
31        bits[i] = bits[i >> 1] + (i & 1)
32    return bits
33 
34 
355 · Hamming distance
36def hamming_distance(a: int, b: int) -> int:
37    return (a ^ b).bit_count()
38 
39 
40if __name__ == "__main__":
41    assert popcount_kernighan(13) == popcount_table(13) == popcount_builtin(13) == 3
42    assert count_bits_upto(5) == [0, 1, 1, 2, 1, 2]
43    assert hamming_distance(1, 4) == 2

Walkthrough

Kernighan's loop works on unbounded ints; for negative x it never terminates (infinitely many ones), so pass non-negative values.
The module-level _TABLE is built at import time with the same recurrence as count_bits_upto.
int.bit_count() (3.10+) is the built-in; it counts the bits of abs(x). bin(x).count("1") is the portable fallback and about 3x slower.
count_bits_upto is the O(n) DP bits[i >> 1] + (i & 1).

Complexity (this implementation)

time O(k) Kernighan, O(1) table/builtin · space O(1)

For huge ints bit_count() is O(number of digits), which is the true information cost.

Language notes

int.bit_count() was added in 3.10; earlier versions use bin(x).count("1").
The table approach only helps for a fixed 32/64-bit width; for general ints bit_count wins.
x & (x - 1) on a negative int is well-defined but the loop does not terminate — Python has no "bit 31" to stop at.

Common mistakes in this language

Passing a negative number to a Kernighan loop and hanging.
Using bin(x).count("1") in a tight loop on 3.10+ instead of bit_count().
Applying the 32-bit table to numbers wider than 32 bits — high bits are silently ignored.

Language differences that matter here

Intrinsic: C++ std::popcount (C++20) / __builtin_popcount(ll) map to one instruction; Python int.bit_count() (3.10+) or bin(n).count("1"); JS/TS have none — Kernighan, a byte table, or the SWAR formula with Math.imul.
Negative inputs: C++ requires unsigned for std::popcount; JS handles a 32-bit two's-complement pattern after >>> 0 (popcount(-1) is 32); Python bit_count() counts abs(x), and Kernighan's loop on a negative Python int never terminates.
Width: the table/SWAR versions are 32-bit specific; C++ has 64-bit overloads, JS needs BigInt above 32 bits, Python needs nothing.

Complexity

Best

O(1)

Average

O(k)

Worst

O(w)

Space

O(1)

Kernighan runs k = popcount(x) iterations, at most the word width w. Lookup table and SWAR are O(w / 8) and O(1) respectively; hardware popcount is one instruction. The 0..n DP is O(n) time and space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Sparse words (few 1-bits) — Kernighan is fastest because it does popcount(x) steps, not w.
Hot loops on many words without hardware support — a 256-entry lookup table or SWAR is branch-free.
Bit counts for every number in a range — the O(n) DP, never n independent popcounts when n is large.

Avoid it when

When a library popcount exists — it compiles to one instruction and is always at least as fast.
On Python big ints the naive bit-by-bit loop is slow; use int.bit_count() or bin(x).count("1").

Alternatives

Bit Masks Prefix Sum

Common mistakes

Using arithmetic >> in the naive loop on a negative 32-bit value — it sign-extends forever. Use >>> in Java/JavaScript or an unsigned type in C++.
Writing x & x - 1 and relying on precedence (correct in most languages but reads wrong); parenthesize.
In the range DP, indexing bits[i >> 1] before it is filled — iterate i in increasing order.
Computing Hamming distance with a & b or a | b instead of a ^ b.

Interview patterns

Counting Bits (0..n) with bits[i] = bits[i & (i - 1)] + 1.
Number of 1 Bits / Hamming Weight with Kernighan; Hamming Distance via XOR.
Total Hamming distance over an array: for each bit position count ones c, add c * (n - c).
Sort integers by number of 1 bits; filter masks of size k in bitmask DP.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced
Recognizing a dynamic-programming problemAdvanced

Mock interviews

Coin ChangeIntermediate

Example problems

Single Numbereasy Counting Bitseasy Bit Counting Trickseasy

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related