比特位的计算

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

思路：先将两个基本的数1和0进行判断，再从这基础上进行奇数偶数判断。

#include <stdio.h>
#include <stdlib.h>
 
 
int* countBits(int n, int* returnSize)
{
    int *ans = malloc(sizeof(int)*(n+1));//开辟一个空间，长度为n+1
    if(n == 0)
    {
        *returnSize = 1;//当n=0时，返回长度为1,数组第一个元素为0
        ans[0] = 0;
        return ans;
    }
    if(n == 1)
    {
        *returnSize = 2;//当n=1时，返回长度为2,数组第一个元素为0，第二个元素为1
        ans[0] = 0;
        ans[1] = 1;
        return ans;
    }
    ans[0] = 0;
    ans[1] = 1;//从两种基础的情况上开始判断
    for(int i = 2;i <= n ;i++)//循环判断奇数偶数
    {
        if(i % 2 == 0)
        {
            ans[i] = ans[i/2];
/*当i为偶数时，ans[i]中1的个数=和ans[i/2]中个数相等，因为两个二进制数i/2相加，所产生1的进位与i/2中1的个数相等*/
        }else{
            ans[i] = ans[i - 1] + 1;//当i为奇数时，所包含的1的个数为前一个偶数中1的个数+1
        }
    }
    *returnSize = n+1;
    return ans;
}
 
int main()
{
    int n = 10;
    int returnSize = 0;
    int* nums = countBits(n, &returnSize);
    printf("returnSize = %d\n",returnSize);
    for(int i = 0;i < returnSize;i++)
    {
        printf("nums[%d] = %d\n",i,nums[i]);
    }
    free(nums);
    nums = NULL;
    return 0;
}