比特位计数

[xiwenAndlejian]

338. 比特位计数

题目

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

示例 1:

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

示例 2:

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

进阶:

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

标签：位运算、动态规划

解答

方法一：循环

参考位1的个数，可以对[0, num]范围内的整数依次进行求位1的数

代码

public int[] countBits(int num) {
    int[] counts = new int[num + 1];
    for (int i = 1; i <= num; i++) {
        // 代码参考 位1的个数
        counts[i] = hammingWeight(i);
    }
    return counts;
}

方法二：动态规划

假设函数：对于数x，位1的个数为 f(x)

那么需要的结果可以写为：[f(0), f(1), ... , f(num-1), f(num)]

动态规划需要的找寻的条件：

• f(x)与f(x-1)的关系
• 边界条件

边界条件很容易就可以得到：f(0) = 0、f(1) = 1

而f(x)与f(x-1)的关系如何分析？

由于是求位1的个数，那么从二进制角度分析x-1与x的关系，推导可得下图：

:memo:：对于图中示例中的X表示数位上1或0均可。

如图所示的示例中：

1. 不发生进位的情况下，仅有末尾0变为1，公共部分XXXX_XXX0不变，即为公共部分中位1的个数再加一即可得f(x)的结果，而公共部分实际上又是x-1的二进制表达式。

   那么可以推导在不发生进位的情况下f(x) = f(x-1) + 1

2. 发生部分进位的情况下，参考上述推论，x与x-1在二进制表达式的公共部分为XXXX_0110=x & x-1。可得f(x) = f(x & x-1) + 1。

3. 发生全部进位的情况下，公共部分为0000_0000=x & (x-1)。可得f(x) = f(x & x-1) + 1

而不发生进位的情况下，公共部分=x & (x-1)=x-1。

因此可以得出f(x)与f(x-1)的关系：f(x) = f(x & x-1) + 1

代码

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

优点：相比方法一，方法二利用了上一步计算的值（f(x-1)）使得计算量大大降低。