从JDK源码角度看Integer

撸了今年阿里、腾讯和美团的面试,我有一个重要发现…….

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/16032


概况

Java的Integer类主要的作用就是对基本类型int进行封装,提供了一些处理int类型的方法,比如int到String类型的转换方法或String类型到int类型的转换方法,当然也包含与其他类型之间的转换方法。除此之外还有一些位相关的操作。

继承结构

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

主要属性

第一部分

    public static final int   MIN_VALUE = 0x80000000;
    public static final int   MAX_VALUE = 0x7fffffff;
    public static final int SIZE = 32;
    public static final int BYTES = SIZE / Byte.SIZE;
    public static final Class<Integer>  TYPE = (Class<Integer>) Class.getPrimitiveClass("int");
  • MIN_VALUE静态变量表示int能取的最小值,为-2的31次方,被final修饰说明不可变。
  • 类似的还有MAX_VALUE,表示int最大值为2的31次方减1。
  • SIZE用来表示二进制补码形式的int值的比特数,值为32,静态变量且不可变。
  • BYTES用来表示二进制补码形式的int值的字节数,值为SIZE除于Byte.SIZE,结果为4。
  • TYPE的toString的值是int
    Class的getPrimitiveClass是一个native方法,在Class.c中有个Java_java_lang_Class_getPrimitiveClass方法与之对应,所以JVM层面会通过JVM_FindPrimitiveClass函数根据”int”字符串获得jclass,最终到Java层则为Class<Integer>
    JNIEXPORT jclass JNICALL
    Java_java_lang_Class_getPrimitiveClass(JNIEnv *env,
                                           jclass cls,
                                           jstring name)
    {
        const char *utfName;
        jclass result;

        if (name == NULL) {
            JNU_ThrowNullPointerException(env, 0);
            return NULL;
        }

        utfName = (*env)->GetStringUTFChars(env, name, 0);
        if (utfName == 0)
            return NULL;

        result = JVM_FindPrimitiveClass(env, utfName);

        (*env)->ReleaseStringUTFChars(env, name, utfName);

        return result;
    }

TYPE执行toString时,逻辑如下,则其实是getName函数决定其值,getName通过native方法getName0从JVM层获取名称,

    public String toString() {
            return (isInterface() ? "interface " : (isPrimitive() ? "" : "class "))
                + getName();
        }

getName0根据一个数组获得对应的名称,JVM根据Java层的Class可得到对应类型的数组下标,比如这里下标为10,则名称为”int”。

    const char* type2name_tab[T_CONFLICT+1] = {
      NULL, NULL, NULL, NULL,
      "boolean",
      "char",
      "float",
      "double",
      "byte",
      "short",
      "int",
      "long",
      "object",
      "array",
      "void",
      "*address*",
      "*narrowoop*",
      "*conflict*"
    };

第二部分

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

    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'
        };
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                          99999999, 999999999, Integer.MAX_VALUE };
  • DigitTens和DigitOnes两个数组放到一起讲更好理解,它们主要用于获取0到99之间某个数的十位和个位,比如48,通过DigitTens数组直接取出来十位为4,而通过DigitOnes数组取出来个位为8。
  • digits数组用于表示数字的所有可能的字符,因为int支持从2进制到36进制,所以这里需要有36个字符才能表示所有不同进制的数字。
  • sizeTable数组主要用在判断一个int型数字对应字符串的长度。比如相关的方法如下,这种方法可以高效得到对应字符串长度,避免了使用除法或求余等操作。
    static int stringSize(int x) {
          for (int i=0; ; i++)
              if (x <= sizeTable[i])
                  return i+1;
    }

IntegerCache内部类

    private static class IntegerCache {
            static final int low = -128;
            static final int high;
            static final Integer cache[];

            static {
                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);
                        h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
                    } catch( NumberFormatException nfe) {
                    }
                }
                high = h;

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

            private IntegerCache() {}
        }

