Counting Bits
Given an integer n, return an array of the number of 1's for each number from 0 to n.
Examples
0 is 0, 1 is 1, 2 is 10 — so the counts are 0, 1 and 1.
5 is 101; shifted right it is 10, which is 2 with one bit, and the dropped digit is 1 — so dp[5] = 2.
Problem Understanding
We need to return an array ans of size n + 1 such that for each i, ans[i] counts the 1 bits when i is written in binary.
Example: n = 2
- 0 -> 0 (0)
- 1 -> 1 (1)
- 2 -> 10 (1)
- Output:
[0, 1, 1]
Algorithm Strategy
Counting the bits of one number costs O(log n), so doing it for all of them costs O(n log n). Dynamic programming makes it O(n).
The insight: i >> 1 is i with its last binary digit thrown away. It therefore has every bit of i except that one, and i & 1 is exactly the digit that was thrown away.
Recurrence: dp[i] = dp[i >> 1] + (i & 1)
Because i >> 1 is always smaller than i, the value it needs has already been written — so one forward pass is enough.
Interactive Visualization
Each column is one number and holds its count of 1 bits. Watch the outlined cell: it is always i >> 1, the same number with its last binary digit dropped — and the panel beside the figure lines the two up so you can see which digit went missing.
Try Past 8: every power of two drops the count straight back to 1.
Dry Run
n = 5
| i | Binary | i >> 1 | dp[i >> 1] | i & 1 | Result dp[i] |
|---|---|---|---|---|---|
| 0 | 000 | 0 | 0 | 0 | 0 |
| 1 | 001 | 0 | 0 | 1 | 1 |
| 2 | 010 | 1 | 1 | 0 | 1 |
| 3 | 011 | 1 | 1 | 1 | 2 |
| 4 | 100 | 2 | 1 | 0 | 1 |
| 5 | 101 | 2 | 1 | 1 | 2 |
Edge Cases & Common Mistakes
Watch out for these pitfalls:
dp[0] needs no work. Zero has no 1 bits, and an array of zeros already says so — but the array has to be n + 1 long, not n.
i >> 1 is always already written. Shifting right halves the number, so the cell being read is to the left of the cell being written. That is what makes one forward pass enough.
A power of two resets the count. 8 is 1000 and dp[8] = 1, right after dp[7] = 3. If your counts only ever climb, you are counting something else.
Solution
One pass, reusing an earlier answer for every number — the lines light up as the figure above steps.
Counting Bits Code
1var countBits = function(n) {2 const dp = new Array(n + 1).fill(0);3 for (let i = 1; i <= n; i++) {4 const half = dp[i >> 1];5 dp[i] = half + (i & 1);6 }7 return dp;8};