[数据结构与算法]比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
看题之前先复习一下，按位与运算和移位运算
按位与运算：
定义就不说了，实在不会的就百度。
原理：0&0=0，0&1=0，1&1=1
举例：

       0 1 1 1
       0 1 1 0
   得  0 1 1 0

移位运算：
分为左移和右移
左移相当于扩大2倍，右移相当于除2并向下取整。
举例：

右移：  0 0 1 0 1 --> 0 0 0 1 0
左移:   0 0 1 0 1 --> 0 1 0 1 0

方法一：利用Brian Kernighan 算法解题
利用x&(x-1)，每次将最后的1给约去，重复操作即可。
为了易于理解，举个小栗子：

比如7吧 0 1 1 1
先出去最后一个1，利用x&(x-1)
 	0 1 1 1
    0 1 1 0
 得 0 1 1 0
 现在二进制序列为0 1 1 0
 再接着除去最后一个1
    0 1 1 0
    0 1 0 1
得  0 1 0 0
现在二进制序列为0 1 0 0
	0 1 0 0
	0 0 1 1
得	0 0 0 0
以上可得进行了3次，一共3个1

代码：

#include <iostream>

using namespace std;

int countOnes(int x)
{
    int ones=0;
    while(x>0)
    {
        x&=(x-1);
        ones++;
    }
    return ones;
}

int main()
{
    int n;
    cin>>n;
    int *a=new int[n+1];
    for(int i=0;i<=n;i++)
        a[i]=countOnes(i);
    for(int i=0;i<n+1;i++)
        cout<<a[i]<<" ";
    delete[] a;
    return 0;
}

方法二：动态规划——最低有效位
对于一个正整数i来说，向右移动一位，就像前面复习得所说，除以2再向下取整，表示为bits[i>>1]吧，那么bits[i]就很容易得出来了：

1. 如果i是偶数，则bits[i]=bits[i>>1];
2. 如果i是奇数，则bits[i]=bits[i>>1]+1;
   综合以上情况可得：bits[i]=bits[i>>1]+(1&i)
   这里(1&i)就是说，如果是偶数得话0&0=0,奇数的话1&1=1。

#include <iostream>

using namespace std;


int main()
{
    int n;
    cin>>n;
    int *bits=new int[n+1];
    for(int i=0;i<n+1;i++)
        bits[i]=0;
    for(int i=0;i<=n;i++)
        bits[i]=bits[i>>1]+(i&1);
    for(int i=0;i<n+1;i++)
        cout<<bits[i]<<" ";
    return 0;
}

不写了，还有别的方法，有兴趣的就去力扣官网瞅瞅吧，我就介绍这两种吧！嘿嘿