Integer.reverse( int ) の処理を追ってみる

前書き

JavaのIntegerクラスには、ビットを反転するInteger.reverseというメソッドがあります。

例えば「100」は2進数に直すと1100100になります。これを反転すると、こんな感じになります。

処理前 : 00000000000000000000000001100100
処理後 : 00100110000000000000000000000000

ちゃんと反転されています。

コード的には以下のような感じで実行します。

/** 3の場合 */
int i = 3;
System.out.println( Integer.toBinaryString( i ) );
  // => 00000000000000000000000000000011

i = Integer.reverse( i );
System.out.println( Integer.toBinaryString( i ) );
  // => 11000000000000000000000000000000

右2つに1が立っていたのが、左2つに移動しています。

この処理はどういったロジックで実現しているのでしょうか。

@CretedDate 2009/09/28頃
@Versions Java5

Integer.reverseの中をこっそり覗いてみよう

では、恒例の覗きの時間です。Integer.reverseの中身は、こんな処理をしています。

/** Integer.reverseの中身 */
public static int reverse(int i) {
  i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
  i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
  i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
  i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24);
  return i;
}

また随分と素敵な表記です。日本語で話せやコラとか言いたくなります。

でも、Integer.bitCountの時に見かけた処理に似ているので、それほど苦戦はしないんじゃないかという甘い予想もしつつ、解析フェーズへ。

とりあえず2進数にしてみる、話はそれからだ

とりあえず、中にいる怪しい16進数を全部2進数にしてみましょう。きっと何か見えるはず。

中にいる16進数は、「0x55555555」、「0x33333333」、「0x0f0f0f0f」、「0xff00」の4つ。これらを2進数にすると、こんな感じになります。

0x55555555	01010101010101010101010101010101
0x33333333	00110011001100110011001100110011
0x0f0f0f0f	00001111000011110000111100001111
0xff00	00000000000000001111111100000000

0x55555555は、0と1が交互に並び、0x33333333は、00と11が交互に並び、0x0f0f0f0fは、0000と1111が交互に並んでいます。

そして最後の0xff00は、32ビットの中の9～16番目までが1で、それ以外が0になっています。

1行目のソースを追ってみる

とりあえず、もう1回、全体のソースを見てみましょう。

1:  i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
2:  i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
3:  i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
4:  i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24);
5:  return i;

1～3行目は、数値とシフトする数が違うだけで、処理自体は似たようなことをしています。

ということは、1行目が理解できれば、1～3行目まで理解したも同然になりそうです。

1行目で使用されている、0x55555555は、0と1が交互に並ぶ処理でした。ということは、1行目の前半、(i & 0x55555555) << 1 で、(i & 0x55555555)は、値を交互に無効にして、1シフトするという意味になります。

例えば、i が 63（2進数だと、111111）だった場合は、こんな風に変換されます。

/** 1行目の前半の処理を、63で試してみる */
1 :  int i = 63;
2 :  System.out.println( Integer.toBinaryString( i ) );
3 :   // => 111111
4 :
5 :  i = (i & 0x55555555);
6 :  System.out.println( Integer.toBinaryString( i ) );
7 :    // => 010101
8 :
9 :  i = i << 1;
10 :  System.out.println( Integer.toBinaryString( i ) );
11 :    // => 101010

1行目 ： 111111
5行目 ： 010101
9行目 ： 101010

0x55555555の&演算で、値が縞々になり、それを左に1つズラすという処理になっています。

そして処理の後半部分の記述が、| (i >>> 1) & 0x55555555。先に1つ右にシフトした後、0x55555555で縞々にして、それを、前半の値と | しています。

さて、この処理はどういう意味の処理でしょう。だいぶ答えを書いてしまった感はありますが、この辺で閃き（ピコーン）タイムにしましょう。

1行目の解説

さて、解答です。

1行目の処理は、010101……でマスクして左に1シフトしたものと、右に1シフトした後に010101……でマスクしたものを | しています。

ということは、1行目の前半と後半において、マスクしているビットは被っていないことが分かります。そして、左シフト、右シフトと、逆方向にシフトしています。

ここまで書けば、答えとほぼ同じですね。そうです、1行目の処理は隣同士のビットを入換える処理というわけでした。

せっかくなので、実際に値を入れて試してみましょう。

/** 1行目の処理を、100で試してみる */
int i = 100;
System.out.println( Integer.toBinaryString( i ) );
  // => 01100100