IntegerCache是Integer的一个内部类,它包含了int可能值的Integer数组,默认范围是[-128,127],它不会像Byte类将所有可能值缓存起来,因为int类型范围很大,将它们全部缓存起来代价太高,而Byte类型就是从-128到127,一共才256个。所以这里默认只实例化256个Integer对象,当Integer的值范围在[-128,127]时则直接从缓存中获取对应的Integer对象,不必重新实例化。这些缓存值都是静态且final的,避免重复的实例化和回收。另外我们可以改变这些值缓存的范围,再启动JVM时通过-Djava.lang.Integer.IntegerCache.high=xxx就可以改变缓存值的最大值,比如-Djava.lang.Integer.IntegerCache.high=500则会缓存[-128,500]。

主要方法

parseInt方法

    public static int parseInt(String s, int radix)
                    throws NumberFormatException
        {
            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') {
                    if (firstChar == '-') {
                        negative = true;
                        limit = Integer.MIN_VALUE;
                    } else if (firstChar != '+')
                        throw NumberFormatException.forInputString(s);

                    if (len == 1)
                        throw NumberFormatException.forInputString(s);
                    i++;
                }
                multmin = limit / radix;
                while (i < len) {
                    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);
        }

两个parseInt方法,主要看第一个即可,第一个参数是待转换的字符串,第二个参数表示进制数。怎么更好理解这个参数呢?举个例子,Integer.parseInt("100",10)表示十进制的100,所以值为100,而Integer.parseInt("100",2)表示二进制的100,所以值为4。另外如果Integer.parseInt("10000000000",10)会抛出java.lang.NumberFormatException异常。

该方法的逻辑是首先判断字符串不为空且进制数在Character.MIN_RADIXCharacter.MAX_RADIX之间,即2到36。然后判断输入的字符串的长度必须大于0,再根据第一个字符可能为数字或负号或正号进行处理。核心处理逻辑是字符串转换数字,n进制转成十进制办法基本大家都知道的了,假如357为8进制,则结果为3*8^2+5*8^1+7*8^0 = 239,假如357为十进制,则结果为3*10^2+5*10^1+7*10^0 = 357,上面的转换方法也差不多是根据此方法,只是稍微转变了思路,方式分别为((3*8+5)*8+7) = 239和((3*10+5)*10+7)=357。从中可以推出规则了,从左到右遍历字符串的每个字符,然后乘以进制数,再加上下一个字符,接着再乘以进制数,再加上下个字符,不断重复,直到最后一个字符。除此之外另外一个不同就是上面的转换不使用加法来做,全都转成负数来运算,其实可以看成是等价了,这个很好理解,而为什么要这么做就要归咎到int类型的范围了,因为负数Integer.MIN_VALUE变化为正数时会导致数值溢出,所以全部都用负数来运算。

构造函数

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

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

包含两种构造函数,分别可以传入int和String类型。它是通过调用parseInt方法进行转换的,所以转换逻辑与上面的parseInt方法一样。

getChars方法

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

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

            while (i >= 65536) {
                q = i / 100;
                r = i - ((q << 6) + (q << 5) + (q << 2));
                i = q;
                buf [--charPos] = DigitOnes[r];
                buf [--charPos] = DigitTens[r];
            }

            for (;;) {
                q = (i * 52429) >>> (16+3);
                r = i - ((q << 3) + (q << 1));  
                buf [--charPos] = digits [r];
                i = q;
                if (i == 0) break;
            }
            if (sign != 0) {
                buf [--charPos] = sign;
            }
        }

该方法主要做的事情是将某个int型数值放到char数组里面,比如把357按顺序放到char数组中。这里面处理用了较多技巧,int高位的两个字节和低位的两个字节分开处理,while (i >= 65536)部分就是处理高位的两个字节,每次处理2位数,这里有个特殊的地方((q << 6) + (q << 5) + (q << 2))其实等于q*100,DigitTensDigitOnes数组前面已经讲过它的作用了,用来获取十位和个位。再看接下去的低位的两个字节怎么处理,其实本质也是求余思想,但又用了一些技巧,比如(i * 52429) >>> (16+3)其实约等于i/10((q << 3) + (q << 1))其实等于q*10,然后再通过digits数组获取到对应的字符。可以看到低位处理时它尽量避开了除法,取而代之的是用乘法和右移来实现,可见除法是一个比较耗时的操作,比起乘法和移位。另外也可以看到能用移位和加法来实现乘法的地方也尽量不用乘法,这也说明乘法比起它们更加耗时。而高位处理时没有用移位是因为做乘法后可能会溢出。

