#format text_markdown

ビット演算メモ
==============

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

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

### 方法 ###

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

```c
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**1**00001          |
+----+------------------------+
|x>>1|0b000**1**0000          |
+----+------------------------+
|OR  |0b00**11**0001          |
+----+------------------------+

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

+----+------------------------+
|x   |0b00**11**0001          |
+----+------------------------+
|x>>1|0b0000**11**00          |
+----+------------------------+
|OR  |0b00**1111**01          |
+----+------------------------+

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

### 他には？ ###

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

等が考えられる。


参考文献
--------

* [ビットに関するアルゴリズム色々](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)