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）