We know that n & (n-1) will eliminate the first right "one", so the number of "one" of n minus the number of (n & (n-1)) is one.

Than dp[i] = dp[i & (i-1)] + 1

vector<int> countBits(int num) {

vector<int> ret;

ret.reserve(num);

ret.push_back(0);

for(int i = 1; i <= num; i++){

ret.push_back((ret[(i-1) & i]) + 1);

}

return ret;

}