构造函数

1
2
3
4
5
6
7
8
9
private final int value;

public Integer(int value) {
    this.value = value;
}

public Integer(String s) throws NumberFormatException {
    this.value = parseInt(s, 10);
}

从构造方法中我们可以知道，初始化一个 Integer 对象的时候只能创建一个十进制的整数。

Integer 转 String

转化为 16 进制/8 进制/2 进制方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
public static String toHexString(int i) {
    return toUnsignedString0(i, 4);
}

public static String toOctalString(int i) {
    return toUnsignedString0(i, 3);
}

public static String toBinaryString(int i) {
    return toUnsignedString0(i, 1);
}

可以看到其实都是调用toUnsignedString0方法，并传入自己的位数，例如16 = 2^4所以传入 4，8 = 2^3传入 3，2 = 2^1，传 1。

toUnsignedString0(int val, int shift)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static String toUnsignedString0(int val, int shift) {
    // assert shift > 0 && shift <=5 : "Illegal shift value";
    // 计算出val二级制实际需要多少位
    int mag = Integer.SIZE - Integer.numberOfLeadingZeros(val);
    // 计算出转化后需要用几位字符存储。
    // 二进制转换为目标进制，只需要将(mag/shift)向上取整，得到的结果就是需要的位数
    // 例如10的二进制为1010，转化为八进制只需要(4/3)向上取值，2位字符就行
    // 但是因为int是向下取整，所以加上（shift-1)保证结果为向上取整的值。
    // 还是拿10来举例，如果想要达到4/3取整的到2，只需要将4加2就行，而(shift-1)能够保证一个数加上后的区间还是在原区间不会溢出。
    int chars = Math.max(((mag + (shift - 1)) / shift), 1);
    // 定义缓存数组
    char[] buf = new char[chars];
    // 格式化val
    formatUnsignedInt(val, shift, buf, 0, chars);

    // 通过缓冲数组创建字符串
    return new String(buf, true);
}

numberOfLeadingZeros(int i)

1
2
3
4
5
6
7
8
9
10
11
12
public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

这个函数会返回 i 在二进制中第一个 1 前 0 的长度。如果 i 为负数，返回 1。如果 i == 0 ，返回 32。

具体算法其实就是参考二分的思想：

  1. 通过右移 16 位判断高十六位是否为 0，如果为 0，n+=16，再将低十六位前移。
  2. 右移 24 位，如果上一步执行了，那么这一步其实是判断高 24 位是否为 0，如果上一步未执行，那么这里是判断高 8 位是为 0。
  3. 通过这样不断二分，逐渐确认了 i 为正数时，0 的数量

n -= i >>>31：如果 i 为正数，右移 31 位的结果为 0，无影响；如果 i 为负数，前面的判断就不会执行，n=1，而 i 右移 31 位的结果就是 1。所以最后返回1-1 = 0.

formatUnsignedInt(int val, int shift, char[] buf, int offset, int len)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static int formatUnsignedInt(int val, int shift, char[] buf, int offset, int len) {
    // 定义字符位置charPos
    int charPos = len;
    // 定义进制值radix
    int radix = 1 << shift;
    int mask = radix - 1;
    do {
        // 从最后一位开始填充
        // 在radix为2^n次方的前提下，val & mask 其实就等于 val % radix取余的结果
        // 所以这一步其实就是对val取余，然后将余数从最后开始填充，再把val/radix进入下一步计算。
        buf[offset + --charPos] = Integer.digits[val & mask];
        val >>>= shift;
    } while (val != 0 && charPos > 0);

    return charPos;
}

// digits数组其实就是可能出现的字符
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'
};

通过这个方法，将 val 转化为目标进制数组。模拟的就是我们进行进制转化的方法。例如 10 转化为 2 进制的计算过程：

1
2
3
4
5
10 % 2 = 0，10 / 2 = 5 即最后一位是0，下一步用5计算
5 % 2 = 1，5 / 2 = 2 倒数第二位是1，下一步用2计算
2 % 2 = 0，2 / 2 = 1 倒数第三位是0，下一步用1计算
1 % 2 = 1，1 / 2 = 0 倒数第四位是1，结束结算
通过上诉计算，10的二进制就是1010

通过很精妙的二分法和位运算从而得到了目标进制的结果。

toString()

Integer 中有一个默认的十进制转化和一个其余进制转化方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// 默认转化方法
public static String toString(int i) {
    // 如果i是最小值，返回“-2147483648”
    if (i == Integer.MIN_VALUE)
        return "-2147483648";
    // 如果i为负数，将i变为正数获取数组长度再一个'-'的长度1
    // 如果i为正数，直接使用i的长度
    int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
    char[] buf = new char[size];
    getChars(i, size, buf);
    return new String(buf, true);
}

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                  99999999, 999999999, Integer.MAX_VALUE };

// 不断比较来确认x真正的位数
static int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;
}

