什麼是在C＃中的UInt32中計數設置位的最快方法？

Question

在不使用查找表的情況下，在UInt32中計數設置位數（即計數1的次數）的最快方法是什麼？有沒有一種方法可以計算O（1）？

Answer 1

bit-twiddling hacks頁面有許多選項。

當然，你可能會說，遍歷所有32位可能爲O（N），在每一次:)

爲了簡單，它是同樣的成本，我會考慮的查找表，per-字節的方法，或迭代，因爲有位設置很多次，我想作爲寫布賴恩Kernighan的整潔的想法：

public static int CountBits(uint value) 
{ 
    int count = 0; 
    while (value != 0) 
    { 
     count++; 
     value &= value - 1; 
    } 
    return count; 
} 

如果你不喜歡填充256條目查找表的想法，每查找一個nybble仍然會很快。請注意，有可能8個數組查找可能比32個簡單位操作慢。

當然，在進入特別深奧的方法之前，測試應用程序的真實性能是值得的...這對你來說真的是一個瓶頸嗎？

Answer 2

是一個重複： how-to-implement-bitcount-using-only-bitwise-operators 或 best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

而且有對這個問題許多解決方案。我使用的是：

int NumberOfSetBits(int i) 
    { 
     i = i - ((i >> 1) & 0x55555555); 
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333); 
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 
    }