前n个数字二进制中1的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 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 <= 10⁵

思路：1.Brian Kernighan算法 对每一个数字通过这个算法计算出1的个数。
2.动态规划，这里的动态规划有三种方式，其本质都是根据已知问题的解求当前问题。

//Brian Kernighan算法
int help(int n){
    int ans=0;
    while(n){
        n=n&(n-1);
        ans++;
    }
    return ans;
}
vector countBits(int n) {
    vectordp(n+1);
    for(int i=0;i<=n;i++){
        dp[i]=help(i);
    }
    return dp;
}

//已知解是比当前整数少了最高有效位上的一个1
vector countBits(int n) {
    vector bits(n + 1);
    int highBit = 0;
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0) {
            highBit = i;
        }
        bits[i] = bits[i - highBit] + 1;
    }
    return bits;
}

//已知解比当前整数少了最低位上的一个数，要自己判断是0还是1
vector countBits(int n) {
    vector bits(n + 1);
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
}

//已知解比当前整数少了最低有效位（第一个出现1的位置）上的一个1
vector countBits(int n) {
    vector bits(n + 1);
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}