1. 应用：将整形数字转换成对应的十进制字符串
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);
}
2. 测试代码
public static void main(String[] args) {
System.out.println(Integer.toString(-2147483647));
System.out.println(Integer.toString(2147483647));
System.out.println(Integer.toString(66580));
}
执行结果：
-2147483647
2147483647
66580
3. 源码分析： getChars(int i, int index, char[] buf)
- 源码
/**
* Places characters representing the integer i into the
* character array buf. The characters are placed into
* the buffer backwards starting with the least significant
* digit at the specified index (exclusive), and working
* backwards from there.
*
* Will fail if i == Integer.MIN_VALUE
*/
static void getChars(int i, int index, char[] buf) {
// 代码段1
int q, r;
int charPos = index;
char sign = 0;
if (i < 0) {
sign = '-';
i = -i;
}
// 代码段2
// 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];
}
// 代码段3
// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
for (;;) {
q = (i * 52429) >>> (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;
}
}
- 此方法作用将int数字转换放进一个字符数组
- 在数字为int最小值时，此方法会失败
以上是此方法注释的内容，源码主要是将数字i转换为字符串，方法有三段组成。 - 代码段1主要判断i的正负，并对负数取反，方便处理。这里也解释了为什么当i为最小数字时方法失败，因为int范围是-2147483648~2147483647，当其取反时超过了int的范围。
- 代码段2是处理i>=65536时，每次取数字i的最后两位转为字符
while (i >= 65536) {
q = i / 100;
// really: r = i - (q * 100);
r = i - ((q << 6) + (q << 5) + (q << 2));
i = q;
//取DigitOnes[r]的目的其实取数字r%10的结果
buf [--charPos] = DigitOnes[r];
//取DigitTens[r]的目的其实是取数字r/10的结果
buf [--charPos] = DigitTens[r];
}
这个代码很简单，我们看懂两个地方就行了。
- a. r = i - ((q << 6) + (q << 5) + (q << 2)); 实际上去 i - q*100，得到r是i的最后两位
- b. buf [--charPos] = DigitOnes[r]; buf [--charPos] = DigitTens[r];巧妙的运用两个数组查找，避免除法等计算。
- 代码段3是处理i<65536时每次取一位转为字符
for (;;) {
//这里其实就是除以10。取数52429和16+3的原因在后文分析。
q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
//将数字i的最后一位存入字符数组，
buf [--charPos] = digits [r];
i = q;
//for循环结束后，buf内容为“12345678”；
if (i == 0) break;
}
这个代码我们需要知道
- a. q = (i * 52429) >>> (16+3) 约等于 i/10
- b. r = i - ((q << 3) + (q << 1))，其实是r = i - q*10, 所以r其实是i的最后一位，然后放进字符数组
但是这里我们肯定会有一些疑惑：
问题1：为什么是65536，为什么要在大于等于65536时和小于65536时采用不同的处理方法。
问题2：代码段3中 q = (i * 52429) >>> (16+3);中52439,16+3是怎么确定出来的
num1 = 65536, num2 = 52429, num3 = 19
在了解这num1,num2,num3为什么是这三个数字之前，我们有几个需要了解的前提：
1.移位效率高于乘除
2.乘法效率高于除法
这时我们注意到，代码段2里采用了除法和移位，代码段3里采用了乘法和移位。理论上我们如果都是用代码段3进行处理效率会更高，但是注意到代码段3有这样一个操作是需要我们学习的。
q = (i * 52429) >>> (16+3); // 约等于i/10，这里巧妙的运用了乘法和移位避免使用除法来提高效率。
这里巧妙的运用了乘法和移位避免使用除法来提高效率，但是同时也要求(i * 52429)不能超过整形的范围。有符号整形是-2147483648至2147483647，无符号是0-4,294,967,296（2^32），由于后面的计算是采用无符号右移，所以我们只需要使得(i * 52429)不超过232就可以了。所以说这里的i理论上是不能超过232除以52429，这就解释了为什么要分i>=num1和i<num1来处理。
好，这样也就解释了num1,num2,num3这三个数的来历。那怎么确定这三个数的值，我们需要进行一些计算。由于q = (i * 52429) >>> (16+3); // 约等于i/10，所以我们得出num2/2^num3=0.1 => num2=2^num3/10
最终num2=2^num3/10+1，最后的+1应该是未了再计算的时候避免被向下取整了吧。这里我有一个测试代码证明了这个猜想
public static void main(String[] args) {
System.out.println((1020 * 52428) >>> (16+3)); // 理论上精确的除以10，在计算机计算过程中可能会产生向下取整导致结果不准确的问题
System.out.println((1020 * 52429) >>> (16+3)); // 改进版
}
运行结果
101
102
回到主题，根据以上关系我们可以得出多组num2,num3
2^10=1024, 103/1024=0.1005859375
2^11=2048, 205/2048=0.10009765625
2^12=4096, 410/4096=0.10009765625
2^13=8192, 820/8192=0.10009765625
2^14=16384, 1639/16384=0.10003662109375
2^15=32768, 3277/32768=0.100006103515625
2^16=65536, 6554/65536=0.100006103515625
2^17=131072, 13108/131072=0.100006103515625
2^18=262144, 26215/262144=0.10000228881835938
2^19=524288, 52429/524288=0.10000038146972656
2^20=1048576, 104858/1048576=0.1000003815
2^21=2097152, 209716/2097152 = 0.1000003815
2^22= 4194304, 419431/4194304= 0.1000001431
2^23= 8388608, 838861/8388608= 0.1000000238
...
接下来其实有一个临界值((num1-1)num2) >>> num3,需要保证((num1-1)num2) 不能超过2^32。所以就是num1越大，num2就越小；num2越大，num1就越小。但同时这里我们有两个诉求：
- 由于上面是约等于i/10,所以我们得对精度有要求。精度必须保证，可以得出num2和num3越大，精度就越高
- 因为乘法小于高于除法，我们偏向于num1越大越好，这样尽量多使用代码段3
从上面两个诉求来看，我们的num1,num2,num3都是越大越好。但是((num1-1)*num2) 不能超过2^32也告诉了我们num1和num2一个大了另一个就得小。所以采取折中的方式，精度足够了就好，乘除法效率上我们也妥协一些。
我们发现，当num3=19时，精度达到了0.10000038146972656，0.1后面是5个0，我们称精度达到了5，这个精度可以说符合要求了已经。并且当num3=20,21,22时精度都保持在5，此时提升num3和num2对精度并没有提升。所以num3我们选择了19, num2也顺理成章为52429， 在2^15 和 2^16之间。同时((num1-1)*num2) 不能超过232，所以num1选择了216。
这里笔者要吐槽一下网上对于这三个值的一些解释，自己都不能说服自己
- 下面这种说法真真看不懂，可能是我没理解到位，下一个精度较高的组合是419431和22。当num值为19,20,21,22时的精度不是一样高的吗，为什么下一个是22。 另外“231/222 = 2^9 = 512。512这个数字实在是太小了”实在是看不懂啊。
52429/524288=0.10000038146972656精度足够高
下一个精度较高的m和n的组合是419431和22。2^31/2^22 = 2^9 = 512。512这个数字实在是太小了。65536正好是2^16，一个整数占4个字节。65536正好占了2个字节，选定这样一个数字有利于CPU访问数据。
- 下面这种说法更是可笑，你说不超出整形范围内值得是((num1-1)*num2)不超过吧。你这么说应该是已经认定了num1=65536，可是num1,num2,num3这三个值的确定本就是互相影响，互相确定的。 你这么说是在num1=65536的大前提下的，可是num1的值时怎么确定的呢，对吧？
至于为什么选择2的19次方524288，是因为52429/524288得到的数字精度在不超出整形范围内，精度是最高的。
4. 对两个数组的解释
100以下的数，DigitTens十位数上的数字，DigitOnes为个位数的数字，如86 ＝DigitTens[86]+ DigitOnes[86] = '8' + '6' = 86
比较巧妙的设计
//100以内的数字除以10的结果（取整）
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',
} ;
//100以内的数字对10取模的结果
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',
} ;
5. 从这个方法我们学到的
- 乘法比除法高效：q = ( i * 52429) >>> (16+3); => 约等于q0.1,但i52429是整数乘法器，结合位移避免除法
- 充分利用计算结果:在获取r(i%100)时，充分利用了除法的结果，结合位移避免重复计算
- 位移比乘法高效:r = i – (( q << 6) + ( q << 5) + ( q << 2)); = >等价于r = i – (q * 100)
- 局部性原理之空间局部性
(1).buf[–charPos] =DigitOnes[r];buf[–charPos] =DigitTens[r];通过查找数组，实现快速访问,避免除法计算
(2).buf [–charPos ] = digits [ r];
作者 @没有故事的老大爷
奋斗，但是该不该知足，该不该休息呢？
