ビット列中で「1」の桁数を求める
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/01 16:16 UTC 版)
「ルックアップテーブル」の記事における「ビット列中で「1」の桁数を求める」の解説
例えば、（二進数の）数字の中で「1」である桁数（ハミング重み）を求める処理を考える。例えば、十進数の「37」は二進数では「100101」であり、「1」である桁は3つある。 この処理をC言語で記述した簡単な例を以下に示す。この例では、int型の引数を対象に「1」である桁を数えている。 int count_ones(unsigned int x) { int result = 0; while (x != 0) result++, x = x & (x-1); return result;} この一見シンプルなアルゴリズムは、実際に実行すると、近代的なアーキテクチャのプロセッサでも数百サイクルを要する場合がある。これは、ループ中で繰り返し分岐処理が実行されるためである（分岐処理は遅いことが多い）。コンパイラによっては、最適化の際にこの処理をループ展開することで性能がいくらか改善される場合もある。しかし、自明なハッシュ関数を利用したアルゴリズムであればよりシンプルかつ高速に処理が行える。 256個の要素を持つ静的なテーブル（名前はbit_setとする）を用意し、各要素には0から255までの数の「1」の桁数を格納する。int型変数の各バイトの値を自明なハッシュ関数としてこのテーブルをルックアップし、それを足し合わせる。この方法であれば分岐は発生せずメモリアクセスが4回発生するだけのため、上記のコードよりもずっと高速である。 /* ('int'は32ビット幅と仮定) */int count_ones(unsigned int x) { return bits_set[ x & 0xFF] + bits_set[(x >> 8) & 0xFF] + bits_set[(x >> 16) & 0xFF] + bits_set[(x >> 24) & 0xFF] ;} 上記のコードは、xを4バイトの unsigned char 配列にキャストすれば、ビット積（&）とシフトが取り除けるのでさらに高速化できる。また、関数化せずインラインで実装してもよい。 なお、現在のプロセッサではこのようなテーブルルックアップは逆に速度の低下を起こす可能性がある。これは、改善前のコードはおそらく全てキャッシュ上から実行されるが、一方でルックアップテーブルがキャッシュに載りきらなかった場合は、低速なメモリへのアクセスが発生するためである（さらに、上記の例では、4回のルックアップそれぞれにおいてテーブル中の要素のアドレスを計算する必要がある）。
※この「ビット列中で「1」の桁数を求める」の解説は、「ルックアップテーブル」の解説の一部です。
「ビット列中で「1」の桁数を求める」を含む「ルックアップテーブル」の記事については、「ルックアップテーブル」の概要を参照ください。
- ビット列中で「1」の桁数を求めるのページへのリンク
