比特位的计算

给你一个整数 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+1if(n == 0){*returnSize = 1;//当n=0时，返回长度为1,数组第一个元素为0ans[0] = 0;return ans;}if(n == 1){*returnSize = 2;//当n=1时，返回长度为2,数组第一个元素为0，第二个元素为1ans[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;
}