Java源码阅读笔记01 - Integer

关于 java.lang.Integer 的部分笔记，基于JDK版本1.7。

概述

Java语言中关于基础数据类型int的封装类型，包含了一些类型之间的相互转换封装方法，除此之外还有一些关于机器数操作的封装API供开发人员使用。

继承关系

1
2
3

--java.lang.Object
  --java.lang.Number
    --java.lang.Integer

部分方法

getChars(int i, int index, char[] buf)

static void getChars(int i, int index, char[] buf) {
    int q, r;
    int charPos = index;
    char sign = 0;

    if (i < 0) {
        sign = '-';
        i = -i;
    }

    // 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;
    }
}

这个方法是Integer转String 的核心方法，目的是为了将一个整数存入一个char数组中。如果传入的i是个负数，那么需要继续正负号并将入参转成正数去处理。关于乘除法和位运算的效率，位运算的效率高于乘法，乘法的效率高于除法，所以坚持尽可能优先使用位运算的原则。但是整型数int的范围最大为 $ 2^{31-1} $ ,所以使用位运算和乘法时入参i实际上有一个上界。接着将行24的代码抽象为等式：

$q = (i * num1) >>> num2,$

行25的等式说明行24需要计算入参i除以10后得到的商值。行24可以继续转换成

$q = i * (num1 / 2^{num2}).$

根据上述两个等式，要保证i * num1不能超过int的范围，同时num1 / $ 2^{num2} $ 在保证精度的情况下尽可能等于0.1。所以对num2遍历取值判断，发现当num2=19，num1=52429时，小数后六位0可以满足精度要求，所以选定num1为52429，num2=19。因为i $*$ num1有最大值限制，而且行24的等式采用的是无符号右移方案，所以int的最大值可以是 $ 2^{32} $ ，因为num1为52429接近 $ 2^{15} $ ，所以i采用了65536( $ 2^{16} $ )作为判断边界。

decode(String nm)

public static Integer decode(String nm) throws NumberFormatException {
    int radix = 10;
    int index = 0;
    boolean negative = false;
    Integer result;

    if (nm.length() == 0)
        throw new NumberFormatException("Zero length string");
    char firstChar = nm.charAt(0);
    // Handle sign, if present
    if (firstChar == '-') {
        negative = true;
        index++;
    } else if (firstChar == '+')
        index++;

    // Handle radix specifier, if present
    if (nm.startsWith("0x", index) || nm.startsWith("0X", index)) {
        index += 2;
        radix = 16;
    }
    else if (nm.startsWith("#", index)) {
        index ++;
        radix = 16;
    }
    else if (nm.startsWith("0", index) && nm.length() > 1 + index) {
        index ++;
        radix = 8;
    }

    if (nm.startsWith("-", index) || nm.startsWith("+", index))
        throw new NumberFormatException("Sign character in wrong position");

    try {
        result = Integer.valueOf(nm.substring(index), radix);
        result = negative ? Integer.valueOf(-result.intValue()) : result;
    } catch (NumberFormatException e) {
        // If number is Integer.MIN_VALUE, we'll end up here. The next line
        // handles this case, and causes any genuine format error to be
        // rethrown.
        String constant = negative ? ("-" + nm.substring(index))
            : nm.substring(index);
        result = Integer.valueOf(constant, radix);
    }
    return result;
}

这个方法是将一个没有指定进制的字符串转换成响应进制的整型数字，具体采用的进制通过入参字符串前两位（前一位）字符判断得到。在行26中，有一个判断入参字符串长度的操作，这个操作只出现在了八进制中。这个判断的目的是确定是否应该采用八进制作为转换标准，因为八进制表示法的第一位是0，单纯通过第一位无法判断该采用八进制还是十进制。所以加入了长度的判断操作，如果第一位为0且之后还有数据，那么就采用八进制作为转换依据。

reverse(int i)

public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

