Counting Bits

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.

本题为统计连续一串数字的二进制中 1 的个数，且要求总的时间复杂度为o(n). 确实，简单的统计一个二进制数字中1的个数不可能不处理就得到从而满足本题的时间要求

可能是看得多了这题就不会想着去一个数一个数的计算而是找相关数字的规律这样就清晰明了了数字是一个一个递增的那么他们中1的个数自然是有一定关系的列出来：

0　　 0

1　　 1 最低位两种情况

10　　1+0

11　　1+1 2的1次方位置为1 加上低位的两种情况

100　　1+0

101　　1+1

110　　1+1

111　　1+2 2的2次方位置为1 加上低2位的四种情况

...

其实就这样子可以看出规律最开始的最低位为0 1得到1的个数是0 和 1，

后面的则在此基础上进位到2的1次方位置上为1，最低位就有0和1两种情况此时1的个数为高位上的1加上地位上的0和1，

然后以此类推

程序中即为在数据的不断增长中存储当前最高位位置以方便一次增加地位上1的位数

vector<int> countBits(int num) {
        vector<int> res;
        if (num<0)
            return res;
        res.push_back(0);
        if (num>=1)
            res.push_back(1);
        int index=1, temp=0;  //index即为当前最高位的位置  temp记录总共加多少次
        for (int i=2; i<=num; ++i)
        {
            if (temp == pow(2, index))
            {
                temp = 0;
                ++index;
            }
            res.push_back(1+res[temp++]);
        }
        return res;
    }