登录 注册

jdk 源码：Integer.getChars(int i, int index, char[] buf)

本贴最后更新于 2047 天前，其中的信息可能已经水流花落

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;
        }
    }
  1. 此方法作用将 int 数字转换放进一个字符数组
  2. 在数字为 int 最小值时，此方法会失败
    以上是此方法注释的内容，源码主要是讲数字 i 转换为字符串，方法有三段组成。
  3. 代码段 1 主要判断 i 的正负，并对负数取反，方便处理。这里也解释了为什么当 i 为最小数字时方法失败，因为 int 范围是-2147483648~2147483647，当其取反时超过了 int 的范围。
  4. 代码段 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];巧妙的运用两个数组查找，避免除法等计算。
  1. 代码段 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 就越小。但同时这里我们有两个诉求：

  1. 由于上面是约等于 i/10,所以我们得对精度有要求。精度必须保证，可以得出 num2 和 num3 越大，精度就越高
  2. 因为乘法小于高于除法，我们偏向于 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。

这里笔者要吐槽一下网上对于这三个值的一些解释，自己都不能说服自己

  1. 下面这种说法真真看不懂，可能是我没理解到位，下一个精度较高的组合是 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访问数据。
  1. 下面这种说法更是可笑，你说不超出整形范围内值得是((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];

作者 @ 没有故事的老大爷
奋斗，但是该不该知足，该不该休息呢？

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3169 引用 • 8207 回帖
昆明 位置
585 4 89 122 68 36 1 33 223

相关帖子

回帖
jdk 源码：Integer.getChars(int i, int index, char[] buf)

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
Maggie
昆明
回帖
0
 帖子
16
 积分
510