ビット逆転テーブルの作り方

超小ネタ。

ウェーブレット行列の C++ 版を書いた時にビット逆転（上位から下位のビットの並びを逆にする）テーブルを作る必要があったので、その時にちょっと工夫したこと。どっかでとっくに既出かも。

状況としては、0 から 255 まで（8ビット）とか、0 から 1023 まで（10ビット）といった、ある最大ビット数を持つ数字に対してビット逆転テーブルを用意したいというもの。

それに対する実装。

  bit_reverse_table_[0] = 0;
  for (uint64_t i = 0; i < alphabet_bit_num_; ++i) {
    uint64_t n = (1 << i);
    uint64_t m = (1 << (alphabet_bit_num_ - i - 1));
    for (uint64_t j = 0; j < n; ++j) {
      bit_reverse_table_[n + j] = bit_reverse_table_[j] + m;
    }
  }

alphabet_bit_num_ がビット数、bit_reverse_table_ がビット逆転テーブル。

中身の解説。

まず、0 から 2^i-1 までのテーブルがすでにできているとする。

たとえば、alphabet_bit_num_=5, i=3 とすると、0 から 2^i-1=7 までのテーブル

00000 10000 01000 11000 00100 10100 01100 11100

までのものができている状態。

これを利用して、8 から 15 までのものを追加することを考える。

まず、8 から 15 という数字は、0 から 7 に 8 のところのビット（左から 2番目）を立てたものだ。

つまり、8 から 15 のビットを逆転させたものは、0 から 7 のビットを逆転させたものに 8 を逆転させたビット（右から 2 番目）を立てたものになる。

元々のテーブルに、右から 2番目のビットを立てたものを追加する。

00000 10000 01000 11000 00100 10100 01100 11100
00010 10010 01010 11010 00110 10110 01110 11110

これで、0 から 15 までのビットを逆転させたものができたことになる。

このように、0 から 2^i-1 までのテーブルがすでにできていれば、それにそれぞれ 1 個のビットを立てたものを追加するだけで、0 から 2^(i+1)-1 までのテーブルにできる。

で、最初に

  bit_reverse_table_[0] = 0;

としていて、これが 0 から 2^0-1=0 までのテーブルということになる。

これで、帰納的に全部のテーブルが作れる。

まあ、どうせ作るテーブルの大きさなんてたいしたことないし、どう作っても一瞬だけど！

追記

テーブルを使わない場合は、http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel のような定番のものがありますが、テーブルを作る場合にこれを使うとちょっと無駄だと思います。まあ実用上問題になることはないと思いますが。

（2012/09/12 追記）
テーブルを使わない場合の例として、もっといいもの（by id:qnighy さん）があったのでリンク。ビットリバース - 簡潔なQ