比特位计数

题目描述

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例1：

1 2	输入: 2 输出: [0,1,1]

示例2：

1 2	输入: 5 输出: [0,1,1,2,1,2]

进阶:

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

题解

前言

这道题需要计算从 0 到 num 的每个数的二进制表示中的 1 的数目。最直观的方法是对每个数直接计算二进制表示中的 1 的数目，时间复杂度较高。也可以使用动态规划的方法，时间复杂度较低。

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

法一：直接计算

最直观的方法是对从 0 到 num 的每个数直接计算「一比特数」。

每个 int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。

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

代码如下：

class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }

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

复杂度分析

时间复杂度：$O(k×num)$，其中 k 是 int 型的二进制位数，k=32。需要对从 0 到 num 的每个数使用 $O(k)$ 的时间计算「一比特数」，因此时间复杂度是 $O(k×num)$。

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

法二：分奇偶，找规律

如果我们熟悉二进制，就会知道，偶数的二进制最后一位是0，奇数的二进制最后一位是1。

且当奇数比偶数大1时，奇数的「一比特数」也会比偶数大1；偶数右移一位相当于除以2，「一比特数」不变。

即我们有：

如果 x 是偶数，则 $bits[x] = bits[x/2]$
如果 x 是奇数，则 $bits[x] = bits[x-1] + 1 = bits[\lfloor x/2 \rfloor] + 1$

基于此，我们有如下代码：

public class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            bits[i] = i % 2 == 0 ? bits[i >> 1] : bits[i - 1] + 1;
        }
        return bits;
    }
}

上述两种情况可以合并成：$bits[x]=bits[x>>1]+(x & 1)$

所以代码可以简化为：

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

复杂度分析

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

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

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

当计算 $i$ 的「一比特数」时，如果存在 $0 \le j<i$，$j$ 的「一比特数」已知，且 $i$ 和 $j$ 相比，$i$ 的二进制表示只多了一个 1，则可以快速得到 $ i $ 的「一比特数」。

令 $\textit{bits}[i]$ 表示 $i$ 的「一比特数」，则上述关系可以表示成：$\textit{bits}[i]= \textit{bits}[j]+1$。

对于正整数 $x$，如果可以知道最大的正整数 $y$，使得 $y \le x$ 且 $y$ 是 $2$ 的整数次幂，则 $y$ 的二进制表示中只有最高位是 1，其余都是 0，此时称 $y$ 为 $x$ 的「最高有效位」。令 $z=x-y$，显然 $0 \le z<x$，则 $\textit{bits}[x]=\textit{bits}[z]+1$。

为了判断一个正整数是不是 $2$ 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 $y$ 是 $2$ 的整数次幂，则 $y$ 的二进制表示中只有最高位是 1，其余都是 0，因此 $y &(y-1)=0$。

由此可见，正整数 $y$ 是 $2$ 的整数次幂，当且仅当 $y &(y-1)=0$。

显然，0 的「一比特数」为 0。使用 $\textit{highBit}$ 表示当前的最高有效位，遍历从 1 到 $\textit{num}$ 的每个正整数 $i$，进行如下操作。

如果 $i &(i-1)=0$，则令 $\textit{highBit}=i$，更新当前的最高有效位。
$i$ 比 $i-\textit{highBit}$ 的「一比特数」多 1，由于是从小到大遍历每个数，因此遍历到 $i$ 时，$i-\textit{highBit}$ 的「一比特数」已知，令 $\textit{bits}[i]=\textit{bits}[i-\textit{highBit}]+1$。

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

代码：

class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        int highBit = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}

复杂度分析

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

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

动态规划——最低设置位

定义正整数 $x$ 的「最低设置位」为 $x$ 的二进制表示中的最低的 1 所在位。例如，10 的二进制表示是 $1010_{(2)}$，其最低设置位为 2，对应的二进制表示是 $10_{(2)}$。

令 $y=x &(x-1)$，则 $y$ 为将 $x$ 的最低设置位从 1 变成 0 之后的数，显然 $0 \le y<x$，$\textit{bits}[x]=\textit{bits}[y]+1$。因此对任意正整数 $x$，都有 $\textit{bits}[x]=\textit{bits}[x &(x-1)]+1$。

遍历从 1 到 $\textit{num}$ 的每个正整数 $i$，计算 $\textit{bits}$ 的值。最终得到的数组 $\textit{bits} $即为答案。

代码：

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

复杂度分析

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

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

参考

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/