Integer.toString( i ) に見る数値から文字列への変換

Integer.toString( int )の中身

では、Integer.toString( int )の中身はどうなっているのでしょう。

覗いてみました。けっこう長いです。

public static String toString(int i) {
  // Integer.MIN_VALUEは正の数に変換することができない
  // 下の処理で正の数への変換を行う箇所がある為、固定の結果を返す形で逃がしている
  if (i == Integer.MIN_VALUE)
    return "-2147483648";
  // 引数で渡された数値が、文字列にすると何文字になるかを取得
  int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
  // 結果として返す予定の文字数分を領域として確保したchar配列を生成
  char[] buf = new char[size];
  // iを文字にして、bufに格納してくれるメソッド
  getChars(i, size, buf);
  // bufを文字列に変換して返す
  return new String(0, size, buf);
}

// 引数で渡された数値が何文字かを判定する為のベタベタな配列
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999, 
        99999999, 999999999, Integer.MAX_VALUE };
// 引数で渡された数値が何文字か判定する
static int stringSize(int x) {
  for (int i=0; ; i++)
    if (x <= sizeTable[i])
      return i+1;
}

// iを文字にして、bufに格納してくれるメソッド
static void getChars(int i, int index, char[] buf) {
  int q, r;
  int charPos = index;
  char sign = 0;

  // 負数か判定して、負ならマイナスを設定する準備
  // ついでに引数を絶対値にしておく
  if (i < 0) { 
    sign = '-';
    i = -i;
  }

  // この辺が面白いところ
  // 65536を超えている値については、100で割りながら、
  // 下2桁が何かを判定し、bufに詰めている
  while (i >= 65536) {
    q = i / 100;
    r = i - ((q << 6) + (q << 5) + (q << 2));
    i = q;
    buf [--charPos] = DigitOnes[r];
    buf [--charPos] = DigitTens[r];
  }

  // この辺も面白いところ
  // 52429掛けて16+3シフトするってどういう意味さって感じです
  for (;;) { 
    q = (i * 52429) >>> (16+3);
    r = i - ((q << 3) + (q << 1));
    buf [--charPos] = digits [r];
    i = q;
    if (i == 0) break;
  }

  // 負数ならマイナスをbufの先頭に詰めている
  if (sign != 0) {
    buf [--charPos] = sign;
  }
}

// 0～99までの値が渡された場合に、10の位の数字を文字列にしたものを返す為の子
// 例えば34を渡せば「3」を返してくれる
final static char [] DigitTens = {
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
'2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
'3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
'4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
'5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
'6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
'7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
'8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
'9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
} ; 

// 0～99までの値が渡された場合に、1の位の数字を文字列にしたものを返す為の子
// 例えば34を渡せば「4」を返してくれる
final static char [] DigitOnes = { 
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
} ;

// 0～36までの数をcharに直す際に使用する配列
final static char[] digits = {
'0' , '1' , '2' , '3' , '4' , '5' ,
'6' , '7' , '8' , '9' , 'a' , 'b' ,
'c' , 'd' , 'e' , 'f' , 'g' , 'h' ,
'i' , 'j' , 'k' , 'l' , 'm' , 'n' ,
'o' , 'p' , 'q' , 'r' , 's' , 't' ,
'u' , 'v' , 'w' , 'x' , 'y' , 'z'
};

長いけど処理自体は単純なので、結果をイメージしながら追いかけると分かり易いです。

とりあえず要点だけ追ってみましょう。

要点だけ追ってみる(toStringの1～3行目)

/** toStringの1～3行目 */
1:  if (i == Integer.MIN_VALUE)
2:    return "-2147483648";
3:  int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);

1,2行目はInteger.MIN_VALUEの場合だけ特別に固有の値を返しています。

3行目で、0未満なら云々という処理があります。「Math.abs( Integer.MIN_VALUE )について」の項で書きましたが、-2147483648は-1を掛けても-2147483648のままなので、3行目の処理は効きません。

というわけで、1～2行目でInteger.MIN_VALUEのみ逃がされているようです。

要点だけ追ってみる(toStringの3～4行目)

/** toStringの3～4行目 */
3:  int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
4:  char[] buf = new char[size];

/** 文字列にした時の文字数を取得する */
static int stringSize(int x) {
  for (int i=0; ; i++)
  if (x <= sizeTable[i])
    return i+1;
}
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };

4行目で、char配列を生成しています。たぶんこのchar配列に、数値を文字に変換した結果を詰めていくんだろうなぁということが予想できます。

そのsizeは3行目でstringSizeメソッドを呼んで、値がマイナスなら、「-」の分だけ1プラスして取得します。

で、その文字数を取得するstringSizeメソッドですが、sizeTableを見ての通り、けっこうゴリゴリです。9以下だったら1桁、99以下だったら2桁、999以下だったら3桁みたいに返しています。

