Powers of two will always have 1 bit only. So check for this case with

(x != 0) && !(x & (x-1))

When a number is not a power of two, find the difference with the largest power of two you've encountered so far:

i - last_power_of_two = diff

diff is guaranteed to already be in the results array, and the last power of two will always be 1 bit so the result will be

1 + results[diff].

See source:

```
namespace {
bool isPowerOfTwo(int i){
return (i != 0 && !(i & (i - 1)));
}
}
vector<int> countBits(int num){
if (num < 0)
return vector<int>();
vector<int> results(num + 1);
int last_power_of_two = 0;
for (int i = 0; i <= num; ++i){
if (i == 0){
results[i] = 0;
continue;
}
if (isPowerOfTwo(i)){
last_power_of_two = i;
results[i] = 1;
continue;
}
int diff = i - last_power_of_two;
int num_of_bits = results[diff] + 1;
results[i] = num_of_bits;
}
return results;
}
```