给你一个整数n，对于0<=i<=n,计算其二进制中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
方法一：Brian Kernighan 算法
最直观的做法是对从 00 到 nn 的每个整数直接计算「一比特数」。每个int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。Brian Kernighan 算法，可以在一定程度上进一步提升计算速度。Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为x 的「一比特数」。对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)。
int coutnoes (int x)
{
int ones=0;
while(x>0)
{
x&=x-1;
ones++;
}
return ones;
}
int* countBits(int n, int* returnSize){
int *res=(int *)malloc(sizeof(int)*(n+1));
*returnSize=n+1;
for (int i=0;i<=n;i++)
{
res[i]=coutnoes(i);
}
return res;
}
时间复杂度：O（nlogn）
空间复杂度：O（1）
解法二：动态规划——最高有效位
方法一需要对每个整数使用O（logn）的时间计算【—比特数】。可以换一个思路，当计算i的【—比特数】时，如果存在0<=j<=i,j的【—比特数】已知，且i和j相比，i的二进制表示之多一个1，则可以快速得到i的—比特数。
令bits[i]表示i的[-比特数]，则上述关系表示为bits[i]=bits[j]+1。
对于正整数x，如果可以知道最大的正整数y，使得y<=x，且y是2的整数次幂，则y的二进制表示中只有最高为是1，其余是0，此时称y为x的[最高有效位]。令z=x-y，显然0<=z
为了判断一个正整数是不是2的整数次幂，可以利用方法一中提到的按位与运算性质。如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y&(y-1)=0。由此可见，正整数 y 是 2 的整数次幂，当且仅当 y & (y−1)=0。
显然，0 的「一比特数」为 0。使highBit 表示当前的最高有效位，遍历从 1 到 n的每个正整数 i，进行如下操作。如果 i&(i-1)=0，则令highBit=i，更新当前的最高有效位。i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个整数，因此遍历到 i 时，i−highBit 的「一比特数」已知，bits[i]=bits[i−highBit]+1。
int* countBits(int n, int* returnSize){
int highbit=0;
int *bit=(int *)malloc(sizeof(int)*(n+1));
*returnSize=n+1;
bit[0]=0;
for (int i=1;i<=n;i++)
{
if ((i&(i-1))==0)
{
highbit=i;
}
bit[i]=bit[i-highbit]+1;
}
return bit;
}
时间复杂度：O（n）
空间复杂度：O（1）
方法三：动态规划——最低设置位
定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1 所在位。例如，1010 的二进制表示是 1010_(2) 10(2)，其最低设置位为 2，对应的二进制表示是 10_{(2)}10 (2) 。
令y=x & (x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y
int* countBits(int n, int* returnSize) {
int* bits = malloc(sizeof(int) * (n + 1));
*returnSize = n + 1;
bits[0] = 0;
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
时间复杂度：O（n）
空间复杂度：O（1）