toString方法

    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);
        }
    public String toString() {
            return toString(value);
        }
    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);
            }

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

一共有3个toString方法,两个静态方法一个是非静态方法,第一个toString方法很简单,就是先用stringSize得到数字是多少位,再用getChars获取数字对应的char数组,最后返回一个String类型。第二个toString调用第一个toString,没啥好说。第三个otString方法是带了进制信息的,它会转换成对应进制的字符串。凡是不在2到36进制范围之间的都会被处理成10进制,我们都知道从十进制转成其他进制时就是不断地除于进制数得到余数,然后把余数反过来串起来就是最后结果,所以这里其实也是这样子做的,得到余数后通过digits数组获取到对应的字符,而且这里是用负数的形式来运算的。

valueOf方法

    public static Integer valueOf(int i) {
            if (i >= IntegerCache.low && i <= IntegerCache.high)
                return IntegerCache.cache[i + (-IntegerCache.low)];
            return new Integer(i);
        }
    public static Integer valueOf(String s) throws NumberFormatException {
            return Integer.valueOf(parseInt(s, 10));
        }
    public static Integer valueOf(String s, int radix) throws NumberFormatException {
            return Integer.valueOf(parseInt(s,radix));
        }

有三个valueOf方法,核心逻辑在第一个valueOf方法中,因为IntegerCache缓存了[low,high]值的Integer对象,对于在范围内的直接从IntegerCache的数组中获取对应的Integer对象即可,而在范围外的则需要重新实例化了。

decode方法

    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);
            if (firstChar == '-') {
                negative = true;
                index++;
            } else if (firstChar == '+')
                index++;
            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) {
                String constant = negative ? ("-" + nm.substring(index))
                                           : nm.substring(index);
                result = Integer.valueOf(constant, radix);
            }
            return result;
        }

decode方法主要作用是解码字符串转成Integer型,比如Integer.decode("11")的结果为11;Integer.decode("0x11")Integer.decode("#11")结果都为17,因为0x和#开头的会被处理成十六进制;Integer.decode("011")结果为9,因为0开头会被处理成8进制。

xxxValue方法

    public byte byteValue() {
            return (byte)value;
        }
    public short shortValue() {
            return (short)value;
        }
    public int intValue() {
            return value;
        }
    public long longValue() {
            return (long)value;
        }
    public float floatValue() {
            return (float)value;
        }
    public double doubleValue() {
            return (double)value;
        }

包括shortValue、intValue、longValue、byteValue、floatValue和doubleValue等方法,其实就是转换成对应的类型。

hashCode方法

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

hashCode方法很简单,就是直接返回int类型的值。

equals方法

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

比较是否相同时先判断是不是Integer类型再比较值。

compare方法

    public static int compare(int x, int y) {
            return (x < y) ? -1 : ((x == y) ? 0 : 1);
        }

x小于y则返回-1,相等则返回0,否则返回1。

无符号转换

    public static long toUnsignedLong(int x) {
            return ((long) x) & 0xffffffffL;
        }
    public static String toUnsignedString(int i) {
            return Long.toString(toUnsignedLong(i));
        }
    public static String toUnsignedString(int i, int radix) {
            return Long.toUnsignedString(toUnsignedLong(i), radix);
        }

转成无符号long型。

bitCount方法

    public static int bitCount(int i) {
            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;
        }

