以下为个人理解,若有错误请谅解!!!
JAVA中整数除10的骚操作?
源码:
// java.lang.Integer#getChars
// assert(i <= 65536, i);
for (;;) {
// 精彩之处:为什么是52429,为什么用>>>而不是>>
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;
}
前提信息
2的n次方除数信息:
// 2 * n = 2^n, ((2 ^ n) / 10 ) / 2 ^ n)
2^10=1024.0, 102/1024.0=0.099609375
2^11=2048.0, 205/2048.0=0.10009765625
2^12=4096.0, 410/4096.0=0.10009765625
2^13=8192.0, 819/8192.0=0.0999755859375
2^14=16384.0, 1638/16384.0=0.0999755859375
2^15=32768.0, 3277/32768.0=0.100006103515625
2^16=65536.0, 6554/65536.0=0.100006103515625
2^17=131072.0, 13107/131072.0=0.09999847412109375
2^18=262144.0, 26214/262144.0=0.09999847412109375
2^19=524288.0, 52429/524288.0=0.10000038146972656
2^20=1048576.0, 104858/1048576.0=0.10000038146972656
2^21=2097152.0, 209715/2097152.0=0.09999990463256836
2^22=4194304.0, 419430/4194304.0=0.09999990463256836
2^23=8388608.0, 838861/8388608.0=0.10000002384185791
2^24=1.6777216E7, 1677722/1.6777216E7=0.10000002384185791
2^25=3.3554432E7, 3355443/3.3554432E7=0.09999999403953552
2^26=6.7108864E7, 6710886/6.7108864E7=0.09999999403953552
2^27=1.34217728E8, 13421773/1.34217728E8=0.10000000149011612
2^28=2.68435456E8, 26843546/2.68435456E8=0.10000000149011612
2^29=5.36870912E8, 53687091/5.36870912E8=0.09999999962747097
2^30=1.073741824E9, 107374182/1.073741824E9=0.09999999962747097
2^31=2.147483648E9, 214748365/2.147483648E9=0.10000000009313226
原因分析
- double转int是直接忽略小数位数的
(int)1.9 // 结果是1
- 为什么不使用其他的指数值?
- 211(212),根据1后面0的个数,大致只能处理1000一下的数字
- 215、216原因同上
- 223(224),1后面的0更多,为什么不用?int数值加上符号为最多32位,如果使用这两个数值被除数的空间范围就会变得很小
- 227、228、229原因同上
- 真实原因:
- 源码中注释错误,i < 66536,而不是<=(这一点很重要!)
- 65535是16位(1111,1111,1111,1111),这就要求与他相乘的数字最大也要小于65536(216,17位)!! !
衍生骚操作
- 那么这个想用这种除十骚操作的最大值是多少呢?
- 答: 81919
原因:
// int最大值是s^31 - 1, 用(2^32 - 1) / 52429就得出这个结果了
((Integer.MAX_VALUE + 1L) * 2L - 1) / 52429
// 结果是81919
```