How many bits...

コンピュータで要素数がたかだか有限個の集合を扱うとき、定石とも言えるやり方が整数の各ビットを「集合に含まれているか」のフラグとして扱うやり方です。この方式だと、集合の「かつ」も「または」も、論理積と論理和で一発で計算できてしまう。もちろん定数時間ですよ。なんて合理的なんでしょう！
でも問題は残ります。符号なし整数で集合を与えられたとして、その集合に含まれている要素の数はと問われると、１ビットずつ検査しないといけない。いきなりビット数nに比例した計算量O(n)を要求されるのです。そこで、これをもうちょい速く計算できないか、すなわち、「nビットの（符号なし）整数の、立っているビットの数を数えろ」をO(n)未満の時間で求められないかと考えています。できればO(log n)くらいで。
いま考えているのは、分割統治法。２ビットのブロックにわけ、ブロック内で合算するのは簡単です。奇数ビットだけと偶数ビットだけ立った整数に分けて、偶数ビットの方を右シフトして加算すればOK。次は、４ビットごとのブロックに分けて、４ビットの上位側をまとめて２つ右シフトして・・・と繰り返していけばlog n回で終わります。
ただ、奇数側と偶数側に分けるためのマスク用ビット列を用意する方法が思いつきません。１回目には「0101010101」、２回目には「00110011」、３回目には「00001111」なんだけど、ビット数が任意のnである以上、このマスクビット列は最初から用意しておくのではなく自動生成できないといけない。それも定数時間で。でも１回目から２回目を生成する方法、そいつが全然思いつきません。これさえ解決できれば革命が・・・おこることは全然ないんだけどさ。