题目要求给出一个数num，求出小于等于num的数在二进制表示时个位上1的总和。例如给出3，小于等于三的数有0、1、2、3，0包含0个1，1包含1个1，2包含1个1，3包含2个1，所以答案应该是｛0，1，1，2｝。
我们可以通过统计每个数字上的1求出结果，这样的时间复杂度就为O(n*sizeof(integer))。
其实还有更好的办法，我们来分析一下，我们先列出部分数的二进制表示：
0
1
10
11
100
101
110
111
1000
我们可以看出，第二个数10有一个一，是从第一个数0上多加一个1得到，第三第四个数分别是第一第二个数加上1得到。而第五、六、七、八个数（100，101，110，111）是第一、二、三、四个数（0，1，10，11）加上1得到。
所以我们发现，可以通过已经生成的数来帮助生成后面的数，而上面分析的加1，其实是进位而来的，我们发现每当经过2^n后，一个数的二进制表示就会进1位，意味着前面的数在最高位加1可以得到后面的数，而回归题目，求1的个数，我们先求出前面数的1个数，后面的数就可以通过加1得到。
所以总体思想是，我们额外使用一个指针idx，指向前面的数，然后num[idx]+1为当前数的1的个数。那么问题就在于idx什么时候回到起点（0）？就是当经过2^n后，令idx为0。
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
AC代码：
[c language=”++”]
class Solution {
public:
vector<int> countBits(int num) {
int idx=0,n2=1;
vector<int> result;
result.push_back(0);
for(int i=1;i<=num;++i)
{
if(i==n2)
{
idx=0;
n2*=2;
}
result.push_back(result[idx++]+1);
}
return result;
}
};
[/c]