ビット逆転ループ

注意: この記事は読んでも役に立ちません。頭を無駄に使いたい人向け。


普通のループは、たとえば 0 から 255 までなら、0 -> 1 -> 2 -> ... というようにループする。

そういう普通のループじゃなくて、ビットを逆転させた数字でループできたらいいのになぁということが最近あった。

0 -> 128 -> 64 -> ... のように。


探してみると、そういうページが見つかった。

さすがネットは広い。

コードは以下の通り。

int r = 0;        // counter
int s = 0;        // bit-reversal of r/2<
int N = 256;      // N can be any power of 2
int N2 = N << 1;  // N<<1 == N*2

do {
  printf("%u ", s);
  r += 2;
  s ^= N - (N / (r&-r));
}
while (r < N2);


思わず「ファッ！？」と声が出てしまいそうな実装だ。

しかし、よくよく考えてみるとそんなに難しいこともない。


ビット演算に慣れている人向けの説明は次のようなものになる。

逆順インクリメントをしたい数字を p として、その全体のビット数を m とし、p の上から連続した 1 の数を n とする。

  1. p をビット逆順インクリメントした数は、上から n+1 個のビットが立っていて残りが 0 の数字(X とする)と p との XOR をとることで求められる。
  2. X は、上から n 個の 0 が並び、その下に 1 があり、残りはすべて 0 の数(Y) を 2 の m乗から引くことで求められる。
  3. Y は、下から n 個の 0 が並び、その上に 1 があり、残りはすべて 0 の数(Z) で 2 の m-1乗を割ることで求められる。
  4. Z は、p の逆順の数字をインクリメントした数字（qとする）と、そのマイナスの数字との AND をとることで求められる。

よって、ループ中には正順のループカウンタ+1（q にあたる）を持っておけばいい。上のコードでは、r が q * 2 にあたる。


まあ、これは簡潔すぎるので、より詳しく説明する（それでも紙に書かないとつらいと思う）。


まず、

r&-r

ここは何をしているのか。

これは、「ビット列の中で、一番下にある 1 のビット」だけを取り出すというコード。


まず、r という数字が、下から n 個の 0 が並んでいて、その上に 1 がある（目的のビット）とする。

n、つまり下から見て並んでいる 0 の数は、r が 1010 なら 1 個、r が 1011 なら 0 個、r が 1100 なら 2個といった具合だ。


ここで、「その数字のビットを反転させたもの」を考える。

1010 なら 0101、1011 なら 0100、1100 なら 0011。


「下から n 個の 0 が並んでいる数字」のビットを反転させたものは、下から n 個の 1 が並んでいる。

これは当たり前だ。


ここで、元の数字と、そのビットを反転させた数字で AND 演算をすることを考える。

この演算では、すべてのビットが反転しているので、共通部分がなくて 0 になる。


たとえば、元の数字が 1100（下から 2個の 0 が並んでいる）、つまり 10進数で 12 の場合。

ビットを反転させた 0011（下から 2個の 1 が並んでいる）との AND は次のように 0 になる。

  1100
& 0011
------
  0000


ここで、元の数字のビットを反転させた 0011、つまり「下から 2 個の 1 が並んでいる数字」をインクリメントするとどうなるかを考える。

  0011
+ 0001
------
  0100

すると、「下から 2個の 0 が並び、その上に 1 がある数字」になる。

下から n 個の 1 があり、その上に 0 がある数字をインクリメントすると、下から n 個の 0 があり、その上に 1 があり、さらにその上はそのままという結果になる。


今度は、元の数字である 1100（下から 2個の 0 が並んでいる）と、この数字の AND をとる。

すると、「下から 2 個の 0 と、その上の 1」が共通ということになる。

それより上の桁は影響を受けないので反転したまま。

次のようになる。

  1100
& 0100
------
  0100


「下から 2 個の 0」は AND で 0 のまま、「その上の 1」は元々 1 だったところなので 1、それより上の数字は元の数字のビットを反転させたもののままなので、AND ですべて 0 になる。

結果として、「元の数字で下から見て最初の 1 だけ 1 として残り、ほかがすべて 0 になった数字」が得られたことになる。


ここで使った「ビットを反転させてインクリメント」という操作は、「マイナスをとる」というのと同じ操作になる。

この辺りについては、「1 の補数」「2 の補数」などをキーワードに調べることができる。


ここまでで、r & -r という操作で、「下から見て最初の 1 だけが立った数字」が得られることがわかった。

1100 なら 0100、1000 なら 1000、1010 なら 0010、1001 なら 0001 といったものになる。



ここで、数字逆順ループの話に戻る。


まず、2進数の普通のインクリメントでは、ビットはどういう変化をするかを考える。

たとえば、2進数の 1010、つまり 10進数の 10 に 1 を足す場合。

  1010
