LeetCode338.比特位数（C++）

题目描述：给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

题解思路：
（方法一）如下图：

class Solution{
public:
    int countOnes(int x)
    {
        int ones=0;
        while(x>0)
        {
            x=x&(x-1);
            ones++;
        }
        return ones;
    }
    vector countBits(int n)
    {
        vector bits(n+1);
        for(int i=0;i<=n;i++)
        {
            bits[i]=countOnes(i);
        }
        return bits;
    }
};

方法二（动态规划–最高有效位）：
题解思路：
1.当计算 i 的「一比特数」时，如果存在 0≤j

2.为了判断一个正整数是不是 2 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0（例如2的二进制位只有一个1,4也只有最高位为1,8…），因此 y & (y−1)=0。由此可见，正整数 y 是 2 的整数次幂，当且仅当 y & (y−1)=0。
当知道j的比特数时，并且j的比特数不止比i大1的时候（例如十进制位6与前一个最高有效位4相比，即：bits[6]=bits[6-4]+1=2），使用 highBit表示当前的最高有效位，遍历从 1 到 n 的每个正整数 i即可(因为如果求当前正在遍历的数的比特位的时候，一定可以用前边之前已经遍历或者已经知道的数的二进制位中1的个数+1，即前边举的6和4的例子)。

class Solution{
public:
    // int countones(int x)
    // {
    //     int ones=0;
    //     while(x>0)
    //     {
    //         x=x&(x-1);
    //         ones++;
    //     }
    //     return ones;
    // }
    // vector countBits(int n)
    // {
    //     vector bits(n+1);
    //     for(int i=0;i<=n;i++)
    //     {
    //         bits[i]=countones(i);
    //     }
    //     return bits;
    // }
    vector countBits(int n)
    {
        vector bits(n+1);
        bits[0]=0;
        int hignBit=0;
        for(int i=1;i<=n;i++)
        {
            if((i&(i-1))==0)
            {
                hignBit=i;
            }
            bits[i]=bits[i-hignBit]+1;
        }
        return bits;
    }
};