刷题笔记(3):力扣-338.比特位计数

本题来自 leetcode 题库第 338 题:338.比特位计数,要求计算 \(1\)\(n\) 中每个数字二进制表示法中 \(1\) 的个数,难度中等(官方难度简单)。使用位运算可以简化算法,但编码时要小心运算符的优先级问题。

题目描述

给你一个整数 \(n\) ,对于 \(0 \leqslant i \leqslant 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 \leqslant n \leqslant 10^5\)

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

题解

该题是计算某个整数 \(x\) 的二进制中 1 的个数(简称为“1 比特数”)。不知道这个具体的业务场景有哪些,但很多语言中内置了求 1 比特数的方法,比如 Java 的 Integer.bitCount,C++ 的 __builtin_popcount,Go 的 bits.OnesCount 等。

由于 \(n \leqslant 10^5\),最直接的思路便是遍历 \(1\)\(n\) 每个数字 \(i\),分别用求 \(i\) 的 1 比特数。对于每个 \(i\) 遍历每个数位计算 \(1\) 的个数(通过取余或转字符串等方法)。时间复杂度为 \(O(n\log n)\)

为了方便,本文中将 \(x\) 的“1 比特数”记作 \(\text{bits}(x)\)

解法 1:Brian Kernighan 算法

对于上述 \(O(n\log n)\) 复杂度的思路中,计数 \(i\)\(1\) 的个数可以使用 Brian Kernighan 算法。Brian Kernighan 算法的思想是:容易证得,对于数字 x,令 x = x & (x - 1) 将去掉 x 二进制表示中最末尾的 1。例如,x = 7x = 111,则 x & (x - 1) == 111 & 110 == 110

利用 Brian Kernighan 算法,对于每个 \(i\),不停的去掉末尾的 1,直到 \(i\) 变为 0,则循环次数即为 \(i\) 中原本含 1 的个数。使用该方法,可以减少循环次数。

综上思路,写出最终的代码;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
res = new Array(n + 1)
for (let i = 0; i < n + 1; i++) res[i] = bits(i)
function bits(x) {
j = 0
while (x > 0) {
x = x & (x - 1)
j++
}
return j
}
return res
}

解法 2:动态规划——最高有效位

该解法寻求 \(O(n)\) 的复杂度。考虑,当按顺序计算 \(i\) 的“1 比特数”时,我们假设 \(i\) 之前的“1比特数”均已知,若能通过某种方法找到 \(j < i\) 使得 \(j\) 的“1比特数”比 \(i\) 的小 \(1\)。那么便有 \(\text{bits}(i)=\text{bits}(j) + 1\)

那么“某种方法”如何得到呢?显然对于任何一个二进制整数,当去掉该数字最高有效位上的 \(1\) 时,该数字会减小,并且该数字的“1 比特数”会减少 \(1\) 个。例如,\(i = 1001\) 去掉最高位的数字 \(1\) 变成 \(0001\),记作 \(j\)(即 \(j = i - 1000\)),显然有 \(j<i\)\(\text{bits}(i) = \text{bits}(j) + 1\)。那么当要计算 \(\text{bits}(i)\) 时,只需找到 \(i\) 的最高有效位上为 \(1\) 其余数位为 \(0\) 的数,不妨记作 \(k\),那么 \(j\) 就等于 \(i - k\)。不难发现 \(k\) 就是不大于 \(i\) 的最大的 \(2\) 的整次幂。

整理一下,算法的思路为:先设置初值: ans[0]=0,然后遍历 \(1\)\(n\),每次遍历找到不大于当前数 \(i\)\(2\) 的最大整次幂 \(k\),便有 ans[i] = ans[i - k] + 1

\(k\) 值可以使用 Brian Kernighan 算法查找:根据 Brian Kernighan 算法可以知道,对于整数 x,当且仅当 x 仅最高位为 \(1\) 时有 x & (x - 1) == 0。所以在遍历的过程中每当 i & (i - 1) == 0 时便更新 k=i

说了这么多,其实代码很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
const res = new Array(n + 1)
res[0] = 0
k = 1
for (let i = 1; i < n + 1; i++) {
if ((i & i - 1) === 0) k = i // 注意运算符的优先级
res[i] = res[i - k] + 1
}
return res
};

该算法时间复杂度为 \(O(n)\),空间复杂度为 \(O(1)\)

解法 3:动态规划——最低有效位

该方法也是 \(O(n)\) 的算法。所以主要的思想和解法 3 一致,都是通过寻找当前迭代数字 \(i\) 和某些特殊的 \(j < i\) 之间的固定的“1 比特数”差值来降低事件复杂度的。

不同于将最高有效位置 \(0\) 来将 \(i\) 变小,该方法使用右移位运算来将 \(i\) 变小。例如 \(i = 1001\),则令 j = i >> 1,使得 \(j=100 < i\)。我们发现 \(\text{bits}(i)\)\(\text{bits}(j)\) 之间的差值即为 \(i\) 的最后一位数字(\(0\)\(1\))。\(i\) 的最后一位数字容易得到为 i % 2,或使用位运算符为 i & 1

写出代码实现为:

1
2
3
4
5
6
7
8
9
10
11
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
const res = new Array(n + 1)
res[0] = 0
for (let i = 1; i < n + 1; i++)
res[i] = res[i >> 1] + (i & 1)
return res
}

解法 4:动态规划——最低设置位

该算法的核心思路与解法 2、3 一致。

定义正整数 \(x\) 的「最低设置位」为 \(x\) 的二进制表示中的最低的 \(1\) 所在位。

在我理解,该算法也是将 \(i\) 变小,变小的方式则为将最低设置位置 \(0\)。显然,此时变小后的数与 \(i\) 的“1比特数”相差 \(1\)(就差在最低设置位上)。将最低设置位置 \(0\) 依然是用到 Brian Kernighan 算法。那么便有 \(\text{bits}(i) = \text{bits}(j) + 1\),其中 j = i & i - 1

代码实现如下:

1

总结与思考

这题虽然简单,但要写出 \(O(n)\) 还是有一定难度。我一开始写了几个小时才写出一个 \(O(n)\) 的算法,主要的思路就是找规律,但那个规律找得不是太好,所以写起来有点啰嗦,要处理的细节比较多,这里就不再贴了。

官方给出了四种解法,第一个中介绍了 Brian Kernighan 算法,可提高效率。后面三种解法在我看来核心思想都是一样的,那便是利用已知的 \(\text{bits}(j)\) 来快速计算 \(\text{bits}(i)\)。那么此时 \(j\) 的选取就是关键了。首先 \(j\) 一定比 \(i\) 小(某些情况等于也可),这三种算法分别通过使最高有效位为 \(0\)、右移一位、使最低设置位为 \(0\) 来减小 \(i\)。然后通过观察变小后得到的 \(j\) 的“1比特数” \(\text{bits}(j)\)\(\text{bits}(i)\) 的差值来计算 \(\text{bits}(i)\)

这道题学到很多细节和知识:

  1. 二进制数的计算可以通过位运算来替代,例如
    • Brian Kernighan 算法,将最后一位 \(1\)\(0\)x & (x - 1)
    • 除 2 取余(取最后一位):x & 1
    • \(2^n\)x << n
    • \(2^n\) 并取整:x >> n
  2. 注意位运算符的优先级,在大多数语言中是最低的