ビット演算メモ
ある数値に最も近い 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 |
0b00100001 |
|
x>>1 |
0b00010000 |
|
OR |
0b00110001 |
すると、MSB の一つ下のビットも強制的に 1 になる。
次に、こうして得られた値を今度は 2 ビット右シフトして同じことをする。
|
x |
0b00110001 |
|
x>>1 |
0b00001100 |
|
OR |
0b00111101 |
こうして 4, 8, 16 ビットとシフト量を増やしつつ繰り返せば MSB 以下が全て 1 になる。
ただし、これだと x = 0 の場合は 0 を返す。ここで 1 を返したい場合は最初か最後で最下位ビットを強制的に 1 にすれば良さそう。
また、int 型のサイズによって実行する処理を増減しないといけない。
他には？
- あるビットごとに区切って、完成済みの変換テーブルを参照する
(速そう) - ビットを逆転させてから LSB (Least Significant Bit) を求めるアルゴリズムを使う
(LSB の計算は非常に高速に書けるが、ビット逆転の演算コストが高いので遅いはず) - 浮動小数点演算器を使う。浮動小数点数が a * 2^n という形で格納されているのを利用
(恐らく非常に高速だが、浮動小数点数のフォーマットが CPU によって異なるためそれを判断するのがめんどくさそう)
等が考えられる。