ビット演算メモ

ある数値に最も近い 2^n -1 を求める

0b00101001 → 0b00111111 のような変換。
1 になっている最上位のビット (Most Significant Bit, MSB) より下を全て 1 にする。
普通に考えたら 1 ビットずつシフトしていって if で判断して、となるが、せっかくなので高速なアルゴリズムを知っておきたい。

方法

参考文献に挙げたページを一通り見た結果、以下のようなコードにした。
速度計測はまだ行っていない。

unsigned int hashIndexNum(unsigned int x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    if (sizeof(x) > 2) x |= x >> 16; //for 32 bit int
    if (sizeof(x) > 4) x |= x >> 32; //for 64 bit int
    return x;
}

unsigned int 型のサイズによらず動作するコードを書きたかった (上記コードは 8 バイトまで対応)。
分岐が入っているように見えるが、コンパイル時に条件式が定数となり、最適化により分岐の判断自体が省略されるはずである。

仕組み

例えば x = 0b00100001 とする。
まず x を 1 ビット右シフトした値と元の x とのビットワイズ OR を取る。

|x |0b00&color(red){1};00001|
|x>>1|0b000&color(red){1};0000|
|OR |0b00&color(red){11};0001|

すると、MSB の一つ下のビットも強制的に 1 になる。
次に、こうして得られた値を今度は 2 ビット右シフトして同じことをする。

|x |0b00&color(red){11};0001|
|x>>1|0b0000&color(red){11};00|
|OR |0b00&color(red){1111};01|

こうして 4, 8, 16 ビットとシフト量を増やしつつ繰り返せば MSB 以下が全て 1 になる。
ただし、これだと x = 0 の場合は 0 を返す。ここで 1 を返したい場合は最初か最後で最下位ビットを強制的に 1 にすれば良さそう。
また、int 型のサイズによって実行する処理を増減しないといけない。

他には？

• あるビットごとに区切って、完成済みの変換テーブルを参照する
  (速そう)
• ビットを逆転させてから LSB (Least Significant Bit) を求めるアルゴリズムを使う
  (LSB の計算は非常に高速に書けるが、ビット逆転の演算コストが高いので遅いはず)
• 浮動小数点演算器を使う。浮動小数点数が a * 2^n という形で格納されているのを利用
  (恐らく非常に高速だが、浮動小数点数のフォーマットが CPU によって異なるためそれを判断するのがめんどくさそう)

等が考えられる。

参考文献

• ビットに関するアルゴリズム色々
• ビット数カウントの解説
• ビット数カウント速度測定
• Henry S. Warren, Jr. Hacker’s Delight (の日本語版) この話題に関してはこの本が有名らしい
• ビットの逆転
• 2のn乗アライメント