Counting Bits

Counting bits returns the number of set bits for every integer from 0 to n. Calling a popcount routine on each value works and is O(n log n), but the problem is really asking for the DP relation that makes it O(n). The insight is that each number's bit count can be built from a smaller number already computed. Two relations both achieve this. The cleaner one uses the right shift. Dropping the lowest bit of i gives i >> 1, a strictly smaller number whose count is already known, and the discarded bit is recoverable: - dp[i] = dp[i >> 1] + (i & 1) — the bits of i are the bits of i without its last bit, plus that last bit. Every term on the right is already computed when i is reached, so a single forward loop fills the table. The alternative uses i & (i − 1), which clears the lowest set bit. That produces a smaller number with exactly one fewer bit, giving dp[i] = dp[i & (i-1)] + 1. Both are O(n); the shift version tends to read more clearly. A third relation appears in many solutions — dp[i] = dp[i − powerOfTwo] + 1, tracking the largest power of two not exceeding i. It works, but requires maintaining that power separately, which the other two avoid entirely. The base case is dp[0] = 0, since zero has no set bits. Everything else follows from it. The follow-up asks for a single pass without built-in popcount, which is exactly what these relations deliver.

Counting bits reuses smaller answers: i >> 1 drops the last bit, so i has the same set bits as i / 2 plus its own final bit. That gives bits[i] = bits[i >> 1] + (i & 1) — every answer reuses one already computed, making the whole array linear.