Netease javaインタビューの質問、itoa、整数から文字列

Netease Java Interview Questions

非常に簡単な質問です。整数を文字列に変換するitoaプログラムを手書きします。インタビューを終えた後、私は電話を切りました。

自分で書いたコードは理論的には機能を実現できますが、脆弱性（最小の負の整数のマイナス後のオーバーフロー、公式のソースコードが最小の負の整数の結果を直接返すなど）があり、パフォーマンスが非常に低く、文字列+の追加が使用されます。 。 。

Integer.toString（）の実装を見に戻ったところ、思っていたものとはかけ離れていることがわかりました。単純な％10、/ 10、+ '0'などの操作だけでなく、これらの操作がまったく表示されないこともあります。

公式の％はありませんが、変位計算で実現しており、計算効率を最大化するために、数値の上位16ビットと下位16ビットの処理方法が異なります。

最初に除算を計算してから、減算を使用して余りを見つけ、％と/の繰り返し操作を回避します。

0〜9の整数から文字への変換は、n + '0'ではありませんが、静的定数配列マッピングを使用して変換を完了し、頻繁な加算計算を回避します。 （数値が2の16乗マイナス1より大きい場合、2桁が同時に変換され、0〜99は、2つの配列（1桁のマッピングテーブルと10桁のマッピング）を使用して2文字にマッピングされます。テーブル）

q = (i * 52429) >>> (16+3)

これは最も醜いコード行であり、実際にはq = q / 10操作を完了します。

符号なしは19ビット右にシフトされます。これは/ 524288に相当しますが、524290ではありませんが524290.0 / 524288 = 0.1000003814697..。65536未満の正の整数の計算誤差が0.1を超えないようにするには、小数点以下6桁の精度で十分です。乗算と右シフトも、直接除算するよりも効率的です。

以下は、Integer.toString（）に関連するすべてのソースコードです。

public static String toString(int i) { if (i == Integer.MIN_VALUE) return '-2147483648' int size = (i <0) ? stringSize(-i) + 1 : stringSize(i) char[] buf = new char[size] getChars(i, size, buf) return new String(buf, true) } static int stringSize(int x) { for (int i=0 i++) if (x <= sizeTable[i]) return i+1 }
static void getChars(int i, int index, char[] buf) { int q, r int charPos = index char sign = 0 if (i <0) { sign = '-' i = -i } // Generate two digits per iteration while (i>= 65536) { q = i / 100 // really: r = i - (q * 100) r = i - ((q << 6) + (q << 5) + (q << 2)) i = q buf [--charPos] = DigitOnes[r] buf [--charPos] = DigitTens[r] } // Fall thru to fast mode for smaller numbers // assert(i>> (16+3) r = i - ((q << 3) + (q << 1)) // r = i-(q*10) ... buf [--charPos] = digits [r] i = q if (i == 0) break } if (sign != 0) { buf [--charPos] = sign } }
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' } 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', } 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', }

|_+_|