题目描述

解题思路

Brian Kernighan 算法

核心思想就是使用 n&(n-1) 将最低位的1变为0，直到n等于0时停止，记录操作的次数，例如10001，相与一次之后就为10000，在相与一次就为00000，一共操作了2次，所以一共2个1。

// Brian Kernighan 算法
// 对于任意整数 x，令 x=x~\&~(x-1)x=x & (x−1)，
// 该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        bits[i] = countOnes(i);
    }
    return bits;
}
public int countOnes(int x) {
    int count = 0;
    while (x != 0) {
        x &= (x - 1);
        count++;
    }
    return count;
}

动态规划——最高有效位

• 如果 i & (i−1)=0，则令 highBit=i，更新当前的最高有效位。（高位必须为2的n次幂，通过 i & (i−1)=0可以得出是否是）
• i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个整数，因此遍历到 i 时，i−highBit 的「一比特数」已知，令bits[i]=bits[i−highBit]+1。（此时后面的+1是高位的1）

例如：bits[10001] = bits[1] + 1，bits[10011] = bits[11] + 1

// 动态规划——最高有效位
public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    int highBit = 0;   // 表示最高位
    for (int i = 1; i <= n; i++) {
        // 判断是否是2的幂
        if ((i & (i - 1)) == 0) {
            highBit = i;
        }
        bits[i] = bits[i - highBit] + 1;
    }
    return bits;
}

动态规划——最低有效位

最低有效位也就是通常的移位操作。
当向右移动一位之后，此时数字x变为x / 2，如果：

• x为奇数：此时bits[x]=bits[x/2]+1
• x为偶数：此时bits[x]=bits[x/2]

也就是统计最后一位的次数。所以可以写为bits[x]=bits[x/2]+x&1。

// 动态规划——最低有效位
public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        bits[i] = bits[i >> 1] + i % 2;
    }
    return bits;
}

动态规划——最低设置位

通过第一个解法可以知道n&(n-1)可以将最低为的1变为0，所以此时bits[n]=bits[n&(n-1)]+1，因为此时只有最后一位1变为0，例如1010就等于1000的1的个数加一。

// 方法四：动态规划——最低设置位
public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}