该方法主要用于计算二进制数中1的个数。一看有点懵,都是移位和加减操作。先将重要的列出来,0x55555555等于010101010101010101010101010101010x33333333等于1100110011001100110011001100110x0f0f0f0f等于1111000011110000111100001111。它的核心思想就是先每两位一组统计看有多少个1,比如10011111则每两位有1、1、2、2个1,记为01011010,然后再算每四位一组看有多少个1,而01011010则每四位有2、4个1,记为00100100,接着每8位一组就为00000110,接着16位,32位,最终在与0x3f进行与运算,得到的数即为1的个数。

highestOneBit方法

    public static int highestOneBit(int i) {
            i |= (i >>  1);
            i |= (i >>  2);
            i |= (i >>  4);
            i |= (i >>  8);
            i |= (i >> 16);
            return i - (i >>> 1);
        }

该方法返回i的二进制中最高位的1,其他全为0的值。比如i=10时,二进制即为1010,最高位的1,其他为0,则是1000。如果i=0,则返回0。如果i为负数则固定返回-2147483648,因为负数的最高位一定是1,即有1000,0000,0000,0000,0000,0000,0000,0000。这一堆移位操作是什么意思?其实也不难理解,将i右移一位再或操作,则最高位1的右边也为1了,接着再右移两位并或操作,则右边1+2=3位都为1了,接着1+2+4=7位都为1,直到1+2+4+8+16=31都为1,最后用i - (i >>> 1)自然得到最终结果。

lowestOneBit方法

    public static int lowestOneBit(int i) {
            return i & -i;
        }

与highestOneBit方法对应,lowestOneBit获取最低位1,其他全为0的值。这个操作较简单,先取负数,这个过程需要对正数的i取反码然后再加1,得到的结果和i进行与操作,刚好就是最低位1其他为0的值了。

numberOfLeadingZeros方法

     public static int numberOfLeadingZeros(int i) {
            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的二进制从头开始有多少个0。i为0的话则有32个0。这里处理其实是体现了二分查找思想的,先看高16位是否为0,是的话则至少有16个0,否则左移16位继续往下判断,接着右移24位看是不是为0,是的话则至少有16+8=24个0,直到最后得到结果。

numberOfTrailingZeros方法

    public static int numberOfTrailingZeros(int i) {
            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);
        }

与前面的numberOfLeadingZeros方法对应,该方法返回i的二进制从尾开始有多少个0。它的思想和前面的类似,也是基于二分查找思想,详细步骤不再赘述。

reverse方法

    public static int reverse(int i) {
            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;
        }

该方法即是将i进行反转,反转就是第1位与第32位对调,第二位与第31位对调,以此类推。它的核心思想是先将相邻两位进行对换,比如10100111对换01011011,接着再将相邻四位进行对换,对换后为10101101,接着将相邻八位进行对换,最后把32位中中间的16位对换,然后最高8位再和最低8位对换。

toHexString和toOctalString方法

    public static String toHexString(int i) {
            return toUnsignedString0(i, 4);
        }
    public static String toOctalString(int i) {
            return toUnsignedString0(i, 3);
        }
    private static String toUnsignedString0(int val, int shift) {
            int mag = Integer.SIZE - Integer.numberOfLeadingZeros(val);
            int chars = Math.max(((mag + (shift - 1)) / shift), 1);
            char[] buf = new char[chars];

            formatUnsignedInt(val, shift, buf, 0, chars);

            return new String(buf, true);
        }
    static int formatUnsignedInt(int val, int shift, char[] buf, int offset, int len) {
            int charPos = len;
            int radix = 1 << shift;
            int mask = radix - 1;
            do {
                buf[offset + --charPos] = Integer.digits[val & mask];
                val >>>= shift;
            } while (val != 0 && charPos > 0);

            return charPos;
        }

这两个方法类似,合到一起讲。看名字就知道转成8进制和16进制的字符串。可以看到都是间接调用toUnsignedString0方法,该方法会先计算转换成对应进制需要的字符数,然后再通过formatUnsignedInt方法来填充字符数组,该方法做的事情就是使用进制之间的转换方法(前面有提到过)来获取对应的字符。

赞(1) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 从JDK源码角度看Integer
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