Counting Bits

Return the set-bit count for every value from 0 through n.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Counting Bits: The set-bit count for value reuses the completed count for value >> 1 and adds value & 1.

Input and goalReturn the set-bit count for every value from 0 through `n`.

Initialize answer[0]For limit 6, allocate seven cells. Zero has no set bits, so answer[0] = 0 before the loop starts.

base value 000?1?2?3?4?5?6

inputlimit = 6invariantentries below the next value are complete

Recognize it

The task requests bit counts for every integer in an increasing range, so each answer can reuse a smaller already-computed integer instead of recounting from scratch.

Keep true

Before computing answer[value], all lower indices are correct. Because value >> 1 is smaller, its count is available, and value & 1 contributes exactly the removed low bit.

Reuse it

When a bit operation maps each state to a smaller state, build answers in numeric order and append the removed-bit contribution; similar recurrences use x & (x - 1), highest powers of two, or parity.

Pattern: DP from a number with its last bit removed.

Simple idea: value >> 1 is the same number without its last bit. Add that last bit to the saved answer.

def count_bits(limit: int) -> list[int]:
   answer = [0] * (limit + 1)
   for value in range(1, limit + 1):
      answer[value] = answer[value >> 1] + (value & 1)
   return answer

Cost: $O(n)$ time and $O(n)$ answer space.