题目

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

示例 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 的数目，例如 的 ， 的 ， 的 等，读者可以自行尝试。下列各种方法均为不使用内置函数的解法。

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

方法一：Brian Kernighan 算法

思路及解法

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

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

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

代码

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var bits: [Int] = []
        for i in 0...n {
            var x = i
            bits.append(countOnes(&x))
        }
        return bits
    }
    
    func countOnes(_ x: inout Int) -> Int {
        var ones: Int = 0
        while x > 0 {
            x &= (x - 1)
            ones += 1
        }
        return ones
    }
}

复杂度分析

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

• 空间复杂度：。除了返回的数组以外，空间复杂度为常数。

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

思路及解法

方法一需要对每个整数使用 的时间计算「一比特数」。可以换一个思路，当计算 的「一比特数」时，如果存在 ， 的「一比特数」已知，且 和 相比， 的二进制表示只多了一个 ，则可以快速得到 的「一比特数」。

令 表示 的「一比特数」，则上述关系可以表示成：。

对于正整数 ，如果可以知道最大的正整数 ，使得 且 是 的整数次幂，则 的二进制表示中只有最高位是 ，其余都是 ，此时称 为 的「最高有效位」。令 ，显然 ，则 。

为了判断一个正整数是不是 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 是 的整数次幂，则 的二进制表示中只有最高位是 ，其余都是 ，因此 。由此可见，正整数 是 的整数次幂，当且仅当 。

显然， 的「一比特数」为 。使用 表示当前的最高有效位，遍历从 到 的每个正整数 ，进行如下操作。

• 如果 ，则令 ，更新当前的最高有效位。

• 比 的「一比特数」多 ，由于是从小到大遍历每个整数，因此遍历到 时， 的「一比特数」已知，令 。

最终得到的数组 即为答案。

代码

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var bits: [Int] = Array.init(repeating: 0, count: n + 1)
        var highBit: Int = 0
        var i = 1
        while i <= n {
            if (i & (i - 1)) == 0 {
                highBit = i
            }
            bits[i] = bits[i - highBit] + 1
            i += 1
        }
        return bits
    }
}

复杂度分析

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

• 空间复杂度：。除了返回的数组以外，空间复杂度为常数。