1. 前言
在Integer類的源碼中液斜，toString方法中調(diào)用getChars方法累贤，getChars方法是獲取數(shù)值對(duì)應(yīng)的字符串，其中有兩個(gè)地方使用了非常巧妙的方式來進(jìn)行除法運(yùn)算和取余運(yùn)算少漆。在計(jì)算機(jī)中臼膏，a/b 和 a%b相比較位運(yùn)算，都是比較費(fèi)時(shí)的計(jì)算的示损。下面來看看jdk中是如何優(yōu)化計(jì)算的
2. 源碼
先lo代碼:
// 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 <= 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;
}
思路是這樣：
當(dāng) i >= 65536時(shí)渗磅，是每?jī)晌蝗〕鰯?shù)字，i /= 100检访，例如 i = 567235474始鱼，
（1）先取最后兩位 7 和 4 放入buf數(shù)組中，i = 5672354脆贵，buf = { , , , , , , , '7', '4'};
（2）再取最后兩位 5 和 4 放入buf數(shù)組中医清，i = 56723，buf = { , , , , , '5', '4', '7', '4'};
當(dāng) i < 65536 時(shí)卖氨，跳出循環(huán)状勤，采用每一次取出一位數(shù)字，也就是 i /= 10
（3）取最后一位 3 放入buf數(shù)組中双泪，i = 5672持搜，buf = { , , , , '3', '5', '4', '7', '4'};
（4）取最后一位 2 放入buf數(shù)組中，i = 567焙矛，buf = { , , , '2', '3', '5', '4', '7', '4'};
（5）取最后一位 7 放入buf數(shù)組中葫盼，i = 56，buf = { , , '7', '2', '3', '5', '4', '7', '4'};
（6）取最后一位 6 放入buf數(shù)組中村斟，i = 5贫导，buf = { , '6', '7', '2', '3', '5', '4', '7', '4'};
（7）取最后一位 5 放入buf數(shù)組中，i = 0蟆盹，buf = { '5', '6', '7', '2', '3', '5', '4', '7', '4'}孩灯，結(jié)束。
但在jdk中逾滥，并不都是直接用 a/b 除法 和 a%c 取余來獲取 商 和 余數(shù)的
- 對(duì)100除法：q = i / 100峰档，直接除法
- 對(duì)100取余：r = i - ((q << 6) + (q << 5) + (q << 2));
推導(dǎo)如下：
? ? ? ?r = i - (q * 100)
? ? ? ?r = i - (q * 64 + q * 32 + q * 4)
? ? ? ?r = i - ((q << 6) + (q << 5) + (q << 2)) - 對(duì)10除法：q = (i * 52429) >>> (16+3);
推導(dǎo)如下：
? ? ? ?2 >>> 19 為 524288，
? ? ? ?q = (52429i) / 524288 = (52428.8i + 0.2i) >>> (16+3)寨昙，
i 拆分為兩部分讥巡，i = a * 10 + b（保證a, b 均為正數(shù)，且 0 <= b <= 9舔哪，
? ? ? ?q = ((10a+b) * 52428.8 + 0.2b) >>> 19
? ? ? ?q = (524288a + 52428.8b + 0.2i) >>> 19
其中欢顷，
? ? ? ?52428.8b 最大值為52428.8 * 9， 0.2i 最大值為 13107.2
所以捉蚤，
? ? ? ?52428.8b + 0.2i 最大值為 484966.4抬驴， 小于 524288 (1 >>> 19), 對(duì)應(yīng)二進(jìn)制會(huì)被右移掉
所以炼七，
? ? ? ? q = (a * 524288) >>> 19 + (52428.8 * b + i * 0.2) >>>19 = (a*524288) >>> 524288 = a - 對(duì)10取余：r = i - ((q << 3) + (q << 1));
推導(dǎo)如下：
? ? ? ?r = i - (q * 10)
? ? ? ?r = i - (q * 8 + q * 2)
? ? ? ?r = i - ((q << 3 + q << 1)
后言
是不是很有意思，以后除法或者是取余運(yùn)算布持，你還只是會(huì)用 “/”, “%”了嗎
其他
本人也是在慢慢學(xué)習(xí)中豌拙，如有錯(cuò)誤還請(qǐng)?jiān)彙⒕凑?qǐng)指出鳖链，謝謝姆蘸！
