```
//Let f(k) be the number of 1's in the binary representation of k, then
//f(k) = 1, if k is a power of 2
//f(k) = f(j) + f(k - j), otherwise
//here j is the largest power of 2 that is no larger than k
//based on the above equation
//if k = 1, then f(k) = 1
//if k = 2, then f(k) = 1
//if k = 3, then j = 2, thus f(k) = f(2) + f(1) = 2
//please note that i in the code is the smallest power of 2 that is no less than k
//that is, i is the power of 2 following j
public class Solution {
public int[] countBits(int num) {
int[] arr = new int[num + 1];
if (num == 0) {
return arr;
}
int i = 1;
int j = 1;
for (int k = 1; k <= num; k++) {
if (k == i) {
arr[k] = 1;
j = i;
i <<= 1;
}
else {
arr[k] += arr[j] + arr[k - j];
}
}
return arr;
}
```