計算 64 bit long 內有幾個 bit 為 1 的速算法

原本在讀 bit array 為啥威, 結果看到 Hamming weight, 即計算一個 "string" 內有幾個 1 的速算法。

基本版 (popcount_1) 的想法還算好懂, 典型的 divide & conquer, 對半切的解法, 看了開頭就猜到後面要怎麼做了。先以 2 bit 為單位算出有幾個 1, 並存在原本的那 2 bit 裡, 再用同樣的手法以 4 bit 為單位算出 4 bit 裡有幾個 1, 並存在原本的那 4 bit 裡, ..., 最後就會在較低的 32 bit 裡得到全部答案。

進階版 (popcount_2) 的第一個寫法有點妙, 我最後才參透它。8、16、32 bit 時最簡單, 若 bit 數的最大值不會超出儲存的空間, 就不用擔心相加會溢位, 而能直接位移並做相加。2 bit 的作法沒變, 4 bit 的作法和 8 bit 開始的作法一樣, 只是先清乾淨「高位元」的地方, 確保後面處理 8、16、32 bit 時不會溢位。

回頭看 x -= (x >> 1) & m1, 將式子展開會得到 x = x - ((x >> 1) & m1)。而原本的算法是 (x & m1) + ((x >> 1) & m1), 將兩式合起來看會得到:

x - ((x >> 1) & m1) = (x & m1) + ((x >> 1) & m1)
x - (x & m1) = ((x >> 1) & m1) + ((x >> 1) & m1)

整理左式:

x - (x & m1) = x & (m1 << 1)

整理右式

((x >> 1) & m1) + ((x >> 1) & m1)
= 2 * ((x >> 1) & m1) 
= ((x >> 1) & m1) << 1
= x & (m1 << 1)

所以這個算法沒錯, 將上面的過程反過來推導, 就會發覺可以用 x - ((x >> 1) & m1) 取代原本的式子以省下一個運算。

H = (x >> 1) & m1
L = x & m1
H + L 
= H + H - H + L
= 2H - H + L 
= (x - L) - H + L
= x - H
= x - (x >> 1) & m1

位元運算的世界真是太奇妙了, 後面的更進階版有機會再來參透吧。