なんかシフト演算とかで綺麗に返す魔法があるんじゃないかと期待していたのでガッカリです。バイナリーサーチ的にすればせめて探索回数は減りそうですが、引数に渡される数値はMAX_VALUE付近は少なく、1～2桁くらいが最も多いと思われるので、このくらいがちょうど良いのかも。

要点だけ追ってみる(toStringの5～6行目)

/** toStringの5～6行目 */
5:  getChars(i, size, buf);
6:  return new String(0, size, buf);

getCharsというメソッドに、引数である「i」と、さっき取った「size」、それに「char[] buf」を入れています。で、最後にbufを文字列に変えて返しています。

ということで、getCharsメソッドは「buf」の中を数値をcharに変換した値で埋めてくれるんだろうなぁ的なことがわかります。

要点だけ追ってみる(getCharsの1～15行目)

  /** getChars（1～8行目） */
  static void getChars(int i, int index, char[] buf) {
1:  int q, r;
2:  int charPos = index;
3:    char sign = 0;
4:
5:    if (i < 0) { 
6:      sign = '-';
7:      i = -i;
8:    }

5～8行目で、引数（ i ）で渡された値負数だったらsignにマイナスを設定して、i は正の数に変換しています。

  /** getChars（9～15行目） */
 9:  while (i >= 65536) {
10:    q = i / 100;
11:    r = i - ((q << 6) + (q << 5) + (q << 2));
12:    i = q;
13:    buf [--charPos] = DigitOnes[r];
14:    buf [--charPos] = DigitTens[r];
15:  }

9行目で65536以上であればループしています。

なぜ65536未満までという中途半端な判定をしているかは、ここより後の処理を見ると分かるので、今は説明を割愛します。

10行目で100で割る処理があり、13～14行目で、bufに対して下から2つ値を詰めている処理があります。

ということは、10～12行目の処理で、r の値に i の下2桁を抽出されたことになります。 q = i / 100; して r = i - ((q << 6) + (q << 5) + (q << 2)); すると、r は i の下2桁になるわけです。

ちなみにDigitOnesとDigitTensの値はこんな感じです。

これに0～99の値を添え字として渡せば、それぞれ10の桁と1の桁の値をchar型にしたものが返ってきます。

// 0～99までの値が渡された場合に、1の位の数字を文字列にしたものを返す為の子
// 例えば34を渡せば「4」を返してくれる
final static char [] DigitTens = {
  '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
  '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
  '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
  '3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
  '4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
  '5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
  '6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
  '7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
  '8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
  '9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
} ; 

// 0～99までの値が渡された場合に、1の位の数字を文字列にしたものを返す為の子
// 例えば34を渡せば「4」を返してくれる
final static char [] DigitOnes = { 
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
} ;

q = i / 100;
r = i - ((q << 6) + (q << 5) + (q << 2));

この処理で、どうして i の下2桁が取れるのでしょう。

100は2進数にすると「1100100」。つまり、0オリジンで考えて、6, 5, 2の場所に1がいます。それだけシフトするということは、100を掛けるということと同義になります。

試しにこんな処理を流してみましょう。

6, 5, 2分シフトした値と、100を掛けた値を比較しています。これを実行すると、100個 true が出力されます。

for( int q = 100; q < 200; q++ ) {
  System.out.println( 
    ((q << 6) + (q << 5) + (q << 2)) == q * 100
  );
}

ということで

q = i / 100;
r = i - ((q << 6) + (q << 5) + (q << 2));

は、

q = i / 100;
r = i - q * 100;

と同義ということになります。10進数で3桁の掛け算する時と概念的には一緒ですよね。

ちなみに同様の方法で他の数字を掛けることもできます。試しに20（10100）を掛けてみましょう。2進数を見ると、4, 2シフトすれば良いことが分かります。

/** 10 × 20 的な処理 */
int i = 10;
i = ( i << 4 ) + ( i << 2 );
System.out.println( i );
  // => 200

/** 31 * 20 的な処理 */
i = 31;
i = ( i << 4 ) + ( i << 2 );
System.out.println( i );
  // => 620

そんなわけで、getCharsの5～8行目の処理は、intに対して100で割って100を掛け、それを元の値から引くことによって、下2桁を抽出しているという、それほど不可思議でもない処理ということでした。

要点だけ追ってみる(getCharsの15～22行目)

16:  for (;;) { 
17:    q = (i * 52429) >>> (16+3);
18:    r = i - ((q << 3) + (q << 1));
19:    buf [--charPos] = digits [r];
20:    i = q;
21:    if (i == 0) break;
22:  }

final static char[] digits = {
  '0' , '1' , '2' , '3' , '4' , '5' ,
  '6' , '7' , '8' , '9' , 'a' , 'b' ,
  'c' , 'd' , 'e' , 'f' , 'g' , 'h' ,
  'i' , 'j' , 'k' , 'l' , 'm' , 'n' ,
  'o' , 'p' , 'q' , 'r' , 's' , 't' ,
  'u' , 'v' , 'w' , 'x' , 'y' , 'z'
};

さて、先回の処理で、現在、ここに来ている値は65536未満ということになっています。

今回の処理は、19行目を見ると、digits から添え字 r の値を抜いてきています。digitsは数値に対して単純に0～zまでを振った値です。ので、r の値は 0 ～ 9 がいることが想像できます。

つまり、

q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1));

