LeetCode 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)来执行此操作

开始的思路

先不考虑进阶, 使用语言自带的函数进行解答,Golang中可以使用bits.OnesCount()函数来计算

1
2
3
4
5
6
7
func countBits(num int) []int {
	nums := make([]int, num+1)
	for i := 0; i <= num; i++ {
		nums[i] = bits.OnesCount(uint(i))
	}
	return nums
}

这种解答十分简单,我们来尝试一下手写一个 OneCount()

leetcode 官方解答内提到有一个位运算的小技巧

对于任意整数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
// 8的二进制为 1000
// 7的二进制为 0111
// 我们进行 & 操作
1000 & 0111 = 0000 
// x 变成了 0 , 8的二进制数为1, 这符合我们的答案
// 让我们再来一个
// 6的二进制为 0110
// 5的二进制为 0101
// 4的二进制为 0100
// 3的二进制为 0011
0111 & 0110 = 0110 // ones + 1
0110 & 0101 = 0100 // ones + 1
0101 & 0100 = 0100 // ones + 1
0100 & 0011 = 0000 // ones = 3 
// 对此我只能发出咸鱼的声音,妙啊

对此技巧,我们可以写出:

1
2
3
4
5
6
func onesCount(x int) (ones int) {
	for ; x > 0; x &= x - 1 {
		ones++
	}
	return
}

但是这依然不满足进阶解答的需求,所以我们继续

进阶

要给出时间复杂度为 O(n) 的解法, 代表我们不能使用系统的内置函数, 且不能进入循环. 我们必须进行逻辑梳理

官方给出的解答: 动态规划–最高有效位 有些晦涩难懂

需要对每个数遍历其二进制表示的每一位。可以换一个思路,当计算 i 的「一比特数」时,如果存在 0 ≤ j < i,j 的「一比特数」已知,且 i 和 j 相比,i 的二进制表示只多了一个 1,则可以快速得到 i 的「一比特数」。

令 bits[i] 表示 i 的「一比特数」,则上述关系可以表示成:bits[i] = bits[j] + 1。

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

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

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

如果 i&(i−1)=0,则令 highBit = i,更新当前的最高有效位。

i 比 i−highBit 的「一比特数」多 1,由于是从小到大遍历每个数,因此遍历到 i 时,i−highBit 的「一比特数」已知,令 bits[i] = bits[i−highBit] + 1。

最终得到的数组 bits 即为答案。

作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

我这尝试做出自己的解释:

  • 当一个数是 2 的整数次幂时, 它的二进制中1的数量只会是1
  • 当一个数不是2的整数次幂时,它的二进制中1的数量为 (它 与 它上次为2的整数次幂的数的差值)的「一比特数」+ 1

我们可以来实际试试:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 8的二进制为 1000 它是2的整数次幂 所以它的二进制中1的数量只会是1
// 那 9 呢?根据上面的总结 它的上次2的整数次幂的数为 8,9-8=1(0001) 的「一比特数」为1
// 9 的二进制位是 1001 ,「一比特数」为 2, 完美
// 那 10 呢?它的上次2的整数次幂的数依然为 8, 10-8=2(0010) 的「一比特数」为1
// 10 的二进制位为 1010, 「一比特数」为 2
// 继续 11 二进制为 1011, 11-8=3 , 3(0011)的「一比特数」为2 
// 对此我只能发出咸鱼的声音,妙啊

// 所以我们能写出下面的方法
func countBits(num int) []int {
	bits := make([]int, num+1)
	highBit := 0 // 最高比特位 即 上次为2的整数次幂的数
  // 0的「一比特数」为 0,不需要进入循环
	for i := 1; i <= num; i++ {
		// 这里是根据上面的位运算的技巧,判断是否为2的整数次幂,因为2的整数次幂只有一个1
  	if i&(i-1) == 0 {
			highBit = i // 更新最高比特位
		}
		// 它与它上次为2的整数次幂的数的差值 的「一比特数」+ 1
		bits[i] = bits[i-highBit] + 1
	}
	return bits
}

应该还是有些晦涩难懂,但是我也没得办法,这太抽象了,官方解答的其他动态规划思想就不继续了,我们还有新办法。

新的办法

对于所有的数字,只有两类 奇数|偶数:

  1. 奇数: 在二进制中表示,奇数一定比前面的那个偶数多一个1,多的就是最低位的1

    举例:

    0 = 0000 1 = 0001

    2 = 0010 3 = 0011

    发现了没有,偶数的最低位总是0,奇数的最低位总是1,我们再考虑偶数

  2. 偶数: 二进制中,偶数中的1一定和除以2之后的那个数一样多,因为偶数的最低位总是0

    除以2就只是右移一位,把最低位的0去掉而已,所以1的数量是不变的

    举例:

    0 = 0000 1 = 0001 // 0不算, 1的「一比特数」= 0 + 1

    2 = 0010 3 = 0011 // 2 / 2 = 1, 1的「一比特数」= 1 …

    4 = 0100 5 = 0101

    6 = 0110 7 = 0111

我们能根据上面的规律来写出以下代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func countBits(num int) []int {
	nums := make([]int, num+1)
	for i := 1; i <= num; i++ {
    // 判断是否为偶数,奇数的最后一位永远是1
		if i&1 == 1 {
			nums[i] = nums[i-1] + 1
		} else {
			nums[i] = nums[i/2]
		}
	}
	return nums
}

以上思路来自:

作者:duadua 链接:https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/ 来源:力扣(LeetCode)