i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
System.out.println( Integer.toBinaryString( i ) );
  // => 10011000

実行前 ： 01 10 01 00
実行後 ： 10 01 10 00

1のビットの場所が、隣同士で入れ替わっていることが分かります。

2～3行目の解説

1:  i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
2:  i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
3:  i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
4:  i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24);
5:  return i;

2～3行目は1行目と同じですね。

1行目は、010101……でマスクして1シフトすることで隣同士を交換していましたが、2行目は00110011……でマスクして2シフトしているので、2つ隣の値と交換するような処理になります。3行目はマスクが0000111100001111……で4シフトなので、4つ隣と交換になります。

実際にやってみましょう。

/** 2～3行目の処理を、100で試してみる */
int i = 100;
System.out.println( Integer.toBinaryString( i ) );
  // => 01100100

/** 2行目の処理 */
i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
System.out.println( Integer.toBinaryString( i ) );
  // => 10010001

/** 3行目の処理 */
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
System.out.println( Integer.toBinaryString( i ) );
  // => 00011001

2行目実行前 ： 01 10   01 00
2行目実行後 ： 10 01   00 01

2行目実行前の1ブロック目 → 実行後の2ブロック目
2行目実行前の2ブロック目 → 実行後の1ブロック目
2行目実行前の3ブロック目 → 実行後の4ブロック目
2行目実行前の4ブロック目 → 実行後の3ブロック目

というように値が入れ替わっていることがわかります。

3行目実行前 ： 1001 0001
3行目実行後 ： 0001 1001

これも2行目実行時と同じように、ブロックが入れ替わっていることが分かります。

4行目の解説

1～3行目を実行することで、8ビット単位でのリバースは終了しました。

残りはあと、8ビット×4個のフィールドの順序を、先頭と4番目を入換え、2番目と3番目を入換えれば、リバース処理も終了です。

そこで利用されるのが、0xff00（00000000000000001111111100000000）です。

32ビット中、8ビットだけ1が入った値を使えば、入換える際に必要なビットだけを選んで残すことができそうですね。

/** 4行目のコード */
4:  i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24);

4行目の処理は、以下の4つの処理に分割できます。

(i << 24)	24個右にシフトすることで、右8つの値だけを残しつつ、左8つの位置に配置する
((i & 0xff00) << 8)	1～3行目で行った処理の8ビット版、3ブロック目を2ブロック目に持っていく
((i >>> 8) & 0xff00)	1～3行目で行った処理の8ビット版、2ブロック目を3ブロック目に持っていく
(i >>> 24)	24時左にシフトすることで、左8つの値だけを残しつつ、右8つの位置に配置する

分かりやすそうな例として、1074791425（01000000 00010000 00000100 00000001）を使ってそれぞれの処理を通して見ましょう。

/** i << 24 の例 */
int i = 1074791425;
i = i << 24;
System.out.println( Integer.toBinaryString( i ) );
  // => 00000001000000000000000000000000

実行前 ： 01000000 00010000 00000100 00000001
実行後 ： 00000001 00000000 00000000 00000000

/** i >>> 24 の例 */
int i = 1074791425;
i = i >>> 24;
System.out.println( Integer.toBinaryString( i ) );
  // => 00000000000000000000000001000000

実行前 ： 01000000 00010000 00000100 00000001
実行後 ： 00000000 00000000 00000000 01000000

/** ((i & 0xff00) << 8) の例 */
int i = 1074791425;
i = ((i & 0xff00) << 8);
System.out.println( Integer.toBinaryString( i ) );
  // => 00000000000001000000000000000000

実行前 ： 01000000 00010000 00000100 00000001
実行後 ： 00000000 00000100 00000000 00000000

/** ((i >>> 8) & 0xff00) の例 */
int i = 1074791425;
i = ((i >>> 8) & 0xff00);
System.out.println( Integer.toBinaryString( i ) );
  // => 00000000000000000001000000000000

実行前 ： 01000000 00010000 00000100 00000001
実行後 ： 00000000 00000000 00010000 00000000

という感じで、無事、1と4、2と3ブロック目のビットを入換えることに成功しました。

全体の処理の概略をもう一度書くと、1行目で1ビット単位で隣同士のブロックを入換え、2行目で2ビット単位で隣同士のブロックを入換え、3行目で4ビット単位で隣同士のブロックを入換え、4行目で8ビット単位で隣同士のブロックを入換えることで、reverseは完了しました。