空間換時(shí)間的思路很妙

接前文，如何統(tǒng)計(jì)一個(gè)整數(shù)的二進(jìn)制數(shù)有多少個(gè) 1 ？

如果你問(wèn)這么無(wú)聊的問(wèn)題有意義嗎？那我猜測(cè)你一定不太喜歡數(shù)學(xué)。這類(lèi)問(wèn)題其實(shí)是對(duì)具體問(wèn)題的一種抽象，比如計(jì)算機(jī)只認(rèn)識(shí)二進(jìn)制的 0 和 1，這兩個(gè) 0 和 1 經(jīng)過(guò)運(yùn)算和轉(zhuǎn)換，卻能表達(dá)整個(gè)世界。你也許認(rèn)為人工智能非常高大上，而在我眼里，不過(guò)是 if、else、循環(huán)的組合罷了。因此不要忽視此類(lèi)看似沒(méi)有意義的問(wèn)題，仔細(xì)思考并試著回答，可以訓(xùn)練我們的計(jì)算機(jī)思維。

回到題目，大多數(shù)人最先想到的就是直接數(shù)一下有多少個(gè) 1，這個(gè)方法可以得到結(jié)果，但肯定不是最優(yōu)的，一個(gè)數(shù)有多少個(gè)二進(jìn)制位，就需要數(shù)多少次，一個(gè) 32 個(gè)二進(jìn)制的整數(shù)，就要數(shù) 32 次。

def?count_bit(num?:int)?->int?:
????count?=?0
????print(bin(num))
????while?num?>?0?:
????????if?num?&?1?==?1:?#說(shuō)明該位為?1
????????????count?+=?1
????????num?=?num?>>?1??#循環(huán)移動(dòng)
????return?count

稍微高明一些做法通常會(huì)是這樣：

熟悉二進(jìn)制的話(huà)就會(huì)知道，任何一個(gè)二進(jìn)制數(shù)都可以轉(zhuǎn)成 2 的 n 次方的和，這樣，一個(gè)二進(jìn)制數(shù)有 n 個(gè) 1 ，只需要判斷 n 次就知道有多少個(gè) 1 而不是全部位數(shù)都判斷一次。舉個(gè)例子：8 是 2 的 3 次方，那 8(0b1000) 就只有一個(gè) 1，而 7(0b0111) 是 2 的 2 次方 加上 2 的 1 次方 加上 2 的 0 次方，共加了 3 次，因此有 3 個(gè) 1，依次類(lèi)推。

二進(jìn)制數(shù)有個(gè)特點(diǎn)，可以將上述思路代碼化：a 與比它小 1 的數(shù) a - 1 進(jìn)行與(&) 運(yùn)算，可以將 a 最右邊的 1 變成 0，比如
5 = 0b101 ，4 = 0b100 ，5 & 4 = 0b101 & 0b100 = 0b100 = 4（相當(dāng)于 5 的二進(jìn)制數(shù)右邊的 1 變成了 0，計(jì)數(shù)一次）4 繼續(xù)循環(huán)，直到變成 0b00，共循環(huán)兩次，因此 5 有 2 個(gè) 1。

def?count_bit2(num?:int)?->int?:
????print(bin(num))
????count?=?0
????while?num:
????????num?=?num?&?num?-?1
????????count?+=?1
????return?count

更聰明的回答者可以將此問(wèn)題推廣到任意進(jìn)制數(shù)的判斷。

還有一個(gè)更簡(jiǎn)單高效的答案，就是查表法，利用空間換取時(shí)間。如果要統(tǒng)計(jì)一個(gè)數(shù)的二進(jìn)制數(shù)有多少個(gè) 1，直接先算好放在一張緩存表里，需要時(shí)直接去表里查就得到了結(jié)果，這樣的查詢(xún)時(shí)間復(fù)雜度為 O(1), 效率比上述第二種與算法的方式還要快。比如 cache = {103:5}，那么 直接 cache[103] 就得出結(jié)果 5，只需要查找一次。

但是問(wèn)題來(lái)了，一個(gè) 32 位的計(jì)算機(jī)可以表示的整數(shù)有 2 的 32 次方個(gè)，每個(gè)整數(shù)假如是 4 字節(jié)，如果要把這些數(shù)都存在表里，至少需要 16 GB的內(nèi)存空間，如果是 64 位，則需要的內(nèi)存不小于 67108864 TB，那么查表法是不是就不行了？

當(dāng)然不是，我們可以只保留 16 位整數(shù)的緩存表，只需要 256 KB左右的內(nèi)存空間，然后將 32 位或 64 位的整數(shù)拆成每 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

????##將一個(gè)數(shù)轉(zhuǎn)為字節(jié)數(shù)組
????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

假如不考慮內(nèi)存夠不夠用，使用 32 位的緩存表會(huì)比 16 位的快嗎？，從理論上上看，32 位的緩存表查詢(xún)次數(shù)更少，應(yīng)該更快，實(shí)際上，計(jì)算機(jī)的 cpu 和內(nèi)存之間還有一個(gè)高速緩存，高速緩存的空間非常小，通常只有幾兆，計(jì)算機(jī)往往需要把內(nèi)存先往高速緩存中搬運(yùn)，然后做相應(yīng)的處理，緩存太大，搬運(yùn)工作就做的越多，因此并不是緩存表越大越快。

下次分享：如何編碼檢查調(diào)度平臺(tái)上的作業(yè)依賴(lài)關(guān)系是否有循環(huán)依賴(lài)。