```
/*
* a[2^i+k] = a[2^(i-1)+k], k<2^(i-1)
* a[2^i+2^(i-1)+k] = a[2^i+k]+1, k<2^(i-1)
*/
class Solution {
public:
vector<int> countBits(int num) {
vector<int> bits(num+1, 0);
bits[1] = 1;
for(int range = 0b10; range <= num; range <<= 1){
int j = range;//2^i
int pre = range>>1;//2^(i-1)
int next = range<<1;//2^(i+1)
while( j < next && j <= num ){
if( j-range < pre )
bits[j] = bits[pre + j - range];
else
bits[j] = bits[j- pre] + 1;
j++;
}
}
return bits;
}
};
```