// 将十进制i填充到数组中
static void getChars(int i, int index, char[] buf) {
    int q, r;
    // 从末尾开始填充
    int charPos = index;
    char sign = 0;
    // 如果i为负数，添加'-'，然后把i变成正数计算
    // 因为最小值取反会超过int范围，所以前面提前处理了Integer.MIN_VALUE
    if (i < 0) {
        sign = '-';
        i = -i;
    }

    // Generate two digits per iteration
    while (i >= 65536) {
        q = i / 100;
        // really: r = i - (q * 100);
        //  如官方注释所示：实际上就是求i%100的结果
        // r = i - (q * 100)
            // r = i - (q * 64 + q * 32 + q * 4)
            // r = i - ((q << 6) + (q << 5) + (q << 2))
        r = i - ((q << 6) + (q << 5) + (q << 2));
        i = q;
        // DigitOnes[r]实际上就是r%10的结果
        // 返回r个位的值，例如r = 74，DigitOnes[74]=4
        buf [--charPos] = DigitOnes[r];
        // DigitTens[r]实际上就是r%100的结果
        // 返回r十位的值，例如r = 74，DigitOnes[74]=7
        buf [--charPos] = DigitTens[r];
    }

    // Fall thru to fast mode for smaller numbers
    // assert(i <= 65536, i);
    for (;;) {
        // 这一部分其实就是用位运算和乘法来实现 i%10
        q = (i * 52429) >>> (16+3); // 约等于 i/10
        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;
    }
}

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',
    } ;

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',
    } ;


// 转化为目标进制的字符串
public static String toString(int i, int radix) {
    // 如果超出范围，则按十进制转化。
    if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
        radix = 10;

    /* 十进制则调用默认方法 */
    if (radix == 10) {
        return toString(i);
    }
    // 33位，多的一位是符号位
    char buf[] = new char[33];
    // i是否为负数的标志negative
    boolean negative = (i < 0);
    int charPos = 32;
    // 如果i为正数，i取反变为负数进行统一处理
    if (!negative) {
        i = -i;
    }
    // 如果i需要转化，就取余填充到数组
    while (i <= -radix) {
        // 取余从后开始填充，因为i为负数，所以计算结果要再次取反
        buf[charPos--] = digits[-(i % radix)];
        // 整除进入下一步计算
        i = i / radix;
    }
    // 将最后的余数加入数组
    buf[charPos] = digits[-i];
    // 如果i为负数，加上'-'号
    if (negative) {
        buf[--charPos] = '-';
    }
    // 通过数组创建字符串并返回
    return new String(buf, charPos, (33 - charPos));
}

一下内容来自Java 源码学习系列（三）——Integer

分析两个问题：

  1. 为什么在 getChars 方法中，将整型数字写入到字符数组的过程中为什么按照数字 65536 分成了两部分呢？这个 65535 是怎么来的？
  2. 在下面两段代码的方法二中，在对 i 进行除十操作的过程中为什么选择先乘以 52429 在向右移位 19 位。其中 52429 和 19 是怎么来的？
1
2
3
4
5
6
7
8
9
方法一：
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];
}
1
2
3
4
5
6
7
8
方法二
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 三个变量代替 65536,52429,19 三个数字，便于后面分析使用。

先明确两点：

移位的效率比直接乘除的效率要高
乘法的效率比除法的效率要高

r = i - ((q << 6) + (q << 5) + (q << 2));表示的其实是

1
2
3
r = i - (q * 100)
  = i - (q * 64 + q * 32 + q * 4)
  = i - ((q << 6) + (q << 5) + (q << 2))

q = (i * num2) >>> (num3);中，>>>表示无符号向右移位。代表的意义就是除以2^num3(524288)。 所以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 就要有这样的关系：

1
num2= (2^num3 / 10 +1)

只有这样才能保证(i * num2) >>> (num3)结果接近于 0.1。

那么 52429 这个数是怎么来的呢?来看以下数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
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 的呢？ 这三个数字之间是有这样一个操作的：

1
（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,所以，他们的乘积在无符号向右移位就能保证数字的准确性。

String 转 Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// 默认使用十进制转化
public static int parseInt(String s) throws NumberFormatException {
    return parseInt(s,10);
}

// 按设定进制进行转化
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用于判断是否溢出
        multmin = limit / radix;
        while (i < len) {
            // Accumulating negatively avoids surprises near MAX_VALUE
            // 负积累可避免再MAX_VALUE处附近出现意外，即使用减号积累，避免错误
            digit = Character.digit(s.charAt(i++),radix);
            if (digit < 0) {
                throw NumberFormatException.forInputString(s);
            }
            // 如果result < multmin，代表值溢出
            // 如果result < multmin --> result < limit / radix --> result * radix < limit --> result*radix - digit < limit (overflow)
            if (result < multmin) {
                throw NumberFormatException.forInputString(s);
            }
            result *= radix;
            // 推导过程加上一步，溢出抛出异常
            if (result < limit + digit) {
                throw NumberFormatException.forInputString(s);
            }
            // 类似于 result * radix + digit，只是Integer中使用负积累避免溢出
            result -= digit;
        }
    } else {
        throw NumberFormatException.forInputString(s);
    }
    // 如果不为负数，对结果取反
    return negative ? result : -result;
}

