Counting Bits

Counting Bits asks you to count the set bits of every number from 0 to n. The naive answer counts each number from scratch; the elegant answer notices that the count for i is hiding inside a number you already solved.

The slow way first

The obvious idea: for each i from 0 to n, count its bits with a small loop (peel off the lowest bit until the number is zero). Counting one number takes up to O(log i) steps, so the whole thing is O(n log n).

The question to ask: while I am computing the answer for i, have I already computed something almost identical? It turns out I have — the answer for a smaller number is one shift away.

The idea: reuse the number with its low bit removed

Take any i. If you drop its lowest bit with a right shift, you get i >> 1 — a smaller number we filled in earlier. Dropping that one bit changes the count by exactly the bit you dropped, which is i & 1 (1 if i is odd, 0 if even). So:

dp[i] = dp[i >> 1] + (i & 1)

Because i >> 1 is always smaller than i, its answer is already in the array by the time we need it. Every value costs O(1).

Walk through it

Step through the animation. The pointer i moves left to right filling dp. At each stop, the cell that lights up to the left is dp[i >> 1] — the value being reused. For example at i = 5, 5 >> 1 = 2, so we read dp[2] = 1 and add 5 & 1 = 1 to get dp[5] = 2.

Pseudocode

make an array dp of length n + 1, all zeros
dp[0] = 0                       # zero has no set bits
for i from 1 to n:
    dp[i] = dp[i >> 1] + (i & 1)   # reuse a smaller answer, add the low bit
return dp

The Python solution

def count_bits(n):
    dp = [0] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        # i >> 1 drops the low bit; (i & 1) adds it back
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

• dp is the answer array; dp[i] will hold the set-bit count of i.
• dp[0] = 0 is the base case — zero has no 1-bits and seeds every later value.
• i >> 1 is i with its lowest bit removed, a strictly smaller index we already filled.
• i & 1 is that lowest bit: 1 when i is odd, 0 when even.
• Line 6 is the whole algorithm — one O(1) recurrence per number.

Complexity

We spend O(n) extra space for the dp array (which is also the required output), and fill it in a single linear pass. The trick — express the answer for i in terms of a smaller, already-solved subproblem — is the essence of dynamic programming.

When this pattern shows up

Practice