easyBit ManipulationPure DSA~12 min
Bit Population Table
A monitoring tool precomputes, for every state code 0..n, how many feature bits are set. Build that lookup table in a single linear pass.
Problem
Given an integer n, return an array ans of length n+1 where ans[i] is the number of 1-bits in the binary representation of i.
Input
An integer n (0 ≤ n ≤ 10^5).
Output
An array of n+1 integers, the popcount of each index.
Constraints
- Aim for O(n) total time, not O(n log n)
- 0 ≤ n ≤ 100,000
- ans[0] = 0
Examples
Example 1
Input
n = 5
Output
[0,1,1,2,1,2]
Counts of set bits for 0,1,2,3,4,5.
Example 2
Input
n = 2
Output
[0,1,1]
0→0, 1→1, 2(=10)→1.