をすると、65536未満の数値において、下1桁を取り出せるということになります。

まずは分かり易い18行目から見てみましょう。

10は2進数で現すと1010になります。ということは、先ほど100を掛ける為に6, 5, 2でシフトしていたのと同じように、この処理は3, 1シフトすることで10を掛けているだけだということが分かります。

このことから、なんとなく q = (i * 52429) >>> (16+3); は 10で割る処理と同義なんじゃないかといういことが想像できたりします。試しにやってみると、こんな感じになります。

int i = 920;
System.out.println( (i * 52429) >>> (16+3) );
  // => 92

i = 611;
System.out.println( (i * 52429) >>> (16+3) );
  // => 61

それっぽいですね。

16+3、つまり「19」シフトするということは、2の19乗は「524288」なので、「524288」で割るのとほぼ同義になります。

書き換えると、こんな感じになります。

( i * 52429 ) / 524288

52429 を掛けて、524288で割ったら、たいていの数は、10で割ったのと同値になります。

具体的には、40959までOKです。40960まで行くと52429を掛けた時に、一番左のビットが1になる為、負の数になってしまいます。

System.out.println( 40960 * 52429 );
// => -2147475456

と、40960がNGだと、前の処理で「65536以下になるまで処理する」と言ってるのと合いませんね。

そこは

( i * 52429 ) / 524288

と

( i * 52429 ) >>> 19

の違いが現れる部分でした。

除算をする場合は、一番左のビットが1になっていれば負の数として扱いますが、「>>>」でシフトする場合は0でも1でも同じように扱います。

その為、シフトを使えば除算をするより1ビット分多く余裕ができます。ちなみに「>>」だと一番左側のビットによって結果が変わるのでNGです。

ということで、 ( i * 52429 ) >>> 19 の場合は、倍の81919までは溢れません。その為、getCharsの9～15行目のところで、65536まで処理をしていました。

やたらと説明が長くなってしまいましたが、これだけ書いて、結局処理的には「10で割って、10を掛けて、元の値から引くことで、1の位を算出してます」というだけの話でした。結論にしてしまうとえらく単純ですね。

コードにすると、これとだいたい同じ意味。

16:  for (;;) { 
17:    q = i / 10;
18:    r = i - ( i * 10 );
19:    buf [--charPos] = digits [r];
20:    i = q;
21:    if (i == 0) break;
22:  }

要点だけ追ってみる(getCharsの23～25行目)

23:  if (sign != 0) {
24:    buf [--charPos] = sign;
25:  }

ここは説明するまでもないようなところですね。

最初に負数だったら云々で判定しておいた変数「sign」を見て、マイナスが入っていたら、bufの先頭にマイナスを突っ込んでます。

ということで、途中で脱線してしまい何を処理していたのか説明している本人もよく分からなくなりましたが、以上の処理を持ちまして、めでたくintがStringに変換されたようです。めでたし、めでたし。

総評

今回は長かったので、ピコーンが無いまま淡々とした説明になってしまいました。残念。

そういえば、中の人のコメントに「x * 52429もshift-addにしようぜ」とか書いてありました。shift-addにするとけっこう性能差出たりするようです。

/** 10を掛けた場合の実行時間 : 平均403ミリ秒 */
long start = System.nanoTime();
int len = Integer.MAX_VALUE / 10;
for( int i = 0; i < len; i++ ) {
  int x = i * 10;
}
System.out.println( System.nanoTime() - start );

/** シフトを使った場合の実行時間 : 平均296ミリ秒 */
long start = System.nanoTime();
int len = Integer.MAX_VALUE / 10;
for( int i = 0; i < len; i++ ) {
  int x = ((i << 3) + (i << 1));
}
System.out.println( System.nanoTime() - start );

空ループを回した場合のコストが200ミリ秒弱なので、我が家のPCでは乗算の場合とシフトの場合で倍以上のコストの差が出ている感じになりました。

10億レコードに対して乗算して回る時なんかに是非使ってみたいロジックですね。

Integer.toString( int )の動作例