leetcode：338. 比特位计数

题目

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

示例：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

进阶：

• 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 **O(n)** 内用一趟扫描解决此问题吗？
• 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

解答 & 代码

解法一：x = x & (x-1)

Brian Kernighan 算法：对于任意整数 x，令 x = x & (x-1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。

遍历 0~n，对每个 n 利用 Brian Kernighan 算法求一比特数即可

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> result(n + 1);
        for(int i = 0; i <= n; ++i)
        {
            int num = i;    // 当前整数
            int cnt = 0;    // 一比特数
            // 令 num = num & (num - 1)，直到 num 变为 0，该操作的次数就是 num 的一比特数
            while(num != 0)
            {
                ++cnt;
                num &= num - 1;
            }
            result[i] = cnt;
        }
        return result;
    }
};

复杂度分析：

• 时间复杂度 O(n logn)：对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)
  • 对于整数 n， 其二进制表示的比特位数 = + 1，最坏情况下，每一位都是 1，就需要循环计算 + 1 次，因此计算其一比特数的时间复杂度 O(logn)
• 空间复杂度 O(1)：结果数组 result 不计

执行结果：

执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 84.77% 的用户
内存消耗：7.6 MB, 在所有 C++ 提交中击败了 81.67% 的用户

解法二：动态规划 + x & (x-1)

动态规划：

• 动态规划数组 **result**：result[i] 代表整数 i 的一比特数（二进制表示中 1 的个数）
• 状态转移方程：result[i] = 1 + result[i & i - 1]
  • 令 j = i & (i - 1)，整数 j 是将整数 i 的二进制表示的最后一个 1 变成 0，因此 j 肯定小于 i，j 的一比特数 result[i] 已经计算得到，因此 result[i] = 1 + result[j]

• 初始化：result[0] = 0

  class Solution {
  public:
    vector<int> countBits(int n) {
        vector<int> result(n + 1);    // 动态规划数组，result[i] 代表整数 i 的一比特数
        result[0] = 0;                // 初始化
        // 状态转移
        for(int i = 1; i <= n; ++i)
            result[i] = 1 + result[i & i - 1];
        return result;
    }
  };

  复杂度分析：

• 时间复杂度 O(n)：一趟遍历即可，对于每个整数，只需 O(1) 的时间计算一比特数

• 空间复杂度 O(1)：结果数组 result 不计

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：7.8 MB, 在所有 C++ 提交中击败了 35.97% 的用户