|
⇤ ← 2014-06-22 10:12:37時点のリビジョン1
サイズ: 3459
コメント:
|
サイズ: 3453
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 69: | 行 69: |
| * [[ビットに関するアルゴリズム色々:http://graphics.stanford.edu/~seander/bithacks.html]] * [[ビット数カウントの解説:http://marupeke296.com/TIPS_No17_Bit.html]] * [[ビット数カウント速度測定:http://www.nminoru.jp/~nminoru/programming/bitcount.html]] * [[Henry S. Warren, Jr. Hacker's Delight (の日本語版):http://www.amazon.co.jp/exec/obidos/ASIN/4434046683/]] この話題に関してはこの本が有名らしい * [[ビットの逆転:http://sunrisebyeast.blogspot.jp/2012/03/blog-post_30.html]] * [[2のn乗アライメント:http://skyrocketing.jp/jkoi/works.html]] |
* [ビットに関するアルゴリズム色々](http://graphics.stanford.edu/~seander/bithacks.html) * [ビット数カウントの解説](http://marupeke296.com/TIPS_No17_Bit.html) * [ビット数カウント速度測定](http://www.nminoru.jp/~nminoru/programming/bitcount.html) * [Henry S. Warren, Jr. Hacker's Delight (の日本語版)](http://www.amazon.co.jp/exec/obidos/ASIN/4434046683/) この話題に関してはこの本が有名らしい * [ビットの逆転](http://sunrisebyeast.blogspot.jp/2012/03/blog-post_30.html) * [2のn乗アライメント](http://skyrocketing.jp/jkoi/works.html) |
ビット演算メモ
ある数値に最も近い 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 によって異なるためそれを判断するのがめんどくさそう)
等が考えられる。