# C++ 84ms solution (beats 100% of cpp submissions)

• 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;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.