計算整數中1的個數的最有效方法是什麼？

Question

可能重複：
Best algorithm to count the number of set bits in a 32-bit integer?

給出一個32位無符號整數，我們希望計算其二進制表示非零位的數量。什麼是最快的方法呢？

我們要做這個N〜10^10次。

注意：由於當前cpu的架構，使用大型查找表通常不是一個好主意。本地計算速度比使用需要查看外部存儲器的巨大陣列要快得多

Answer 1

實際上有幾個選項，我認爲本地方式對於這種方式太慢了。

您可以使用查找表獲取8位值，並對來自無符號整型值的所有四個字節並行執行，然後求和結果。這其中也可以有很好的平衡性（無論是多核心，還是甚至有些SSE3/4都可以提供幫助）。

你也可以去和Brian Kernighan的解決方案：

unsigned int v;    // count the number of bits set in v 
unsigned int c;    // c accumulates the total bits set in v 
for (c = 0; v; c++) 
{ 
    v &= v - 1;    // clear the least significant bit set 
} 

而且最後可能的方法，我在什麼地方找到前段時間（在64位機器上，因爲模運算將是非常快有）：

unsigned int v;  // count the number of bits set in v 
unsigned int c;  // c accumulates the total bits set in v 

c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;