返回 登录
0

Java Integer 类解读

Integer 类是Java中最常用的类型,它是原生类型 int 的包装类。在开发中我们基本可以将两者等价。但是,最近在开发中遇到一个 == 与 equals 不一致的错误。所以趁此机会深入了解一下java中的Integer类。

Integer的界限范围与int类型是一致的。都是 0x7fffffff~0x80000000。Integer类中是这样声明的。

    /**
     * A constant holding the minimum value an {@code int} can
     * have, -2<sup>31</sup>.
     */
    public static final int   MIN_VALUE = 0x80000000;

    /**
     * A constant holding the maximum value an {@code int} can
     * have, 2<sup>31</sup>-1.
     */
    public static final int   MAX_VALUE = 0x7fffffff;

这两个范围大家经常用,一般不会出现问题。但是,由于补码表示负数的关系。正数总是比负数多一个来。作为边界值,这经常会导致问题。例如下面的代码:`

// Math.abs(int) 方法也是这个逻辑
int abs(int num) {
    return num < 0 ? -num : num;
}

这里返回结果不全是正数,输入Integer.MIN_VALUE的结果还是Integer.MIN_VALUE,因为没有相应的补码与之对应。所以在使用绝对值的时候还是要小心的,要考虑是否会出现一个Integer.MIN_VALUE的输入,如果有可能,那就需要更大范围的类型(Long)来表示或者单独对它进行处理。系统提供的abs方法并没有考虑这个问题。

Integer 类可转换的进制范围: 2-36。 这两个范围参考Character.MIN_RADIX与Character.MAX_RADIX两个值。除了常用的二进制、八进制、十六进制,其它在范围内的进制都可以十分方便地转换输出。
整个转换的代码如下:

    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'
    };
    public static String toString(int i, int radix) {

        if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
            radix = 10;

        /* Use the faster version */
        if (radix == 10) {
            return toString(i);
        }

        char buf[] = new char[33];
        boolean negative = (i < 0);
        int charPos = 32;

        if (!negative) {
            i = -i;
        }

        while (i <= -radix) {
            buf[charPos--] = digits[-(i % radix)];
            i = i / radix;
        }
        buf[charPos] = digits[-i];

        if (negative) {
            buf[--charPos] = '-';
        }

        return new String(buf, charPos, (33 - charPos));
    }

这里需要注意的地方有:2-36 进制以外的进制都当十进制处理;十进制使用了默认的、更加快速的处理方法;这里数字的运算是使用负数参与计算的(while循环那里),个人感觉是因为负数的范围比正数大,这样不需要额外处理Integer.MIN_VALUE的问题,整个代码变得简洁很多。

对于常见的二进制、八进制、十六进制,我们并不关心数字的符号,所以它提供了更加方便的接口。代码如下:

    public static String toHexString(int i) {
        return toUnsignedString(i, 4);
    }

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

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

    private static String toUnsignedString(int i, int shift) {
        char[] buf = new char[32];
        int charPos = 32;
        int radix = 1 << shift;
        int mask = radix - 1;
        do {
            buf[--charPos] = digits[i & mask];
            i >>>= shift;
        } while (i != 0);

        return new String(buf, charPos, (32 - charPos));
    }

这里的实现明显要比上面的实现高效,简洁。

接下来就是最常用的toString()接口了,他的实现用了一些高级的算法在里面。直接看代码:

    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) {
        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);
    }

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

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

    // Requires positive x
    static int stringSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }

这里从toString()方法开始看。先是对Integer.MIN_VALUE做了单独的处理。接下来转成正数,开始主要的处理逻辑。主要逻辑以65536做为分界线,分成了两部分。大于65536的部分使用了除法,一次生成两位十进制字符;小于等于65536的部分使用了乘法加位移做成除以10的效果。下面的使用乘法的部分效率更高但是在16位以上的数字会存在溢出的问题,52429这个数字如果选得太小精度又会不够,所以应该这里被迫只能分成了两部分。整个过程使用生成字符都尽量避免运算,采用查表的的方式。可以看出这里对细节的处理非常的多。

接下来是我们常用的pareseInt()方法:

    /**
     * Parses the string argument as a signed integer in the radix
     * specified by the second argument. 
     * <p>Examples:
     * <blockquote><pre>
     * parseInt("0", 10) returns 0
     * parseInt("473", 10) returns 473
     * parseInt("+42", 10) returns 42
     * parseInt("-0", 10) returns 0
     * parseInt("-FF", 16) returns -255
     * parseInt("1100110", 2) returns 102
     * parseInt("2147483647", 10) returns 2147483647
     * parseInt("-2147483648", 10) returns -2147483648
     * parseInt("2147483648", 10) throws a NumberFormatException
     * parseInt("99", 8) throws a NumberFormatException
     * parseInt("Kona", 10) throws a NumberFormatException
     * parseInt("Kona", 27) returns 411787
     * </pre></blockquote>
     *
     * @param      s   the {@code String} containing the integer
     *                  representation to be parsed
     * @param      radix   the radix to be used while parsing {@code s}.
     * @return     the integer represented by the string argument in the
     *             specified radix.
     * @exception  NumberFormatException if the {@code String}
     *             does not contain a parsable {@code int}.
     */
    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;
    }
    public static int parseInt(String s) throws NumberFormatException {
        return parseInt(s,10);
    }

这里也是通过计算负数再添加符号位的方式避免Integer.MIN_VALUE单独处理的问题。这里使用了一个mulmin变量来避免数字溢出的问题,单纯的使用正负号不能准确判断是否溢出(一次乘法导致溢出的结果符号不确定)。

接下来到了 IntegerCache 相关的内容,代码如下:

    /**
     * Cache to support the object identity semantics of autoboxing for values between
     * -128 and 127 (inclusive) as required by JLS.
     *
     * The cache is initialized on first usage.  The size of the cache
     * may be controlled by the -XX:AutoBoxCacheMax=<size> option.
     * During VM initialization, java.lang.Integer.IntegerCache.high property
     * may be set and saved in the private system properties in the
     * sun.misc.VM class.
     */


    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() {}
    }
    public static Integer valueOf(int i) {
        assert IntegerCache.high >= 127;
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

在Integer类中有一个静态内部类,它负责存储了(high -low)个静态Integer对象,并切在静态代码块中初始化。low的值是固定的-128,high的默认值是127,如果不去配置虚拟机参数,这个值不会变。配合valueOf(int) 方法,可以节省创建对象造成的资源消耗。

从注释中可以看出 -XX:AutoBoxCacheMax= 参数可以影响到缓存的大小。
“java.lang.Integer.IntegerCache.high” 参数可以影响到high的值。
自动装箱时,如果值在cache中,那么会直接返回cache中的对象不会额外创建一个对象。

这里就能解释为什么一些自动装箱的值会出现值不相等的情况,例如:

Integer a = 10;
Integer b = 10;
assert a == b // 没问题,他们对应缓存中的同一个对象地址

Integer c = 10000;
Integer d = 10000;
assert c == d // 不相等,他们没有被缓存所以不是指向同一地址的
assert c.equals(d); // 没问题,equals的本质是值的比较

这里贴出Integer类的equals()方法 与 hashCode()方法的代码:

    public int hashCode() {
        return value;
    }

    public boolean equals(Object obj) {
        if (obj instanceof Integer) {
            return value == ((Integer)obj).intValue();
        }
        return false;
    }

符合预期。

接下来跳过几个获取系统属性的方法。我们看它提供的几个非常有意思的位操作的方法。

留下最高位

    public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }
// 随便一个例子,不用管最高位之后有多少个1,都会被覆盖
// 00010000 00000000 00000000 00000000      raw
// 00011000 00000000 00000000 00000000      i | (i >> 1)
// 00011110 00000000 00000000 00000000      i | (i >> 2)
// 00011111 11100000 00000000 00000000      i | (i >> 4)
// 00011111 11111111 11100000 00000000      i | (i >> 8)
// 00011111 11111111 11111111 11111111      i | (i >> 16)
// 00010000 0000000 00000000 00000000       i - (i >>>1)

留下最低位

    public static int lowestOneBit(int i) {
        // HD, Section 2-1
        return i & -i;
    }
// 例子
// 00001000 10000100 10001001 00101000    i
// 11110111 01111011 01110110 11011000    -i
// 00000000 00000000 00000000 00001000  i & -i

数字开头有多少个0

    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: 00000000 00000000 00000000 00000001         n = 1
// i: 00000000 00000001 00000000 00000000         n = 17
// i: 00000001 00000000 00000000 00000000         n = 25
// i: 00010000 00000000 00000000 00000000         n = 29
// i: 01000000 00000000 00000000 00000000         n = 31
// i >>>31 == 0
// return 31

数字结尾有多少个0

    public static int numberOfTrailingZeros(int i) {
        // HD, Figure 5-14
        int y;
        if (i == 0) return 32;
        int n = 31;
        y = i <<16; if (y != 0) { n = n -16; i = y; }
        y = i << 8; if (y != 0) { n = n - 8; i = y; }
        y = i << 4; if (y != 0) { n = n - 4; i = y; }
        y = i << 2; if (y != 0) { n = n - 2; i = y; }
        return n - ((i << 1) >>> 31);
    }
// 与求开头多少个0类似,也是用了二分法,先锁定1/2, 再锁定1/4,1/8,1/16,1/32。
// i: 11111111 11111111 11111111 11111111    n: 31
// i: 11111111 11111111 00000000 00000000    n: 15
// i: 11111111 00000000 00000000 00000000    n: 7
// i: 11110000 00000000 00000000 00000000    n: 3
// i: 11000000 00000000 00000000 00000000    n: 1
// i: 10000000 00000000 00000000 00000000    n: 0

1的位数

    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;
    }
// 具体例子参考维基百科,这里不再列举

这是一个O(lgN)的算法,N代表i的bit数(这里N = 32)。算法的具体内容参考维基百科:Hamming weight
核心思想类似分治。

按bit旋转

    public static int rotateLeft(int i, int distance) {
        return (i << distance) | (i >>> -distance);
    }
    public static int rotateRight(int i, int distance) {
        return (i >>> distance) | (i << -distance);
    }

这里我一开始没有理解。尤其是shift操作符右面的参数是负数的情况。后来一番搜索之后终于发现,这里实质上是利用了shift操作参数取值的技巧。shift操作符的定义参考这里。
重点看这里:

在左参数是int类型的时候,右参数只有低五位有效;
在左参数是long类型的时候,右参数只有低六位有效。
我们列举一下前几个值就能发现规律:
图片描述

所以有这么一个恒等式 distance + (-distance & 0x1F) = 32。这不刚好用来做32位旋转嘛。

这代码虽然不好理解,但确实简洁。

按bit逆置

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

这个方法可以分成前后两部分。前半部分类似归并排序,先把相邻两位逆置,再把4位逆置,不断扩展,直到每一个Byte内部都逆置完毕。后半部分实质上是一个按Byte逆置的过程。
前半部分比较难理解,这里提供一份可以打log的代码,可以通过log查看它整个逆置的过程。有兴趣的同学自行copy。

public void testReverse() {
    int number = 12345678;
    System.out.printf("%s  number\n\n", formatBinary(number));
    int a = (number & 0x55555555) << 1;
    System.out.printf("%s  (number & 0x55555555) << 1\n", formatBinary(a));
    int b = (number >>> 1) & 0x55555555;
    System.out.printf("%s  (number >>> 1) & 0x55555555\n", formatBinary(b));
    number = a | b;
    System.out.printf("%s  number\n\n", formatBinary(number));
    int c = (number & 0x33333333) << 2;
    System.out.printf("%s  (number & 0x33333333) << 2\n", formatBinary(c));
    int d = (number >>> 2) & 0x33333333;
    System.out.printf("%s  (number >>> 2) & 0x33333333\n", formatBinary(d));
    number = c | d;
    System.out.printf("%s  number\n\n", formatBinary(number));
}
static String formatBinary(int number) {
    char[] buff = new char[36];
    int mask = Integer.MIN_VALUE;
    int printer = 0;
    for (int i = 0; i < 32; i++) {
        if ((number & (mask >>> i)) != 0) buff[printer++] = '1';
        else buff[printer++] = '0';
        if (((i + 1) & 0x7) == 0) buff[printer++] = ' ';
    }
    return new String(buff);
}

判断符号

    /**
     * Returns the signum function of the specified {@code int} value.  (The
     * return value is -1 if the specified value is negative; 0 if the
     * specified value is zero; and 1 if the specified value is positive.)
     *
     * @return the signum function of the specified {@code int} value.
     * @since 1.5
     */
    public static int signum(int i) {
        // HD, Section 2-7
        return (i >> 31) | (-i >>> 31);
    }

正常情况下,我们都是写if语句的。然而,真的可以不用。

按Byte逆置

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

这里的代码很熟悉。因为它就是 按bit逆置 的后半部分。

Integer类精彩的代码就这些了,读过这一遍还是有很多收获的。 有什么理解不对的地方还请大家指正。

学习Java的同学注意了!!!
学习过程中遇到什么问题或者想获取学习资源的话,欢迎加入Java学习交流群,群号码:454297367 我们一起学Java!

评论