比特位计数

题目链接:leetcode 338

题目描述

给定一个非负整数 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 的「一比特数」。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$

基于此,我们有如下代码:

1
2
3
4
5
6
7
8
9
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)$

所以代码可以简化为:

1
2
3
4
5
6
7
8
9
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}$ 即为答案。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
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} $即为答案。

代码:

1
2
3
4
5
6
7
8
9
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/

坚持原创技术分享,感谢您的支持和鼓励!