【刷题日记】前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 <= 105

进阶:

• 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
• 要求算法的空间复杂度为O(n)。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。

题目链接

遍历每个整数的每一位计算 [ 一比特数 ]

Brian Kernighan 算法：

• 使用 x & (x - 1) 可以将 x 最后一个为1的位变为0
• 对 x 重复此操作直到 x为0，操作的重复次数就是 x 的1的个数

对每个整数计算 [ 一比特数 ] 的时间复杂度不超过 O(logn)

时间复杂度：O(nlogn)

空间复杂度：O(1)

class Solution {
public:
    int countOnes(int x) {
        int ans = 0;
        while(x > 0) {
            x = x & (x-1);
            ans ++;
        }
        return ans;
    }

    vector countBits(int n) {
        vector v(n+1);
        for(int i = 1;i <= n;i ++ ) {
            v[i] = countOnes(i);
        }
        return v;
    }
};

动态规划：使用已知的递推计算未知的

最高有效位： 对于x ，已知最大的正整数 y 是2的整数幂次，并且 y<=x，则 y 只有最高位为1，其余都为0，则称 y 为 x 的最高有效位。 （距离x最近的2的幂次数）

则若 z = x - y ， 则 bits[x] = bits[z] + 1 (+1即为减去的最高有效位的那个1)

例：

x = 10 : 1010

最高有效位 y = 8 : 1000

z = x - y = 1010 - 1000 = 0010

bits[10] = bits[2] + 1 = 2

判断2的整数幂：x & (x-1) = 0

1. 遍历1~n，当 x & (x-1) == 0 时，记录更新最高有效位 highbit O(n)
2. 对每个遍历的 x ，都计算其 [ 一比特数 ] ，bits[x] = bits[x - highbit] + 1 O(1)

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    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;
    }
};

注：运算符的优先级：等于 == 的优先级高于 逻辑运算符 &

例:

int x = 2;
cout << (x & (x - 1) == 0) << endl;
cout << ((x & (x - 1)) == 0) << endl;

输出：

0  // 1.计算x-1=1  2.比较(x-1)==0 结果为0  3.计算x & 0 = 0
1  // 1.计算x-1=1  2.计算x & (x-1) 结果为0  3.比较 0 == 0 结果为true，即1

最高有效位的动态规划需要实时维护最高有效位

最低有效位：通过右移x ，去除x的最低位，从而从已经计算出的数 bits[x >> 1] 得到 bits[x]

• 最低位为0，偶数，bits[x] = bits[x >> 1]
• 最低位为1，奇数，bits[x] = bits[x >> 1] +1

合并为： bits[x] = bits[x >> 1] + (x % 2) = bits[x >> 1] + (x & 1)

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    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的所在位

例：1010 最低设置位为2

思路一中Brian Kernighan 思想使用 x & (x-1) 逐位将最低设置位的1变为0，则使用一次 x & (x-1) 将最低设置位由1变0，即减少1个1，因此：

bits[x] = bits[x & (x-1)] + 1

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