实现入参int数值（以下简称为入参）的二进制补码的逆序返回。借鉴了分治的思想，首先将入参数值的补码每两位一组，左右交换码值。在行3中，0x55555555的二进制值是01010101010101010101010101010101，与入参执行按位与操作，再向左移动一位，低位补0，这样入参按两位分组后的低位码值即移到了左边。同时将入参向右移动一位，高位补0，与0x55555555执行按位与操作取得入参按两位分组后的高位码值即移动了右边，两个结果按位或执行后，即为入参按照两位分组后逆序交换后的结果。同理，在行4中，0x33333333的二进制值是00110011001100110011001100110011，会将行3执行后的补码序列按照每四位一组进行分组，每组中的高两位和低两位依次交换先后顺序。在行5中，则对行4操作执行完毕后的补码每八位一组，按照高四位和低四位依次交换先后顺序。至此，就已经完成了4个字节内部的补码逆序操作。行6 ~ 7以字节为单位，分别将低位第四字节左移到高位第一位，低位第三字节左移到高位第二位，高位第一字节右移到低位第四位，高位第二字节右移到低位第三位，四个结果按位取或结果，返回最后逆序的结果。

同理论方法：

public static int reverseBytes(int i) {
    return ((i >>> 24)        ) |
        ((i >>   8) &   0xFF00) |
        ((i <<   8) & 0xFF0000) |
        ((i << 24));
}

bitCount(int i)

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

统计入参int数值（以下简称为入参）补码表示中值为1的二进制位的个数。如下图：

图 - 1

第一行是入参的补码表示，接着将补码两两分组，分别统计每个分组中二进制位为1的个数，并用两位二进制替换原来的分组，该两位二进制的值标识对应分组中二进制位为1的个数，于是得到第二行的补码序列。

根据第一行和第二行的补码序列，我们可以观察到：

二进制位input	用来标识1的个数的新二进制位output	说明
00	00	没有1
01	01	一个1
10	01	一个1
11	10	两个1

现在需要通过input列的二进制序列计算出output序列。发现等式output = input - （input >>> 1）。如果input不是两位二进制，例如四位、八位、十六位、三十二位，上述等式并不成立，原因在于左两位二进制的移动影响了后两位二进制中的高位，于是把高位全部记为0，即源码中行3的表述。

同理，图1中将第二行得到的补码序列两两相加构成一个四位二进制序列，之后再将新生成的四位二进制序列两两相加，构成一个八位二进制序列，直至最后得到一个32位的补码序列，该序列的值即为入参的补码表示中二进制位为1的个数。

关于源码实现，行4首先计算低两位与11的与和，然后将序列右移两位计算高两位与11的与和，结果相加构成若干个四位二进制序列分组。行5将序列右移四位计算高四位与1111的与和，然后与原序列相加，结果为若干八位二进制序列分组。行6将序列右移八位后，高八位和低八位可做加法操作，得到16位二进制序列。行7计算序列高十六位和低十六位的和得到一个三十二位序列。因为一个int数值的二进制长度是32($ 2^6 $)位，所以高于六位的二进制位都是无效的，所以通过0x3F将高于六位的二进制位清零计算最后结果。

IntegerCache

private static class IntegerCache {
    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) {
            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);
        }
        high = h;

        cache = new Integer[(high - low) + 1];
        int j = low;
        for(int k = 0; k < cache.length; k++)
            cache[k] = new Integer(j++);
    }

    private IntegerCache() {}
}

原作者之所以设计这段代码，可能是出于性能的考虑。这段代码缓存了从-128到127共256个int型数值。如果在需要创建Integer实例的时候，如果值在-128到127之间，那么会直接从缓存里取值而不是重新创建对象。

涉及基础知识点

原码、反码、补码概念及相互转换；
左移、有符号右移和无符号右移。

参考文献

java源码Integer.bitCount算法解析，分析原理（统计二进制bit位）
Java源码 Integer.bitCount实现过程
JDK源碼 Integer.bitCount(i)
白中英 (2013)。《计算机组成原理》。北京：科学出版社