// String转为无符号位int，默认以10进制进行
public static int parseUnsignedInt(String s) throws NumberFormatException {
    return parseUnsignedInt(s, 10);
}

// String转换为无符号位int
public static int parseUnsignedInt(String s, int radix)
            throws NumberFormatException {
    if (s == null)  {
        throw new NumberFormatException("null");
    }

    int len = s.length();
    if (len > 0) {
        // 确定s不以负号开头
        char firstChar = s.charAt(0);
        if (firstChar == '-') {
            throw new
                NumberFormatException(String.format("Illegal leading minus sign " +
                                                   "on unsigned string %s.", s));
        } else {
            // 无符号位整型最大值为2^32-1，大于Integer.MAX_VALUE，所以需要分两种情况处理
            // 如官方注解所示，Integer.MAX_VALUE以最大进制(36)表示为6位（zik0zj），10进制表示为10位（2147483647）
            // 又因为Integer.MAX_VALUE并不是对应位数的最大值，所以采用5或者9来比较，保证一定小于最大值
            // 没有超过int最大值可以使用默认函数进行，否则使用Long进行类型转换
            if (len <= 5 || // Integer.MAX_VALUE in Character.MAX_RADIX is 6 digits
                (radix == 10 && len <= 9) ) { // Integer.MAX_VALUE in base 10 is 10 digits
                return parseInt(s, radix);
            } else {
                long ell = Long.parseLong(s, radix);
                // 不超过无符号位最大值，转为int返回
                if ((ell & 0xffff_ffff_0000_0000L) == 0) {
                    return (int) ell;
                // 超过最大值，抛出异常
                } else {
                    throw new
                        NumberFormatException(String.format("String value %s exceeds " +
                                                            "range of unsigned int.", s));
                }
            }
        }
    } else {
        throw NumberFormatException.forInputString(s);
    }
}

valueOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 默认使用10进制转换
public static Integer valueOf(String s) throws NumberFormatException {
    return Integer.valueOf(parseInt(s, 10));
}

// 将s转化为int返回
public static Integer valueOf(String s, int radix) throws NumberFormatException {
    return Integer.valueOf(parseInt(s,radix));
}

// 如果在缓冲区范围内，就加入缓冲区，否则创建对象
public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

缓冲区代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private static class IntegerCache {
        // 默认缓冲区范围：-128 ~ 127
        static final int low = -128;
        static final int high;
        static final Integer cache[];

        static {
            // high value may be configured by property
            int h = 127;
            // 根据设定参数更改缓冲区范围
            String integerCacheHighPropValue =
                sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
            if (integerCacheHighPropValue != null) {
                try {
                    int i = parseInt(integerCacheHighPropValue);
                    i = Math.max(i, 127);
                    // Maximum array size is Integer.MAX_VALUE
                    h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
                } catch( NumberFormatException nfe) {
                    // If the property cannot be parsed into an int, ignore it.
                }
            }
            high = h;
            // 新建数组存放缓冲区范围内的数据
            cache = new Integer[(high - low) + 1];
            int j = low;
            for(int k = 0; k < cache.length; k++)
                cache[k] = new Integer(j++);

            // range [-128, 127] must be interned (JLS7 5.1.7)
            assert IntegerCache.high >= 127;
        }

        private IntegerCache() {}
    }

缓冲区中含有一个静态代码块，会在 Integer 加载时执行。

也就是说，默认情况下：当 Integer 被加载时，就新建了-128 到 127 的所有 Integer 对象并存放在 Integer 数组 cache 中。

而在 valueOf 代码中，当调用 valueOf 方法时，如果参数的值在-127 到 128 之间，则直接从缓存中返回一个已经存在的对象。如果参数的值不在这个范围内，则 new 一个 Integer 对象返回。

所以，当把一个 int 变量转成 Integer 的时候（或者新建一个 Integer 的时候），建议使用 valueOf 方法来代替构造函数。或者直接使用Integer i = 100;编译器会转成Integer s = Integer.valueOf(10000);。

hashCode()和 equals()

1
2
3
4
5
6
7
8
@Override
public int hashCode() {
    return Integer.hashCode(value);
}

public static int hashCode(int value) {
    return value;
}

如上，原来 Integer 类型的 hashCode 就是这个数的值。这是我没想到的。

1
2
3
4
5
6
7
8
9
10
public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

public int intValue() {
    return value;
}

转化为基础类型直接比较。