c - O(1)時間で2進数の1の数を見つける方法は?

Question

これは以前に尋ねられたことは知っていますが、ここにリストされているこの特定のソリューションを見ています：

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

それはどのように機能しますか？

ここに関連する注意事項はありますか?

理論的には、一定時間で答えを見つけることは可能ですか? つまり、カウントするために実際にビットを反復処理する必要はありませんか?

Answer 1

これを行う最も速い方法は popcnt 命令です。通常、コンパイラ組み込み関数を介してアクセスできます。あなたのソリューションは、この指示がないプラットフォームで役立つ場合があります。

Answer 2

型のビット数は一定であるため、ビットの反復は一定時間です。

したがって、1 ビットのマスクをチェックし、ターゲット値の各ビットをシフトするソリューションは確かにO(1)(たとえば、定数が 32 の場合) です。