空间换时间的思路很妙
共 2282字，需浏览 5分钟
·
2020-08-21 12:52
接前文，如何统计一个整数的二进制数有多少个 1 ？
如果你问这么无聊的问题有意义吗？那我猜测你一定不太喜欢数学。这类问题其实是对具体问题的一种抽象，比如计算机只认识二进制的 0 和 1，这两个 0 和 1 经过运算和转换，却能表达整个世界。你也许认为人工智能非常高大上，而在我眼里，不过是 if、else、循环的组合罢了。因此不要忽视此类看似没有意义的问题，仔细思考并试着回答，可以训练我们的计算机思维。
回到题目，大多数人最先想到的就是直接数一下有多少个 1，这个方法可以得到结果，但肯定不是最优的，一个数有多少个二进制位，就需要数多少次，一个 32 个二进制的整数，就要数 32 次。
def count_bit(num :int) ->int :
count = 0
print(bin(num))
while num > 0 :
if num & 1 == 1: #说明该位为 1
count += 1
num = num >> 1 #循环移动
return count
稍微高明一些做法通常会是这样：
熟悉二进制的话就会知道，任何一个二进制数都可以转成 2 的 n 次方的和，这样，一个二进制数有 n 个 1 ，只需要判断 n 次就知道有多少个 1 而不是全部位数都判断一次。举个例子：8 是 2 的 3 次方，那 8(0b1000) 就只有一个 1，而 7(0b0111) 是 2 的 2 次方 加上 2 的 1 次方 加上 2 的 0 次方，共加了 3 次，因此有 3 个 1，依次类推。
二进制数有个特点，可以将上述思路代码化：a 与比它小 1 的数 a - 1 进行与(&) 运算，可以将 a 最右边的 1 变成 0，比如
5 = 0b101 ，4 = 0b100 ，5 & 4 = 0b101 & 0b100 = 0b100 = 4（相当于 5 的二进制数右边的 1 变成了 0，计数一次）4 继续循环，直到变成 0b00，共循环两次，因此 5 有 2 个 1。
def count_bit2(num :int) ->int :
print(bin(num))
count = 0
while num:
num = num & num - 1
count += 1
return count
更聪明的回答者可以将此问题推广到任意进制数的判断。
还有一个更简单高效的答案，就是查表法，利用空间换取时间。如果要统计一个数的二进制数有多少个 1，直接先算好放在一张缓存表里，需要时直接去表里查就得到了结果，这样的查询时间复杂度为 O(1), 效率比上述第二种与算法的方式还要快。比如 cache = {103:5}，那么 直接 cache[103] 就得出结果 5，只需要查找一次。
但是问题来了，一个 32 位的计算机可以表示的整数有 2 的 32 次方个，每个整数假如是 4 字节，如果要把这些数都存在表里，至少需要 16 GB的内存空间，如果是 64 位，则需要的内存不小于 67108864 TB，那么查表法是不是就不行了？
当然不是，我们可以只保留 16 位整数的缓存表，只需要 256 KB左右的内存空间，然后将 32 位或 64 位的整数拆成每 16 位一组，这样 32 位的只需要查 2 次，64 位的只需要查 4 次。甚至可以只保留 8 位的，这样 32 位的只需要查 4 次，64 位的只需要查 8 次。代码如下：
def count_bit3(num: int, bit_type: str = "32") -> int:
print(bin(num))
##初始化缓存表
cache_16 = [0] * 256
for i in range(256):
cache_16[i]=(i & 1) + cache_16[i // 2]
count = 0
##将一个数转为字节数组
byte_nums = []
if bit_type == "32":
byte_nums = [num >> i & 0xFF for i in (24, 16, 8, 0)]
elif bit_type == "64":
byte_nums = [num >> i & 0xFF for i in (56, 48, 40, 32, 24, 16, 8, 0)]
for byte in byte_nums:
count += cache_16[byte]
return count
假如不考虑内存够不够用，使用 32 位的缓存表会比 16 位的快吗？，从理论上上看，32 位的缓存表查询次数更少，应该更快，实际上，计算机的 cpu 和内存之间还有一个高速缓存，高速缓存的空间非常小，通常只有几兆，计算机往往需要把内存先往高速缓存中搬运，然后做相应的处理，缓存太大，搬运工作就做的越多，因此并不是缓存表越大越快。
下次分享：如何编码检查调度平台上的作业依赖关系是否有循环依赖。