338.位数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围内的每个数 i，计算其二进制数中 1 的个数，并将它们作为数组返回。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize){
    int * array = (int *)malloc(sizeof(int) * (num + 1));
    memset(array, 0, sizeof(int) * (num + 1));
    for(int i = 1; i < num + 1; i++)
    {
        array[i] = array[i >> 1] + (1 & i);
    }
    *returnSize = num + 1;
    return array;

思考：暴力破解是可行的，但还有更优雅的解决方案。

你可以通过计算前面得到的结果知道下面的数字。先判断第一个数字是否为1比特位，然后右移一位即可。右移一位得到的结果的位数为1的结果之前已经得到了比特位，将两者相加即可得到当前位数1的个数。