Counting bits
Why it exists
Problem: Given a number `n`, you need to count the number of set bits (1s) for every integer from `0` to `n`. Naively counting bits for each number independently takes O(n log n) time.
Naive approach: Loop through `1` to `n`, and use a while loop shifting bits right to count the 1s for each number.
Better idea: Notice that the binary representation of any number `i` is just the binary representation of `i >> 1` (its integer half) with one extra bit at the end. We can reuse the bit count we already computed for `i >> 1` and add 1 if `i` is odd. This calculates all counts in O(n) time.
Mental model
Every number is just a smaller number shifted left, with a potential 1 tacked onto the end. Re-use the smaller number's bit count!
Initialize an array `bits` of size `n+1`. To find the bit count of `i`, look up the bit count of `i >> 1` (which we already computed since it's smaller), and add 1 if `i` has a 1 in the lowest bit position (`i & 1`).
Repeated decision: Can I reuse the bit-count I already computed for a smaller number that this one is built from, instead of recounting from scratch?
Explanation
To solve this efficiently, we employ Dynamic Programming (state and transition). Our state is the number of set bits for a given integer `i`. Our transition is reusing the answer for `i >> 1`.
The core recurrence is:
`bits[i] = bits[i >> 1] + (i & 1)`
Let's hand-trace building this array from `0` to `7`:
- `i = 0` (`000`): Base case. `bits[0] = 0`.
- `i = 1` (`001`): `bits[1 >> 1] + (1 & 1)` -> `bits[0] + 1 = 1`.
- `i = 2` (`010`): `bits[2 >> 1] + (2 & 1)` -> `bits[1] + 0 = 1`.
- `i = 3` (`011`): `bits[3 >> 1] + (3 & 1)` -> `bits[1] + 1 = 2`.
- `i = 4` (`100`): `bits[4 >> 1] + (4 & 1)` -> `bits[2] + 0 = 1`.
- `i = 5` (`101`): `bits[5 >> 1] + (5 & 1)` -> `bits[2] + 1 = 2`.
- `i = 6` (`110`): `bits[6 >> 1] + (6 & 1)` -> `bits[3] + 0 = 2`.
- `i = 7` (`111`): `bits[7 >> 1] + (7 & 1)` -> `bits[3] + 1 = 3`.
Notice that the bit count of `110` (6) is exactly the bit count of `011` (3) because shifting left just adds a `0` to the end, which doesn't increase the number of 1s. The only time the bit count increases is when the lowest bit is a `1`, which we capture with `(i & 1)`.
Alternatively, for counting bits of a SINGLE isolated number, you can use **Brian Kernighan's algorithm**: `x & (x - 1)` clears the lowest set bit. Looping this until `x` is `0` counts bits in exactly O(popcount) steps. However, for a sequence from `0` to `n`, the DP recurrence is faster because it reuses previous answers.
Common mistakes
- Recomputing each count independently: Writing a helper function to count bits and calling it `n` times misses the whole point of the problem. This node exists specifically to demonstrate reusing smaller subproblem answers (1D DP in disguise).
- Getting the recurrence direction backwards: You must build the array iteratively from `1` up to `n`. `i >> 1` is a SMALLER index, which guarantees that `bits[i >> 1]` has already been computed by the time you need it.
Recall questions
- What is the O(n) DP recurrence for counting bits from 0 to n?
- Why does `bits[i] = bits[i >> 1] + (i & 1)` work?
- What does Brian Kernighan's trick `x & (x - 1)` do?
Questions & answers
Return an array of the number of 1s in the binary representation of every number in the range [0, n].
Initialize an array of size n+1. Iterate from 1 to n, setting `ans[i] = ans[i >> 1] + (i & 1)`. Return the array.
Approach: Direct application of the DP counting bits recurrence.
Determine the number of set bits in a single large integer as fast as possible.
Use Brian Kernighan's algorithm: repeatedly apply `x = x & (x - 1)` and increment a counter until `x` is 0.
Approach: When not computing a range, Kernighan's trick jumps straight to the 1s, taking O(set bits) time instead of O(total bits).
Continue learning
Previous: Bitwise operators
Related: State & transition