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.

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize) 
{
    *returnSize = num + 1;
    int *ret = (int *)malloc(*returnSize * sizeof(int));
    /*数组元素初始化为0*/
    memset(ret,0x0,*returnSize * sizeof(int));
    /*i&(i-1)去掉最右边的1,因此要计算ret[i]就等于去掉的1个1加上ret[i&(i-1)]*/
    for(int i = 1;i <= num;i++)
        ret[i] = ret[i&(i-1)] + 1;
    
    return ret;
}

2022.01.16更新

class Solution {
public:
    vector<int> countBits(int n) {
        int highBit = 0;
        vector<int> bits(n+1,0);
        for(int i = 1;i <= n;i++) 
        {
            if(0 == (i&(i-1)))
                highBit = i;
            bits[i] = bits[i - highBit] + 1;
        }

        return bits;
    }
};

看官方题解前无论如何也想不到这题会用到动态规划，这里不断更新最高位，当值从小到大不断增加时可以根据前面已经计算出来的信息进行计算，举例：
例如计算17包含的1的个数，则计算小于17的最大的2的幂次方16，由于16只有1个1，因此17包含2个1.
几年前的解法居然还是平平无奇的计算