今天刷力扣碰到了这道题，虽然是一道easy难度的题，但是感觉对位运算这块的算法很生疏，所以记录一下。
题目描述
给你一个整数 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
解法一：暴力法
直接从0开始到n，计算每个数字二进制中的1的个数，将其加到数组中。这里可以利用Brian Kernighan算法提升计算的速度，其原理是：对于任意的整数x，令x=x&(x-1)，能将x的二进制中的最后一个1变成0，因此不断重复，直到x=0为止，重复的次数就是x二进制中1的个数。
int countOnes(int x)
{
int cnt=0;
while(x!=0)
{
x=x&(x-1);
cnt++;
}
return cnt;
}
vector<int> countBits(int n)
{
vector<int> res(n+1);
for(int i = 0;i <= n; i++)
{
res[i] = cntones(i);
}
return res
}
解法二：动态规划——保留最高有效位
考虑是否能够找到一个整数i，在后面的一段范围内整数j的二进制1的个数，只用在整数i的二进制1的个数上加1，用式子来表达就是：
$$
res[i]=res[j]+1
$$
那该找什么样的数呢？首先傻子都知道0、1这两个数字有几个1，然后对于10、11来说，其首位都为1，若把最高位挡住，其形式与0、1一模一样，所以将0、1的1的个数加1，就是10、11的1的个数，同样对于100、101、110、111，其最高位都为1，将其最高位挡住，其形式也与上面几个数字一模一样，所以将上面求得的几个二进制数字的1的个数加1就是对应100、101、110、111的1的个数，以此类推，就可以求得相应的二进制数的1的个数。
上面例子中的10、100这样的数其实就是2的整数次幂，为了判断一个整数是不是2的整数次幂可以利用解法一中的性质，判断y&(y-1)==0即可，最终C++代码如下：
vector<int> countBits(int n)
{
vector<int> res(n+1,0);
int flag = 0;
for(int i=1;i<=n;i++)
{
if(i&(i-1)==0)//判断是否为2的整数次幂
flag = i;
res[i]=res[i-flag]+1;
}
return res;
}
解法三：动态规划——最低有效位
比如对于11这个奇数，其二进制是1011，可以考虑右移一位，将它变成101，此时它的1的个数就等于101，对于11本身来说，还要加上右移消失掉的一个1，也就是其本身的1的个数，若对于10这样的偶数，其二进制是1010，其右移后为101，由于其最低一位为0，所以10的1的个数就等于101的个数，通过这个例子就能很容易推出一个递推式：
$$
若x等于奇数，res[x]=res[x>>1]+1\
若x等于偶数，res[x]=res[x>>1]
$$
得出递推式之后，代码就很容易写出来：
vector<int> countBits(int n)
{
vector<int> res(n+1,0);
for(int i = 1;i <= n; i++)
res[i] = res[i>>1] + (i&1);
return res;
}