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)不超过 2^32 就可以了。所以说这里的 i 理论上是不能超过 2^32 除以 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) 不能超过 2^32,所以 num1 选择了 2^16。
这里笔者要吐槽一下网上对于这三个值的一些解释,自己都不能说服自己
- 下面这种说法真真看不懂,可能是我没理解到位,下一个精度较高的组合是 419431 和 22。当 num 值为 19,20,21,22 时的精度不是一样高的吗,为什么下一个是 22。 另外**“2^31/2^22 = 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];
作者 @ 没有故事的老大爷
奋斗,但是该不该知足,该不该休息呢?
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于