Math & Bit Manipulation · LC #338
Counting Bits
Compute the number of 1 bits for every integer from 0 to n in O(n) time using the DP recurrence `dp[i] = dp[i >> 1] + (i & 1)`.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Return an array `ans` of length `n+1` where `ans[i]` is the number of 1s in the binary representation of `i`. Solve it in O(n) time and O(n) output space (O(1) extra).
Sample I/O
Input: n = 2 Output: [0,1,1] Input: n = 5 Output: [0,1,1,2,1,2]
Intuition
How to Think About It
Intuition
Right-shifting `i` by 1 gives `i/2`, whose bit count is already computed. The shifted number differs from `i` only in the last bit, so `dp[i] = dp[i>>1] + (i&1)` builds the answer bottom-up without repeating work.
Core Concept
DP recurrence: `dp[0] = 0`; for `i` from 1 to n: `dp[i] = dp[i >> 1] + (i & 1)`. `i >> 1` drops the LSB (already computed); `i & 1` contributes 1 if LSB is set, 0 otherwise. Processes in ascending order so sub-problems are always already solved.
When to use
When you need popcount for a range of integers - O(n) vs O(n·32) for calling hammingWeight on each.
When NOT to use
When you only need popcount of a single integer - LC 191 is simpler. When n is very large and sparse - streaming popcount with Kernighan is more cache-friendly.
Key Insights
What to Know Cold
- The recurrence leverages the fact that `i >> 1` is always < `i`, so the DP table is trivially ordered.
- Alternative recurrence: `dp[i] = dp[i & (i-1)] + 1` (Kernighan-style DP - also O(n)).
- Both recurrences produce the same result; the `i>>1` version is simpler to derive in an interview.
- Output array doubles as the DP table - no extra space needed beyond the output.
- The pattern of popcount values follows a self-similar (fractal) structure: each power-of-2 block is the previous block with all values incremented by 1.
1 example
Worked Examples
Trace dp for n=5
Build table 0..5
dp[0]=0; dp[1]=dp[0]+(1&1)=1; dp[2]=dp[1]+(2&1)=1; dp[3]=dp[1]+(3&1)=2; dp[4]=dp[2]+(4&1)=1; dp[5]=dp[2]+(5&1)=2
countBits(5); // [0,1,1,2,1,2] // i=4 (100): dp[4]=dp[2]+0=1+0=1 // i=5 (101): dp[5]=dp[2]+1=1+1=2
Shows how right-shift recurrence reuses prior results - no 32-bit inner loop.