fastjson深度源码解析-IOUtils.getChars
getChars(i, size, buf);那么接下来就深入理解一下getChars方法。这部分我把关于这段代码的分析直接写到注释中，便于结合代码理解。
static void getChars(int i, int index, char[] buf) {
int q, r;
int charPos = index;
char sign = 0;
if (i < 0) {
sign = '-';
i = -i;
}
// 每次循环过后，都会将i中的走后两位保存到字符数组buf中的最后两位中，读者可以将数字i设置为12345678测试一下，
//第一次循环结束之后，buf[7] = 8,buf[6]=7。第二次循环结束之后，buf[5] = 6,buf[4] = 5。
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];
}
// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
//循环将其他数字存入字符数组中空余位置
for (;;) {
//这里其实就是除以10。取数52429和16+3的原因在后文分析。
q = (i * 52429) >>> (16+3);
// r = i-(q*10) ...
r = i - ((q << 3) + (q << 1));
//将数字i的最后一位存入字符数组，
//还是12345678那个例子，这个for循环第一次结束后，buf[3]=4。
buf [--charPos] = digits [r];
i = q;
//for循环结束后，buf内容为“12345678”；
if (i == 0) break;
}
if (sign != 0) {
buf [--charPos] = sign;
}
}
//其中用到的几个数组
//100以内的数字除以10的结果（取整），
//比如取DigitTens[78]，返回的是数字7
//只要是70-79的数字，返回的都是7，依次类推，所以总结出规律，其实就是返回的对应数字除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取模的结果，
//比如取DigitTens[78]，返回的8
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',
} ;
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'
};接下来分析两个问题：
问题一、为什么在getChars方法中，将整型数字写入到字符数组的过程中为什么按照数字65536分成了两部分呢？这个65535是怎么来的？
部分一
while (i >= num1) {
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 <= 65536, i);
for (;;) {
q = (i * num2) >>> (num3);
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
buf [--charPos] = digits [r];
i = q;
if (i == 0) break;
}使用num1,num2,num3三个变量代替源代码中的数字，便于后面分析使用。
问题二、在上面两段代码的部分二中，在对i进行除十操作的过程中为什么选择先乘以52429在向右移位19位。其中52429和19是怎么来的？
解答
回答上面两个问题之前，首先要明确两点：
移位的效率比直接乘除的效率要高
乘法的效率比除法的效率要高先理解以下代码：
r = i - ((q << 6) + (q << 5) + (q << 2));表示的其实是r = i - (q * 100);，i-q*2^6 - q*2^5 - q*2^2 = i-64q-32q-4q = i-100q。
q = (i * num2) >>> (num3);中，>>>表示无符号向右移位。代表的意义就是除以2^num3。 所以q = (i * 52429) >>> (16+3); 可以理解为：q = (i * 52429) / 524288;,那么就相当于 q= i * 0.1也就是q=i/10，这样通过乘法和向右以为的组合的形式代替了除法，能提高效率。
再来回答上面两个问题中，部分一和部分二中最大的区别就是部分一代码使用了除法，第二部分只使用了乘法和移位。因为乘法和移位的效率都要比除法高，所以第二部分单独使用了乘法加移位的方式来提高效率。那么为什么不都使用乘法加移位的形式呢？为什么大于num1(65536)的数字要使用除法呢？原因是int型变量最大不能超过(2^31-1)。如果使用一个太大的数字进行乘法加移位运算很容易导致溢出。那么为什么是65536这个数字呢？第二阶段用到的乘法的数字和移位的位数又是怎么来的呢？
我们再回答第二个问题。
既然我们要使用q = (i * num2) >>> (num3);的形式使用乘法和移位代替除法，那么n和m就要有这样的关系：
num2= (2^num3 /10 +1)只有这样才能保证(i * num2) >>> (num3)结果接近于0.1。
那么52429这个数是怎么来的呢?来看以下数据：
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超过22的数字我就不列举了，因为如果num3越大，就会要求i比较小，因为必须保证(i * num2) >>> (num3)的过程不会因为溢出而导致数据不准确。那么是怎么敲定num1=65536,num2= 524288, num3=19的呢？ 这三个数字之间是有这样一个操作的：
（num1* num2）>>> num3因为要保证该操作不能因为溢出导致数据不准确，所以num1和num2就相互约束。两个数的乘积是有一定范围的，不成超过这个范围，所以，num1增大，num2就要随之减小。
我觉得有以下几个原因：
1.52429/524288=0.10000038146972656精度足够高。
2.下一个精度较高的num2和num3的组合是419431和22。2^31/2^22 = 2^9 = 512。512这个数字实在是太小了。
65536正好是2^16，一个整数占4个字节。65536正好占了2个字节，选定这样一个数字有利于CPU访问数据。不知道有没有人发现，其实65536* 52429是超过了int的最大值的，一旦超过就要溢出，那么为什么还能保证（num1* num2）>>> num3能得到正确的结果呢？
这和>>>有关，因为>>>表示无符号右移，他会在忽略符号位，空位都以0补齐。
一个有符号的整数能表示的范围是-2147483648至2147483647，但是无符号的整数能表示的范围就是0-4,294,967,296（2^32），所以，只要保证num2*num3的值不超过2^32次方就可以了。65536是2^16,52429正好小于2^16,所以，他们的乘积在无符号向右移位就能保证数字的准确性。
getChars使用了的体系结构知识：
1.乘法比除法高效：q = ( i * 52429) >>> (16+3); => 约等于q0.1,但i52429是整数乘法器，结合位移避免除法。
2.重复利用计算结果:在获取r(i%100)时，充分利用了除法的结果，结合位移避免重复计算。
3.位移比乘法高效:r = i – (( q << 6) + ( q << 5) + ( q << 2)); = >等价于r = i – (q * 100);
4.局部性原理之空间局部性
(1).buf[–charPos] =DigitOnes[r];buf[–charPos] =DigitTens[r];通过查找数组，实现快速访问,避免除法计算
(2).buf [–charPos ] = digits [ r];
京公网安备 11010502036488号