Counting Bits
Count the set bits of every number from 0 to n, and see how each answer is built from one already computed
Problem Statement
Given an integer n, return an array of length n + 1 where position i holds the number of 1 bits in i.
Input: n = 2
Output: [0, 1, 1]
0 → 0 zero ones
1 → 1 one one
2 → 10 one one
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]Intuition
The obvious solution: run Number of 1 Bits on every value from 0 to n. That is O(n log n) — up to 32 steps each, n times.
It also throws away everything it learns. Counting the bits of 11 tells you nothing about 12, even though you are about to compute that too.
Ask the question from dynamic programming: am I recomputing something I already know?
Look at what a right shift does:
11 = 1 0 1 1 three ones
11 >> 1 = 1 0 1 two ones ← this is the number 5
So: bits(11) = bits(5) + (the bit that fell off)The insight
Shifting right by one drops the last bit and leaves a smaller number you have already solved.
bits(i) = bits(i >> 1) + (i & 1)
└─ already in └─ the dropped
the array bit: 0 or 1i >> 1 is always less than i, so its answer is already sitting in the array. Each value costs one lookup and one addition — O(1) — instead of a loop.
Approach
Create the array with result[0] = 0
Zero has no set bits. This is the base case, and it is the only value not computed from another.
For each i from 1 to n, read the answer for i >> 1
i >> 1 is roughly i / 2, so it was filled in earlier. This is the "already solved subproblem".
Add the last bit back
i & 1 is 1 if i is odd, 0 if even. That is exactly the bit the shift discarded.
Solution
def count_bits(n: int) -> list[int]:
"""Count set bits for every value from 0 to n.
bits(i) = bits(i >> 1) + (i & 1)
Dropping the last bit gives a smaller value already solved.
"""
result = [0] * (n + 1)
for i in range(1, n + 1):
result[i] = result[i >> 1] + (i & 1)
return resultThe parentheses around i & 1 are required. In Python & binds lower than +, so result[i >> 1] + i & 1 would add first and then AND — silently wrong.
An equally good alternative recurrence
bits(i) = bits(i & (i - 1)) + 1.
Clearing the lowest set bit (the trick from Number of 1 Bits) also lands on a smaller, already-solved number — with exactly one fewer set bit.
Both are O(n). The shift version is easier to explain; this one connects the two problems more directly.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Time — one pass from 1 to n, doing constant work per value. The naive version is O(n log n), since each of the n values needs its own bit-counting loop.
Space — O(n) for the output array. That is required by the problem, so it does not count as extra space; no additional structure is used beyond it.
Edge Cases
Related Problems
- Number of 1 Bits — the single-number version, and the alternative recurrence
- Climbing Stairs — the same "build on a smaller answer" shape, without bits
- Dynamic Programming — why writing answers down is the whole technique