Bits — Counting Bits

solve(n) — return an array ans of length n + 1 where ans[i] is the number of
1 bits in i, for every 0 <= i <= n. Counting each number separately is
O(n log n); do it in O(n) with dynamic programming.

Shifting right drops the last bit: i >> 1 is a smaller number whose answer you already
know, and the dropped bit is i & 1. So ans[i] = ans[i >> 1] + (i & 1).

Examples

solve(2)  → [0,1,1]
solve(5)  → [0,1,1,2,1,2]
solve(0)  → [0]