1059-前 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 的每个整数的二进制表示中的 1 的数目。

部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 1 的数目，例如 Java 的Integer.bitCount，C++ 的 __builtin_popcount，Go 的 bits.OnesCount 等，读者可以自行尝试。下列各种方法均为不使用内置函数的解法。

为了表述简洁，下文用「一比特数」表示二进制表示中的 1 的数目。

解题思路1

方法一：Brian Kernighan 算法
最直观的做法是对从 0 到 n 的每个整数直接计算「一比特数」。每个 int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。

利用 Brian Kernighan 算法，可以在一定程度上进一步提升计算速度。Brian Kernighan 算法的原理是：对于任意整数 x，令x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。

对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)。

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

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

复杂度分析

时间复杂度：O(nlogn)。需要对从 0 到 n 的每个整数使用计算「一比特数」，对于每个整数计算「一比特数」的时间都不会超过 O(logn)。

空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

方法二：动态规划——最高有效位

最终得到的数组 \textit{bits}bits 即为答案。

class Solution
{
public:
    vector<int> countBits(int n) 
    {
        vector<int> 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;
    }
};

复杂度分析

时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。

空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

方法三：动态规划——最低有效位

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

复杂度分析

时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。

空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。