public class Solution {

public int[] countBits(int num) {

```
// The original solution without DP, which is a simple bit trick that x&(x-1) eliminates the last bit 1 of x.
/**
int[] res = new int[num+1];
for(int i = 0; i < num + 1; i++) {
int cnt = 0;
int x = i;
while(x > 0) {
x &= (x-1);
cnt++;
}
res[i] = cnt;
}
return res;
**/
int[] dp = new int[num+1];
for(int i = 1; i < num + 1; i++) {
dp[i] = dp[i&(i-1)] + 1;
}
return dp;
}
```

}