+ 0001
------
  1011

一番下の桁だけ変化する。

つまり、0001 と XOR をとるのと同じことだ。


じゃあ、2進数の 1001、つまり 10進数の 9 に 1 を足す場合はどうだろう。

  1001
+ 0001
------
  1010


一番下の桁が 1 から 0 になって、繰り上がって次の桁が 0 から 1 になる。

これは、0011 と XOR をとるのと同じことになる。


次に、2進数の 1011、つまり 10進数の 11 に 1を足す場合。

  1011
+ 0001
------
  1100

2回繰り上がるので、下から 1番目と 2番目が 0 から 1 に、3番目が 0 から 1 になる。

0111 と XOR をとるのと同じということだ。



変化するのは、常に下から数えて連続したいくつかの桁ということになる。

その変化する桁の数は、繰り上がりの回数 + 1 になる（繰り上がりがなければ 1個、1回繰り上がるなら 2個)。

そして、繰り上がりの回数というのは、下から数えた連続した 1 の個数。


まとめると、変化する桁の数は

(下から見て連続した 1 の数) + 1

ということになる。

1001 なら、下から見て連続した 1 の数は 1個なので、変化する桁は 2個。

1010 なら、下から見て連続した 1 の数は 0個なので、変化する桁は 1個。

1011 なら、下から見て連続した 1 の数は 2個なので、変化する桁は 3個。



ここまでで一旦まとめる。

2進数のインクリメントには、次の性質がある。

  • (下から見て連続した 1 の数) + 1 個だけ、下の桁で 0 と 1 が変化する。

つまり、次のことができたら、ビット逆順のインクリメントができることになる。

  • (上から見て連続した 1 の数) + 1 個だけ、上の桁の 0 と 1 を変化させる。



つまり、「(上から見て連続した 1 の数) + 1 個のビットが上から立った数字(X とする)」が得られたら、それとの XOR をとることで、ビット逆順の数字のインクリメントができることになる。


1100 なら、上から 2 個の 1 が連続しているので、上から 3 つのビットが立った 1110 と XOR をとることで、次の数字が得られる。

  1100
^ 1110
------
  0010

1100（0011の逆）-> 0010（0100の逆）と進んでいるので、ちゃんとビット逆順のインクリメントができている。


ここで、「（上から見て連続した 1 の数） + 1 個のビットが上から立った数字(X)」というのは、直接得ることはできない。

だが、上で見たように、「下から見て最初の 1 だけが立った数字」というものは r & -r という演算で簡単に得られる。

ここから、「下から見て最初の 1 だけが立った数字」を求める方法から、「（上から見て連続した 1 の数） + 1 個のビットが上から立った数字(X)」を得る方法を考える。



まず、「（上から見て連続した 1 の数） + 1 個のビットが上から立った数字(X)」を求める方法。

具体的には、そういう数字とは、

1001 なら、上から見て連続した 1 の数は 1個なので、求める数字は上から 2 個のビットが立った 1100。

0101 なら、上から見て連続した 1 の数は 0個なので、求める数字は上から 1 個のビットが立った 1000。

1101 なら、上から見て連続した 1 の数は 2個なので、求める数字は上から 3 個のビットが立った 1110。


これを求めるには、「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」があればいい。


1001 なら、0100。

0101 なら、1000。

1101 なら、0010。


この「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」があれば、2 の補数をとる（この例でいうと 10000 から引くというのと同じ）ことで、Xが得られる。

10000 - 0100 = 1100

10000 - 1000 = 1000

10000 - 0010 = 1110



次に、「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」を求める方法。

これは、「逆順の数字で、下から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Z)」のビットを逆順にすることで求められる。


数字が 1101 なら、求めたい「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」は、上で見たように 0010 となる。

この場合、逆順の数字は 1011 なので、これから「下から見て連続した 1 の数だけ下から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Z)」を求められるとすると、Z は Y の逆の 0100 になる。


このように、「1 が一個だけ立っている数字」については、ビット逆順の数字を求めることは非常に簡単だ。

n桁の 2進数なら、n桁目（最上位ビット）だけが立っている数字をその数字で割ればいい。

4桁の場合、1000を割ることになる。

1000 / 0001 = 1000
1000 / 0010 = 0100
1000 / 0100 = 0010
1000 / 1000 = 0001



あとは、「下から見て連続した 1 の数だけ下から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Z)」を求める方法。


まず、「下から見て 1 が n個連続した数字」について考える。

n個連続した 1 の、すぐ上の桁は必ず 0 になっている。

（上の桁が 1 なら、それも「連続した 1」としてカウントされるから）


たとえば 1011 で考えると、下から 1 が 2個並んでいて、その上に 0 がある。


