统计数的二进制表示中1的个数

题目：给定一个非负整数num，求0<=i<=num的每个整数的二进制数中一的个数

很简单就能想到使用builtin函数求解，但是很不幸这个方案被ban掉了，并且要求我们要能在一次遍历中求出结果。仔细观察结果产生的规律，我们没有必要每一次求解都将整个整数的二进制位遍历一次，只需利用已经计算出的结果和改数的最高位即可计算出结果。比如对数10101而言，看除第一位外的数值为5，显然此时1的二进制表达中5的位数已经求出来了了，于是乎我们只需要将这个结果加上1就可以了。还有一个问题是如何方便的确定减数的大小。假定减数设定为s，则s必定为2的幂，则在s 至 2s - 1中间的数都应该减去s再查表中的结果，当循环计数器i等于2s时，则将s扩大一倍，直到循环结束。具体的C语言实现如下：

int *countBits(int num, int *returnSize) {
    int *ret = malloc(sizeof(int) * (++num));
    ret[0] = 0;
    int begin = 0, sum = 1;
    for (int i = 1; i < num; i++) {
        if (i == sum) {
            begin = i;
            sum = 2 * i;
            ret[i] = 1;
        } else {
            int off = i - begin;
            if (off) {
                ret[i] = 1 + ret[off];
            } else {
                ret[i] = ret[off];
            }
        }
    }
    *returnSize = num;
    return ret;
}