Counting Bits

Problem

Given a non-negative integer n, produce an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.

• n is at most a couple hundred thousand.
• The intended solution runs in a single linear pass without calling a popcount routine on each number.

Examples

• n = 3 → [0, 1, 1, 2]: 0 = 0b0, 1 = 0b1, 2 = 0b10, 3 = 0b11.
• n = 7 → [0, 1, 1, 2, 1, 2, 2, 3]: 5 = 0b101 has two bits, 6 = 0b110 has two, 7 = 0b111 has three.
• n = 0 → [0].

Hints

1. Computing popcount independently for each number costs O(n log n). Can the answer for i be derived from an answer you already have?
2. What is the relationship between the bits of i and the bits of i >> 1? What about i and i & (i - 1)?
3. Dynamic programming: ans[i] = ans[i >> 1] + (i & 1), or equivalently ans[i] = ans[i & (i - 1)] + 1.