ここで、「下から見て 1 が n個連続した数字」をインクリメントするとどうなるかを考える。

下から n個の 1 は、すべて繰り上がって 0 になる。

その上の 0 は、繰り上がりで 1 になる。

つまり、「下から n個の 0 が並んでいて、その上に 1 がある」という状態になる。

1011 で考えると、次のようになる。

  1011
+ 0001
------
  1100

下から 2個の 1 が並んでいたのが、インクリメントすると下から 0 が 2個並んだ数字になる。



そして、「下から 0 が n個並んだ数字」から「下から見て連続した 1 の数だけ下から 0 が並び、その次に 1 があり、残りはすべて 0 の数」を求めるには、上で見た通りに、元の数字とそのマイナスの数字で AND 演算をすればいい。


ここまでで、必要な計算は一通り揃った。

流れを復習する。


数字の全体のビット数（仮に 4 とする）を m とする。

また、逆順インクリメントしたい数字の、上から連続した 1 の数を n とする。

  1. ある数字 p をビット逆順インクリメントするには、上から n+1 個のビットが立っていて残りが 0 の数字(X)と XOR をとることで求められる。
  2. X は、上から n 個の 0 が並び、その下に 1 があり、残りはすべて 0 の数(Y) を 2 の m乗（この場合は 10000）から引くことで求められる。
  3. Y は、下から n 個の 0 が並び、その上に 1 があり、残りはすべて 0 の数(Z) で 2 の m-1乗（この場合は 1000）を割ることで求められる。
  4. Z は、p の逆順の数字をインクリメントした数字（下から n 個の 0 が並んでいる。q とする）と、そのマイナスの数字との AND をとることで求められる。


ここで、p の逆順の数字をインクリメントした数字である q はループ時に持っておくことにする。

次のようにループすることになる。

    p    q
 0000 0001
 1000 0010
 0100 0011
 1100 0100
 0010 0101
 ...

p が逆順の 0, 1, 2, 3, 4 で、q が正順の 1, 2, 3, 4, 5 だということがわかるだろうか。


q を持っておけば、上の各数字は次のようになる。

（p の次の値を p' とする。また、べき乗は ** で表す。& = AND, ^ = XOR）

Z = q & -q
Y = (2 ** (m - 1)) / Z
X = (2 ** m) - Y
p' = p ^ X

これらをまとめると、次のようになる。

p' = p ^ ((2 ** m) - ((2 ** (m - 1)) / (q & -q)))

ここで、N = 2 ** m とおき、また r = 2 * q とおくと、次のようになる。

p' = p ^ (N - (N / (r & -r)))

これで、元のコードとほぼ同じものになった。



元のコードに戻る。

int r = 0;        // counter
int s = 0;        // bit-reversal of r/2
int N = 256;      // N can be any power of 2
int N2 = N << 1;  // N<<1 == N*2

do {
  printf("%u ", s);
  r += 2;
  s ^= N - (N / (r&-r));
}
while (r < N2);

ここでは、正順のカウンターである r を 2 倍している。

これは、途中の計算を減らすためだ。


しかし、そこまで気にしないなら、N2 を減らして、また for 文を使って次のように書くこともできる。

int s = 0;        // bit-reversal of r/2
int N = 256;      // N can be any power of 2

for (int r = 0; r < N; ++r, s ^= N - (N / 2 / (r & -r) )) {
  printf("%u ", s);
}

だいぶすっきりした。

でも、これはコメントがないとつらそう。


で、ビット逆順のループなんかどこで使うのかという話だが、以前書いたウェーブレット行列の省メモリ構築方法で使っている。

ウェーブレット行列のライブラリはこちら。


ビット逆順のループについて知ったのはつい最近で、それまではビットを逆順にするテーブルを作っていた。

ビットを逆順にするテーブルの作り方についても前に書いたことがあるけど、あらためてコードを簡単にして書くと次のようになる。

  int N = 8;
  int t[256] = {0};

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < (1 << i); ++j) {
      t[(1 << i) + j] = t[j] + (1 << (N - i - 1));
      printf("%d\n", t[(1 << i) + j]);
    }
  }

簡潔に書けるので気に入っている。

また、ある単独の数字のビットを逆転させたいというだけなら、有名な次のやり方がいい（32bit版）。

x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;

これは、4ビットや 8ビットの場合を紙に書いてやってみると、簡単なことをやっているのがわかる。


というわけで、ビット逆転についての話でした。

実用的には最後の有名なやり方だけでもいいと思うけど、簡潔に書けるとうれしい。


普通はなかなか使う機会がないと思う*1。


ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
posted with amazlet at 13.10.18
ジュニア,ヘンリー・S. ウォーレン
エスアイビーアクセス
売り上げランキング: 62,823
Amazon.co.jpで詳細を見る

*1:FFT では使うらしい。