Counting Bits
Problem statement
Given a non-negative integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every i from 0 to n.
Examples
Example 1
Input: n = 3
Output: [0, 1, 1, 2]
Explanation: 0 = 0, 1 = 1, 2 = 10, 3 = 11.
Example 2
Input: n = 6
Output: [0, 1, 1, 2, 1, 2, 2]
Explanation: 4 = 100, 5 = 101, 6 = 110.
Hints
Approach
Dynamic programming on the last bit. Shifting i right by one drops its lowest bit, so i has exactly the 1 bits of i >> 1, plus one more if its lowest bit is set.
ans[0] = 0.- For
ifrom1ton,ans[i] = ans[i >> 1] + (i & 1).
i >> 1 is always smaller than i, so its answer is ready when needed. Each entry takes constant time. For example, 6 is 110: 6 >> 1 = 3 (11, two bits) and 6 & 1 = 0, so ans[6] = 2.
O(n)Space O(1) extraclass Solution: def countBits(self, n: int) -> list[int]: ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i >> 1] + (i & 1) # bits of i without its last bit, plus that bit return ansFollow-up questions
- Use this table to count the 1 bits of a 32-bit number in four lookups.
Frequently asked questions
Yes: ans[i] = ans[i & (i - 1)] + 1. i & (i - 1) removes the lowest set bit, giving a smaller number with exactly one fewer 1 bit. Both are O(n).
Precomputing bit counts for a range is how fast popcount tables work: build the counts for all 256 byte values once, then count bits in any value a byte at a time. That lookup-table idea appears in bitmap indexes and in quickly computing prefix lengths for many netmasks.