# Four lines, C++, time O(n), space O(n)

• ``````class Solution {
public:
vector<int> countBits(int num) {
vector<int> ret(num+1, 0);
for (int i = 1; i <= num; ++i)
ret[i] = ret[i&(i-1)] + 1;
return ret;
}
};``````

• Won't `i&(i-1)` take sizeof(integer) time?

• It's O(n) space. You can't solve it O(1) space as you are returning an array of size num.

• Yes. It's O(n) space. The title is wrong.

• It's a constant time operation.

• Yes, it was my fault and I have made it right. Thanks !

• Can you explain a bit why i&(i-1)?

• i&(i-1) drops the lowest set bit. For example: i = 14, its binary representation is 1110, so i-1 is 1101, i&(i-1) = 1100, the number of "1" in its binary representation decrease one, so ret[i] = ret[i&(i-1)] + 1. (Sorry, my English is so poor and I have tried my best to make it clearly, I hope you can understand my explanation)

• Thanks fengcc, it is very clear!

• This answer bothers me. How would you begin to figure out this method? iterating through and bit shifting is easy to see, but I couldn't see myself coming up with this method without significant prodding.

• @fengcc you are so clever!!!!! the idea is so beautiful

• Just want to add to fengcc's explanation, as it still took me sometime to think it through. So when you remove the lowest set bit (or the rightmost non-zero bit), you will arrive at a smaller number than the current number: 14 ==> 12. Since your computed series already includes all the counts for n=0,1,2,...,12,13, you will most certainly already have the count for the number 12. And as fengcc pointed out, the only difference in count between 14, and 12 is 1 bit, so you add 1 to the count for 12 and get the correct count for 14.

• How elegant to rely directly on the nature of the question. Doesn't even need to derive a pattern.

• Nice...
How beautiful code it is.

• @fengcc Nice solution! I never thought about the iteration to solve the problem with for;

• it's very great! after read @fengcc explanation and think it through ,I write it for myself :
It is need to return an array, which every item value is the numbers '1' in binary of the item's sequence No. . As i&(i-1) decrease one '1', so array[i] - 1= array[i&(i-1)] , then array[i] = array[i&(i-1)] + 1.

• yeah , the code is very easy to understand , however I can't come up with such idea to solve this question , can you
tell me how do you improve your thinking in daily life

• lihailewodege

• I think the logic is great, but how can you prove that bit_count(i & i-1) will be always bit_count(i)-1? Is it known formula?

• @asbear yeah, same question here, the code is definitely elegant, but I don't know why it works.

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