携手创造，一起成长！这是我参与「日新计划 8 月更文应战」的第35天，点击查看活动详情

标题

给你一个整数 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 的数目，例如 $\text{Java}$ 的 $\text{Integer.bitCount}$，$\text{C++}$ 的 \texttt{__builtin_popcount}，$\text{Go}$ 的 $\text{bits.OnesCount}$ 等，读者能够自行测验。下列各种办法均为不运用内置函数的解法。

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

办法一：Brian Kernighan 算法

思路及解法

最直观的做法是对从 $0$ 到 $n$ 的每个整数直接核算「一比特数」。每个 $\text{int}$ 型的数都能够用 $32$ 位二进制数表明，只需遍历其二进制表明的每一位即可得到 $1$ 的数目。

利用 $\text{BrianKernighan}$ 算法，能够在一定程度进步一步提升核算速度。$\text{BrianKernighan}$ 算法的原理是：关于任意整数 $x$，令 $x=x\&(x-1)$，该运算将 $x$ 的二进制表明的最后一个 $1$ 变成 $0$。因而，对 $x$ 重复该操作，直到 $x$ 变成 $0$，则操作次数即为 $x$ 的「一比特数」。

关于给定的 $n$，核算从 $0$ 到 $n$ 的每个整数的「一比特数」的时刻都不会超越 $O(\log n)$，因而总时刻复杂度为 $O(n\log n)$。

代码

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
    }
}

复杂度剖析

• 时刻复杂度：$O(n\log n)$。需求对从 $0$ 到 $n$ 的每个整数运用核算「一比特数」，关于每个整数核算「一比特数」的时刻都不会超越 $O(\log n)$。

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

办法二：动态规划——最高有用位

思路及解法

办法一需求对每个整数运用 $O(\log n)$ 的时刻核算「一比特数」。能够换一个思路，当核算 $i$ 的「一比特数」时，假如存在 $0\le j<i$，$j$ 的「一比特数」已知，且 $i$ 和 $j$ 相比，$i$ 的二进制表明只多了一个 $1$，则能够快速得到 $i$ 的「一比特数」。

令 $\text{bits}[i]$ 表明 $i$ 的「一比特数」，则上述关系能够表明成：$\text{bits}[i]=\text{bits}[j]+1$。

关于正整数 $x$，假如能够知道最大的正整数 $y$，使得 $y\le x$ 且 $y$ 是 $2$ 的整数次幂，则 $y$ 的二进制表明中只要最高位是 $1$，其他都是 $0$，此时称 $y$ 为 $x$ 的「最高有用位」。令 $z=x-y$，明显 $0\le z<x$，则 $\text{bits}[x]=\text{bits}[z]+1$。

为了判断一个正整数是不是 $2$ 的整数次幂，能够利用办法一中提到的按位与运算的性质。假如正整数 $y$ 是 $2$ 的整数次幂，则 $y$ 的二进制表明中只要最高位是 $1$，其他都是 $0$，因而 $y\&(y-1)=0$。由此可见，正整数 $y$ 是 $2$ 的整数次幂，当且仅当 $y\&(y-1)=0$。

明显，$0$ 的「一比特数」为 $0$。运用 $\text{highBit}$ 表明当时的最高有用位，遍历从 $1$ 到 $n$ 的每个正整数 $i$，进行如下操作。

• 假如 $i\&(i-1)=0$，则令 $\text{highBit}=i$，更新当时的最高有用位。

• $i$ 比 $i-\text{highBit}$ 的「一比特数」多 $1$，由于是从小到大遍历每个整数，因而遍历到 $i$ 时，$i-\text{highBit}$ 的「一比特数」已知，令 $\text{bits}[i]=\text{bits}[i-\text{highBit}]+1$。

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

代码

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
    }
}

复杂度剖析

• 时刻复杂度：$O(n)$。关于每个整数，只需求 $O(1)$ 的时刻核算「一比特数」。

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