POPCOUNTで考えるSIMD

立っているビットの数（POPCOUNT）を数える鮮やかな方法があって、簡単なSIMDとなっていました。

どのような方法で計算するか

CPUやJavaなど環境によっては計算ルーチンが用意されていますが、ない時はどのように計算すればいいでしょうか。まずは単純な方法を考えてみます。

1ビットずつ足していく

単純に1ビットずつ見て足していくという方法もありますが、桁数に比例して時間がかかってしまいます。

表引きにする

8ビット分なりを表にすれば加算の回数は減りますが、それでも桁数に比例する状況はそのままとなります。

ということで、これらの方法では桁数比例の時間がかかるのは変わりません¹。

まずは1ビットの演算なんだし

1ビットずつ足していくとすれば、最初の結果は0～2の2ビットで収まります。なら、何ビットあるか知りませんがレジスタの全幅を使うのは無駄が多すぎます。なお、ビット幅が決まらないと定式化の際に問題が出るので、以下では32ビットとしておきます（いちばん下が0ビット、いちばん上が31ビット）。

0ビット目+1ビット目の結果を0ビット～1ビットの2桁に、2ビット目+3ビット目の結果を2ビット～3ビットに…というように2桁ごとに別々な計算をするようにすれば、一気に16ビットの足し算が終わってしまいます。おまけに、結果の境界を超えた繰り上がりが発生しないので、単なる整数演算でこの演算を行うことができます。

C言語で書けば、val = (val & 0x55555555) + ((val >> 1) & 0x55555555)のようになります（0x55555555は、1ビットおきに値を拾うためのマスクです）。

あとは同様に、2桁+2桁の足し算、4桁+4桁の足し算というようにすすめていけば、桁数の対数のステップで終わらせることができます。

SIMDって？

3DCGなどのマルチメディア分野で顕著に見られますが、「大量のデータに同じ演算を行う」必要はよくあります。今回はたまたまふつうの整数演算で片付きましたが、現代のCPUやGPUには、長いレジスタに複数のデータを突っ込んで、複数の演算を並列で一気に行う、SIMD命令が搭載されています。

1. 桁数にかかわらず整数どうしの演算は定数時間でできる、という前提です（多倍長演算で足し算も桁数に比例する時間がかかる、ような場合は考慮していません） ↩