自己动手实现 parseInt 与Java Integer.parseInt 源码分析

[Shellbye]

Integer.parseInt 应该算是 Java 中比较常见常用的方法了。本文准备在自己实现的基础之上，逐步分析 Java 源码的实现。

自己动手的第一版

字符串转数字，其原理其实并不复杂，基本上没有太多开发经验的同学也可以写出如下一个简单的实现

    public static int myParseInt(String s, int radix) {
        int result = 0;
        int i = 0;
        int len = s.length();
        while (i < len) {
            int c = (int)s.charAt(len - i - 1) - '0'; // 这里只能处理二、八、十进制
            System.out.println(c);
            double a = c * Math.pow(radix, i);
            result += (int) a;
            i++;
        }
        System.out.println(result);
        return result;
    }

这是一版完全从数学原理角度的实现，基本上没有任何的优化，所以就不多说了。这里需要注意是 while 循环里的第一行，即字符到数字的转换，利用的是当前字符在 ascii 码表中距离 0 的距离来计算的，所以一个潜在的限制就是只能处理二、八、十进制。

自己动手的第二版——不使用指数运算

在第一版中，有一个计算量比较大的地方，就是其中的指数运算，在第二版中，我们通过调整处理的方向，把指数运算优化为乘法运算

    public static int myParseInt(String s, int radix) {
        int result = 0;
        int i = 0;
        int len = s.length();
        while (i < len) {
            int c = (int)s.charAt(i) - '0'; // 这里只能处理二、八、十进制
            System.out.println(c);
            result *= radix;
            result += c;
            i++;
        }
        System.out.println(result);
        return result;
    }

相比于第一版从低位开始处理，在第二版中，我们从高位开始处理，每次先乘以基数，相当于把 result 左移，然后在加上新增的低位数，这样就避免了开销比较大的指数运算。

考虑高于十进制的情况

上面基本上完成了字符串转数字的核心模块，接下来就考虑遗留的进制限制的问题。首先分析这个问题的根源，是因为我们利用了 ascii 码表中各个数字距离 0 的距离来将字符转为了整数，从如下 ascii 码表中我们看出，字母距离 0 之间的距离，是不能直接转换的，因为中间隔了 7 个其他字符，所以需要一些特殊处理。

    public static int char2Number(char c) {
        int dis = (int)c - '0';
        if (dis > 9) {
            dis -= 7;
        }
        return dis;
    }

这里还有一个潜在的坑，就是字母在使用的之前需要转成大写，因为我们刚才的分析中，针对的是大写字母，小写字母的距离又是另一回事儿了，所以要全部转为大写再转换，新的代码如下

    public static int myParseInt(String s, int radix) {
        s = s.toUpperCase();
        int result = 0;
        int i = 0;
        int len = s.length();
        while (i < len) {
            int c = char2Number(s.charAt(i));
            System.out.println(c);
            result *= radix;
            result += c;
            i++;
        }
        System.out.println(result);
        return result;
    }

对输入的检查——进制不符

上面我们并没有对用户的输入做任何的检查，假设有如下用户输入，

myParseInt("1A", 10);

我们应该是报错的，因为用户输入的进制基数和字符串是不符的，但是我们目前的程序却会输出 20 ， 这显然是不对的，因为我们在程序内部并没有在处理的过程中检查每一个字符转换之后和进制基数的关系。改进版本如下

    public static int char2Number(char c) {
        int dis = (int)c - '0';
        if (dis > 9) {
            dis -= 7;
        }
        return dis;
    }

    public static int myParseInt(String s, int radix) throws Exception {
        s = s.toUpperCase();
        int result = 0;
        int i = 0;
        int len = s.length();
        while (i < len) {
            int c = char2Number(s.charAt(i));
            if (c >= radix)
                throw new Exception(String.format("wrong input %s for radix: %s", s.charAt(i), radix));
            System.out.println(c);
            result *= radix;
            result += c;
            i++;
        }
        System.out.println(result);
        return result;
    }

对第一位可能的符号位的处理

到目前为止，我们都是把输入当作无符号的数也就是正数来处理的，这显然是有问题的，因为输入的第一位可能是一个符号位，不能直接当数值位来处理。所以要先判断第一位。

    public static int char2Number(char c) {
        int dis = (int)c - '0';
        if (dis > 9) {
            dis -= 7;
        }
        return dis;
    }

    public static int myParseInt(String s, int radix) throws Exception {
        s = s.toUpperCase();
        int result = 0;
        int i = 0;
        int len = s.length();
        boolean neg = false;

        char firstChar = s.charAt(0);
        if (firstChar == '-') {
            neg = true;
            i++;
        } else if (firstChar == '+') {
            i++;
        }
        while (i < len) {
            int c = char2Number(s.charAt(i));
            if (c >= radix)
                throw new Exception(String.format("wrong input %s for radix: %s", s.charAt(i), radix));
            result *= radix;
            result += c;
            i++;
        }
        return neg ? -result : result;
    }

