DSA Counting Bits

The problem

Counting Bits asks for the popcount of every number from 0 up to a given number n. The popcount of a number is its count of set bits, the bits equal to 1 in its binary form.

The answer is a list with one count per number. The list starts at 0, whose popcount is 0.

cases = [
    (0, [0]),
    (2, [0, 1, 1]),
    (5, [0, 1, 1, 2, 1, 2]),
    (8, [0, 1, 1, 2, 1, 2, 2, 3, 1]),
]
for n, expected in cases:
    print("n =", n, "counts:", expected)

Read the last row from the binary side. The number 8 is 1000 in binary, so its count drops back to 1. The number 7 is 111, so its count is 3.

Intuition: count each number from scratch

The first idea counts one number by reading its bits. It checks the lowest bit, adds it, then shifts the number right. The loop ends when no bits remain.

n = 13
total = 0
m = n
steps = 0
while m:
    total += m & 1
    steps += 1
    m = m >> 1
print("number", n, "binary", format(n, "b"))
print("popcount:", total, "bit checks:", steps)

The direct count works for any single number. Repeating it for every number in a range repeats the same work. The small answers inside a big number are counted again and again.

Brute force: a fresh bit scan for every number

The brute force runs the direct count once per number. A counter records every bit check across the whole range.

def direct(n):
    total = 0
    checks = 0
    m = n
    while m:
        total += m & 1
        checks += 1
        m = m >> 1
    return total, checks

for limit in [8, 16, 32]:
    counts = []
    all_checks = 0
    for n in range(limit + 1):
        total, checks = direct(n)
        counts.append(total)
        all_checks += checks
    print("up to", limit, "- bit checks:", all_checks, "last count:", counts[-1])
print("counts up to 8:", [direct(n)[0] for n in range(9)])

The answers are right and the waste is visible. Each number pays for its full bit length. A table can answer each number from a smaller one instead.

The optimal solution: build each count from the halved number

The state is a table where counts(i) is the popcount of i, and halving i drops its lowest bit, so counts(i) equals counts of i halved plus the dropped bit.

Halving is a right shift by one. The dropped bit is i mod 2, which the code reads as i & 1. The halved number is always smaller, so its count is already in the table.

def count_bits(n):
    counts = [0] * (n + 1)
    for i in range(1, n + 1):
        counts[i] = counts[i >> 1] + (i & 1)
    return counts

cases = [
    (0, [0]),
    (2, [0, 1, 1]),
    (5, [0, 1, 1, 2, 1, 2]),
    (8, [0, 1, 1, 2, 1, 2, 2, 3, 1]),
]
for n, expected in cases:
    result = count_bits(n)
    print("n =", n, "->", result, "match:", result == expected)

All four cases from the start of the article pass. Each new count costs one lookup and one addition. No bit is scanned twice.

Walkthrough: building the table up to 10

The walk fills one entry at a time. Each row shows the number, its halved value, the dropped bit, and the count they build.

counts = [0]
print("0 binary 0 count 0")
for i in range(1, 11):
    counts.append(counts[i >> 1] + (i & 1))
    print(i, "binary", format(i, "b"), "halved", i >> 1, "dropped bit", i & 1, "count", counts[i])
print("table:", counts)

Read the row for 10 off the table. The number 10 halves to 5, whose count is 2. Its dropped bit is 0, so its own count stays 2.

Complexity

The table does one step per number, so its time is O(n) for a range up to n. The table holds one count per number, so its space is O(n), and the answer itself needs that space.

def direct_checks(limit):
    checks = 0
    for n in range(limit + 1):
        m = n
        while m:
            checks += 1
            m = m >> 1
    return checks

for limit in [16, 32, 64]:
    print("up to", limit, "- brute bit checks:", direct_checks(limit), " table steps:", limit)

The brute checks grow faster than the range. The table steps match the range exactly. One built answer per number is the whole method.

Edge cases and pitfalls

Zero has no set bits, so its count is 0. A power of two has exactly one set bit. A number one below a power of two is all ones in binary, so its count is its bit length.

def count_bits(n):
    counts = [0] * (n + 1)
    for i in range(1, n + 1):
        counts[i] = counts[i >> 1] + (i & 1)
    return counts

counts = count_bits(16)
print("zero:", counts[0])
print("power of two, 16:", counts[16])
print("all ones, 15:", counts[15])
print("even number drops a zero bit, 10 vs 5:", counts[10], counts[5])
print("odd number drops a one bit, 11 vs 5:", counts[11], counts[5])
print("matches int.bit_count:", all(counts[n] == n.bit_count() for n in range(17)))

The pitfall is the dropped bit. Forgetting it makes every odd number read one too low. The last line checks the whole table against the built-in counter.