c# - UInt32でセットビットをカウントする最速の方法は何ですか?

Question

UInt32ルックアップ テーブルを使用せずに、セットされたビットの数をカウントする (つまり、1 の数をカウントする) 最速の方法は何ですか? でカウントする方法はありO(1)ますか？

Answer 1

ちょっとしたハックのページには、いくつかのオプションがあります。

もちろん、32 の可能なビットすべてを反復することは、毎回同じコストであるという点で O(N) であると主張することができます:)

簡単にするために、バイトごとのルックアップテーブルアプローチ、またはビットが設定されている回数だけ反復するブライアン・カーニハンのすてきなアイデアを検討します。これは次のように記述します。

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

256 エントリのルックアップ テーブルを作成するという考えが気に入らない場合でも、ルックアップ パー ニブルはかなり高速です。8 つの配列ルックアップは、32 の単純なビット操作よりも遅くなる可能性があることに注意してください。

もちろん、特に難解なアプローチに進む前に、アプリの実際のパフォーマンスをテストすることは価値があります...これは本当にボトルネックですか?

Answer 2

次の複製です: how-to-implement-bitcount-using-only-bitwise-operators または best-algorithm-to-count-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;
    }