一些其他问题

到目前为止，一个基本可用的字符串转整型的方法就完成了，但是它还是不完美的，还有以下一些问题需要考虑：

1. 对 2147483648即越界数字的处理；
   为什么要特殊处理 2147483648 呢？因为它其实是越界了，超过了 int 的最大值，而我们目前的程序 会返回 -2147483648。 针对这个情况，Java 源码（见后）的处理方式是先按照负数去处理，因为负数的最大值是 -2147483648 ，而正数最大值是 2147483647。对于其他更大的数字，则需要在转换的过程中逐步判断，发现大于 int 的最大值就抛出异常。
2. 对输入进制的限制；
   我们目前的思考，都是针对输入的字符进行的，但是因为输入的进制基数 radix 也是用户输入的，也是需要进行判断处理的，不能默认一定是正确的。比如因为英文字母只有 26 个，所以我们这里的最多也能处理到 36 进制，所以就不允许输入大于这个值的进制基数了。
3. 对输入字符串中非法字符的处理；
   我们上面的算法中，利用了字符在 ascii 码表中与 0 的距离来进行转换，但是这种转换缺乏对待转换字符的校验，所以会出现以下问题：

myParseInt("1:", 10); // 输出 13

这个问题的出现是因为 : 应该是一个非法的字符，而我们却把它当作一个正常的输入用与 0 的距离来进行转换了，所以这里需要对输入的每一个字符都判断。

Java 源码关于 Integer.parseInt 的实现

把上面的问题全部考虑到，基本上就是 Java 的源码的实现了，所以我就不在继续 myParseInt 了，这里就直接祭出Java 的源码了

    public static int parseInt(String s, int radix)
                throws NumberFormatException
    {
        /*
         * WARNING: This method may be invoked early during VM initialization
         * before IntegerCache is initialized. Care must be taken to not use
         * the valueOf method.
         */

        if (s == null) {
            throw new NumberFormatException("null");
        }

        if (radix < Character.MIN_RADIX) {
            throw new NumberFormatException("radix " + radix +
                                            " less than Character.MIN_RADIX");
        }

        if (radix > Character.MAX_RADIX) {
            throw new NumberFormatException("radix " + radix +
                                            " greater than Character.MAX_RADIX");
        }

        int result = 0;
        boolean negative = false;
        int i = 0, len = s.length();
        int limit = -Integer.MAX_VALUE;
        int multmin;
        int digit;

        if (len > 0) {
            char firstChar = s.charAt(0);
            if (firstChar < '0') { // Possible leading "+" or "-"
                if (firstChar == '-') {
                    negative = true;
                    limit = Integer.MIN_VALUE;
                } else if (firstChar != '+')
                    throw NumberFormatException.forInputString(s);

                if (len == 1) // Cannot have lone "+" or "-"
                    throw NumberFormatException.forInputString(s);
                i++;
            }
            multmin = limit / radix;
            while (i < len) {
                // Accumulating negatively avoids surprises near MAX_VALUE
                digit = Character.digit(s.charAt(i++),radix);
                if (digit < 0) {
                    throw NumberFormatException.forInputString(s);
                }
                if (result < multmin) {
                    throw NumberFormatException.forInputString(s);
                }
                result *= radix;
                if (result < limit + digit) {
                    throw NumberFormatException.forInputString(s);
                }
                result -= digit;
            }
        } else {
            throw NumberFormatException.forInputString(s);
        }
        return negative ? result : -result;
    }

源码的部分分析

上面的源码中，大部分逻辑都是比较简单易懂的，比较核心的字符转数字，也是在其他类（digit = Character.digit(s.charAt(i++),radix);）中实现的。但是其中关于越界问题的检测逻辑我当初就没有一眼看明白。

            multmin = limit / radix;
            while (i < len) {
                // 省略其他代码
                if (result < multmin) {
                    throw NumberFormatException.forInputString(s);
                }
                result *= radix;
                if (result < limit + digit) {
                    throw NumberFormatException.forInputString(s);
                }

其中的 limit 就是最大值，之前我一直没搞明白 multmin 是做什么的，直到写这个博客，才明白过来，这是用来检测要转换的字符串是否越界用的。准确的说，上面我截取的这部分代码，都是做这个事儿的。那么为什么要这么做呢？这其实是必须的，因为 result 虽然在上一次的转换中没有越界，但是很有可能在本次的转换中因为与 radix 做乘积而越界，所以这里提前判断一下它和 multmin 的大小，后面的判断也是同理。这里需要注意的是 Java 的实现中是先按照负数来处理的，所以这里的不等式的方向与处理正数恰好是不一样的。

参考资料

https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#parseInt-java.lang.String-int-
https://stackoverflow.com/questions/40167218/why-does-the-integer-paseint-algorithm-calculate-negative-result-finally-in-su
https://stackoverflow.com/questions/1410555/how-does-integer-parseintstring-actually-work