[解決済み] BitcountをBitwise演算子のみで実装する方法は？

質問

課題は、ビット演算子のみを用いたビットカウントロジックの実装です。私はそれをうまく動作させることができましたが、誰かがよりエレガントなアプローチを提案することができるかどうか疑問に思っています。

Bitwise opsのみ使用可能です。if"、"for"などは不可。

int x = 4;

printf("%d\n", x & 0x1);
printf("%d\n", (x >> 1) & 0x1);
printf("%d\n", (x >> 2) & 0x1);
printf("%d\n", (x >> 3) & 0x1);

ありがとうございました。

解決方法は？

から http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here

c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
c = ((c >> 16) + c) & 0x0000FFFF;

編集：確かに少し最適化されているので、読みにくくなっています。とすると読みやすいと思います。

c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F);
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF);
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF);

この5つのステップでは、隣接するビットを1、2、4...といった具合に追加していきます。 この方法は、分割統治（Divide and Conquer）に基づいています。

最初のステップでは、ビット0と1を加算して2ビットのセグメント0-1に入れ、ビット2と3を加算して2ビットのセグメント2-3に入れる......といった具合です。

第2段階では、0-1と2-3の2ビットを足し合わせて4ビット0-3に、4-5と6-7の2ビットを足し合わせて4-7に......といった具合に、4ビットを足し合わせていく。

例

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)
After the first step I have:      0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10
In the second step I have:        0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011
In the fourth step I have:        0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100
In the last step I have:          0000000000000101 (       00000001+00000100       )

は 5 に等しく、これは正しい結果です。