jdk源码学习笔记---Integer


初衷

刚接触java不到2礼拜的小白试图通过阅读jdk的源码来学习java。如有理解或表达不对的地方,欢迎各位大佬指正,谢谢。


0. Integer类的用途

1.对基本类型int进行包装,个人感觉从某种意义上来讲Integer类是int的装饰器。

2.对外开放的丰富的功能能够好的处理int型数据,提高代码的复用。

1. Integer类的继承和实现体系

Integer类的继承和实现体系如下图所示:

这里写图片描述

其中Number类是一个抽象类,其中的抽象方法都是希望通过子类来实现返回对应类型的值。如intValue()返回int,longValue()返回long等。而Compareble是一个泛型的接口,且接口中只有一个compareTo方法,也就是说Integer实现了compareTo方法来实现Integer的对象在容器中时能够进行自然排序。(好比在C++中,vector中的元素是类A的对象,想要调用vector的sort函数对其进行排序时,需要类A重载<操作符。只不过在Java中更OO)

2. 各种toString

在Integer类中首先映入眼帘的应该是各种toString方法,因此我们就先来分析这一堆将int转换为String的方法。

2.1 public static String toString(int i)

这个函数主要用来将10进制的整数转换为String。代码如下:

    public static String toString(int i) {
//返回-2^32的字符串
if (i == Integer.MIN_VALUE)
return "-2147483648";
//计算字符串的size
int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
char[] buf = new char[size];
//将int转换为字符序列存在buf里
getChars(i, size, buf);
return new String(buf, true);
}

从上面的代码可以看出将10进制的整数转为String大致分为三步:1.计算字符数组的size。2.将10进制整数以某种算法填充到字符数组中。3.将字符数组转换为String并返回。


首先来看第一步:计算字符数组的size

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

从代码中可以看出,stringSize只考虑了x是正整数时的情况,因为负整数的情况在调用方那里已经考虑了。stringSize的处理流程是将x与sizeTable中的值比较,例如x=10,那么在查表的过程中会将i锁定为1(10<99),然后返回2(1+1=2),即字符数组的size=2。

PS:在java中没有像C/C++中的字符串那样在字符串的结尾需要一个’\0’作为结束符来标记。如果是使用C/C++来实现的话应该是return i+2。


接下来看第二步:10进制整数转换为字符数组

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 * 100);
r = i - ((q << 6) + (q << 5) + (q << 2));
i = q;
//查表,减少运算开销
buf [--charPos] = DigitOnes[r];
buf [--charPos] = DigitTens[r];
}

//此时i<=65536,进入快速模式,每次循环计算出一位数字
for (;;) {
//等价于i*0.1
q = (i * 52429) >>> (16+3);
//等价于r = i-(q*10)
r = i - ((q << 3) + (q << 1));
buf [--charPos] = digits [r];
i = q;
if (i == 0) break;
}
if (sign != 0) {
buf [--charPos] = sign;
}
}

整个字符数组的填充过程是从最末尾开始然后往前移动的,取整数的各个位上的数也是从后往前。假设此时输入的i=65536,这个时候会进入whlie循环,循环体每次迭代时会计算出最后的两位数字所对应的字符。其中DigitOnes和DigitTens分别为当前最末位和次末尾的字符表,代码如下所示:

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

还是举刚才的例子,q=65536/100,r=36,通过查上面的表可知最末位为’6’,次末位为’3’。

当i的值小于等于65536时,进入快速模式(此时最多迭代5次),每次迭代计算出一位数字所对应的字符。该代码的作者对于位运算的各种黑科技也是比较娴熟,由于我对这种位运算技巧不太熟练,就暂先不对其中的奥妙进行分析,日后再进行研究。


最后是第三部,字符数组转换为String

    String(char[] value, boolean share) {
// assert share : "unshared not supported";
this.value = value;
}

在这里不得不提到String构造函数的另一个重载版本,那个版本主要是将内容逐一赋值到value中。代码如下:

    public String(char value[]) {
this.value = Arrays.copyOf(value, value.length);
}

而在这里使用到的是共享版本,直接将传进来的value的引用赋值给String的value。这样做的好处是省去了内容逐一复制的开销,时间复杂度从O(n)降到O(1),并且共享内部数据,节省了内存。

2.2 public static String toString(int i, int radix)

该方法接受两个参数,i是待转换的整数,radix是进制参数,如radix=7,则返回i以7进制的表示形式的字符串。代码如下:

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

//2进制表示为字符串需要32个字符+1个符号字符
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));
}

算法的大致流程是:首先判断radix参数的值,若radix=10或者在允许的范围之外将调用2.1中提到的toSring来转换为String并返回。否则,会迭代计算最末位字符,然后在charPos的位置上补i。最后再截断字符数组构造出String并返回。

虽然算法流程较为简单,但有两个地方需要注意:

1. i和radix在参与最末位计算时用的是相反数,但如果不是相反数其实也可以实现功能,至于为什么要以相反数的形式处理,目前还不知道。。

2. 如果i是负数,那么转换后的String只是在最前面加了个’-‘。假设i=-32,radix =2,那么结果将是-100000而不是1111111111111111111111111111111111111111111111111111111111100000
。如果想转换成1111111111111111111111111111111111111111111111111111111111100000可以使用toBinaryString方法。

2.3 public static String toBinaryString(int i)

用于将int转换成二进制表示形式的String的方法,代码如下:

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

方法内只有一行代码,就是调用toUnsignedString0。由于该方法只被toBinaryString,toHexString和toOctalString调用,因此toUnsignedString0是一个私有的静态方法。toUnsignedString0的代码如下:

    private static String toUnsignedString0(int val, int shift) {
// assert shift > 0 && shift <=5 : "Illegal shift value";
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);

// Use special constructor which takes over "buf".
return new String(buf, true);
}

算法的大致流程可分为3步:

1.计算出二进制表示形式的字符串的最前面的0的个数。如:2818048,对应二进制:00000000 00101011 00000000 00000000,会返回10。

2.计算字符数组的size。

3.格式化字符数组并构造String返回。


下面分别详细分析这3个步骤:

1.计算最前面的0的个数

Intger类实现了numberOfLeadingZeros方法来完成这个功能,代码如下:

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

在这里作者将32位的内存块看成是4块8位连续的内存块,并用到了二分查找的思想来快速定位最前面的1的位置。举个栗子:假设此时i=33,那么此时i的二进制表示形式如下:

00000000 00000000 00000000 00100001
A B C D

那么算法会执行第一个判断(i >>> 16 == 0),意思就是i右移16位后看A和B两个区域中有没有1,i右移后如下所示:

00000000 00000000 00000000 00000000
A B C D

看图就知道显然是没有的,因此n+=16(此时n=17),而此时i将会左移16位,左移后i的二进制表示形式如下:

00000000 00100001 00000000 00000000
A B C D

然后执行第二个判断(i >>> 24 == 0),同样,意思就是i右移24位后看C中有没有1(A和B在上一步已经看过有没有1)。i右移24位后如下所示:

00000000 00000000 00000000 00000000
A B C D

显然C中是没有1的,因此n+=8(此时n=25),并且i将会左移8位,左移后i的二进制表示形式如下:

00100001 00000000 00000000 00000000
A B C D

现在执行第三个判断(i >>> 28 == 0),等价于i右移28位的i的D的后4位中是否有1。i右移28位后如下所示:

00000000 00000000 00000000 00000010
A B C D

注意,这个时候D的后4位中有1,说明最前面的1会出现在D的前四位中,n就不累加了。

然后执行第四个判断(i >>> 30 == 0)。i右移后二进制表示形式如下:

00000000 00000000 00000000 00000000
A B C D

这个时候n+=2(此时n=27),i左移2位,i左移后二进制表示形式如下:

10000100 00000000 00000000 00000000
A B C D

最后,由于原本i的最低位没判断是不是1,所以要检查最低位是否为1,如果为1,则n需要-1,此时n=26。也就是说i的二进制表示形式前面有26个0。

查找最前面的1的位置时可以将i循环左移或者友移来处理,但性能明显不如二分查找。


2.计算字符数组的size

得到val的前置0的个数后可以用32-这个个数来得到字符数组size的候选值。之所以是候选值是因为在计算真正的字符数组的size时要根据shift的值来计算对应进制的字符数。 (PS:假设进制数为n,那么shift=log2(n),也就是说如果是2进制,shift=1,如果是8进制,shift=3,16进制shift=3,依此类推) 计算size代码如下:

int chars = Math.max(((mag + (shift - 1)) / shift), 1);

其中shift-1的作用是当位数不能被radix整除时做的填充作用。


3.格式化字符数组

这个方法和C中的itoa差不多,数组从后往前存,先把shift转换成对应的真正的进制radix,掩码max的作用是每次去进制对应的最低位的bit数,然后查表转化为对应的字符,具体代码如下:

     static int formatUnsignedLong(long 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[((int) val) & mask];
val >>>= shift;
} while (val != 0 && charPos > 0);

return charPos;
}

2.4 public static String toHexString(int i)和public static String toOctalString(int i)

这两个方法其实都是调用2.3中提到的toUnsignedString0方法,只不过参数不同罢了,不再复述。代码如下:

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

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

3. 各种String转int

有各种int转String的方法,当然也有各种String转int的方法啦。。下面将对这些方法进行理解和分析。

3.1 public static int parseInt(String s, int radix)

这个方法用于将String转换成int,其中radix为进制数,例如parseInt(“473”, 10)后会返回473.并且该方法throws了NumberFormatException。代码如下所示:

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.
*/

//判断String是否为空,radix是否在范围内的日常
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();
//MAX_VALUE = 2147483647
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);
//当digit=-1即<0时表示在字符表中没有找到对应的值,即改字符不能被数字化。
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是负数累加
result -= digit;
}
} else {
throw NumberFormatException.forInputString(s);
}
return negative ? result : -result;
}

值得注意的是结果是通过负数累加得到的,不知道为什么不用正数累加。。。。

3.2 public static int parseInt(String s)

该方法其实就是调用3.1的parseInt,只不过把参数写死了。代码如下:

    public static int parseInt(String s) throws NumberFormatException {
return parseInt(s,10);
}

4. String转Intger

既然有int转String,String转int,那么也会有String转Integer。Integer类中的那些valueOf方法和decode方法能够满足这一需求。

4.1 valueOf

在自动装箱(autoboxing)时其实相当于调用了valueOf。代码如下:

    public static Integer valueOf(String s, int radix) throws NumberFormatException {
return Integer.valueOf(parseInt(s,radix));
}

public static Integer valueOf(String s) throws NumberFormatException {
return Integer.valueOf(parseInt(s, 10));
}

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个valueOf都是调用parseInt方法来将String转成int,最后调用第3个valueOf方法。(PS:第3个valueOf方法中使用到了一个叫IntegerCache的类,这个类主要对-128到127之间的数进行了cache。 至于IntegerCache类是如何工作的,下一节将会详细分析它。)第3个valueOf为了能提高效率,会先判断是否能够cache,如果不能cache则根据int的值来new出新的Integer对象,并返回。

4.2 decode

decode方法不同于valueOf中的内核parseInt的不同之处在于parseInt将String转int时,String中不能带有如16进制特有的”Ox”,’#’等字符,而decode不需要接收进制数的参数,直接根据String的内容来进行解析并返回Integer。代码如下:

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

//判断是否为16进制或8进制
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 {
//此时valueOf返回的值域是-2147483647~2147483647
result = Integer.valueOf(nm.substring(index), radix);
result = negative ? Integer.valueOf(-result.intValue()) : result;
} catch (NumberFormatException e) {
//在try中认为-2147483648是异常,所以再解析一次
String constant = negative ? ("-" + nm.substring(index))
: nm.substring(index);
result = Integer.valueOf(constant, radix);
}
return result;
}

从整个程序来看,个人感觉decode只是在valueOf的基础上加上了16进制和8进制的前置字符解析,相当于对valueOf的装饰。在实现上
值得一提的是在catch NumberFormatException的时候对-2147483648又进行了一次重新的解析,这是为什么呢?这是因为try中的nm根据起始位置拿到子串后是一个代表正数的String(符号位被跳过了)。假设现在这个提取出的Stringa=”2147483648”,那么valueOf调用的parseInt会认为这个数太大了,超出了范围,会抛出NumberFormatException异常(详情请看3.1)。所以在catch要再解析一次,如果这一次还出错,那么毫无疑问JVM将直接终止程序。

5. IntegerCache

这个类是Integr的静态内部类,主要功能是将值为-128到127并且能够自动装箱的对象进行缓存,并将这些对象在类加载时存放在常量池中。以提高在自动装箱时的效率,并减少内存分配和撤销的开销。(PS:只有在自动装箱时和调用valueOf时才会使用到缓存) 代码如下:

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

从代码中可以看出可以通过修改配置文件来修改cache的最大值的范围。至于配置文件怎么设置,日后再说,先占个坑。。。而在用构造函数构造Intger对象时为什么不会用到缓存呢?答案就在这里。

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

6. 各种位的骚操作

Integer类提供了对int的各种位操作,如highestOneBit,lowestOneBit,numberOfTrailingZeros等。下面将对这些位操作方法进行理解和分析。

6.1 public static int highestOneBit(int i)

这个方法的作用是获取i的最高位,并且后面的额位全部补0,并将这个数返回。代码如下:

    public static int highestOneBit(int i) {
// HD, Figure 3-1
//逐步扩大区域地将最高位后面所有位置1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
//这里>>>是因为如果i是负数那么结果会是0
return i - (i >>> 1);
}

为了理解这个算法套路,举个例子。假设i=446,那么i的二进制形式如下:

00000000 00000000 00000001 10111110

执行第1行代码时,处理过程如下:

  00000000 00000000 00000000 11011111  (i>>1)
| 00000000 00000000 00000001 10111110 (i)
--------------------------------------------

00000000 00000000 00000001 11111111

执行第2行代码时,处理过程如下:

  00000000 00000000 00000000 01111111  (i>>2)
| 00000000 00000000 00000001 11111111 (i)
--------------------------------------------

00000000 00000000 00000001 11111111

执行第3行代码时,处理过程如下:

  00000000 00000000 00000000 00011111  (i>>4)
| 00000000 00000000 00000001 11111111 (i)
--------------------------------------------

00000000 00000000 00000001 11111111

执行第4行代码时,处理过程如下:

  00000000 00000000 00000000 00000001  (i>>8)
| 00000000 00000000 00000001 11111111 (i)
--------------------------------------------

00000000 00000000 00000001 11111111

执行第5行代码时,处理过程如下:

  00000000 00000000 00000000 00000000  (i>>16)
| 00000000 00000000 00000001 11111111 (i)
--------------------------------------------

00000000 00000000 00000000 00111111

执行第6行代码时,处理过程如下:


00000000 00000000 00000001 11111111 (i)
- 00000000 00000000 00000000 11111111 (i>>>1)
--------------------------------------------

00000000 00000000 00000001 00000000

从上面的过程可以看出这个算法的思想是先将i最高位后面的位都置为1,然后用i-(i>>>1),这个式子等价于将最高位后面的所有位取反。

6.2 public static int lowestOneBit(int i)

这个方法的作用和6.1的方法的作用类似,只不过这个是找最低位的1的位置,然后后面的位全部补0,并将这个数返回。代码如下:

    public static int lowestOneBit(int i) {
// HD, Section 2-1
return i & -i;
}

这个方法只有一行代码,但利用了负数的二进制是正数的补码取反+1的性质。举个栗子:现在i=10,那么算法的执行流程是这样的:

  00000000 00000000 00000000 00001010  (i)
& 11111111 11111111 11111111 11110110 (-i)
--------------------------------------------

00000000 00000000 00000001 00000010

这位运算简直骚的一批。。。

6.3 public static int bitCount(int i)

这个方法用于计算一个整数的二进制表示式中有多少个1。该算法采用的二分的思想,两两一组相加,之后四个四个一组相加,接着八个八个,最后就得到各位之和了。。代码如下:

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

同样为了更直观的理解算法的套路,举个栗子:假设i=139。那么第1行代码的执行过程如下:

  00000000 00000000 00000000 10001011  (i)
- 00000000 00000000 00000000 01000101 (i>>>1)
& 01010101 01010101 01010101 01010101 (0x55555555)
--------------------------------------------

00000000 00000000 00000000 10001011 (i)
- 00000000 00000000 00000000 01000101 (中间结果)
--------------------------------------------

00000000 00000000 00000000 01000110 (i)

在这里其实进行了两两分组,将10001011(前面的0已省略)分成了10 00 10 11,分别表示有1,0,1,2个1。这些数据用二进制表示成01 00 01 10,合起来就是01000110.也就是这一步的最终结果。

第2行代码的执行过程如下:

  00000000 00000000 00000000 01000110  (i)
& 00110011 00110011 00110011 00110011 (0x33333333)
+ 00000000 00000000 00000000 00010001 (i>>>2)
& 00110011 00110011 00110011 00110011 (0x33333333)
--------------------------------------------

00000000 00000000 00000000 00000010 (中间结果)
+ 00000000 00000000 00000000 00010001 (中间结果)
--------------------------------------------

00000000 00000000 00000000 00010011 (i)

同样,和上一步类似,这里对原始的i进行了四四分组,将10001011(前面的0已省略)分成了1000 1011,分别表示有1,3个1.这些数据用二进制表示成0001 0011.合起来就是00010011,也就是这一步的最终结果。

第3行代码的执行过程如下:

  00000000 00000000 00000000 00010011  (i)
+ 00000000 00000000 00000000 00000001 (i>>>4)
& 00001111 00001111 00001111 00001111 (0x0f0f0f0f)
--------------------------------------------

00000000 00000000 00000000 00010100 (中间结果)
& 00001111 00001111 00001111 00001111 (0x0f0f0f0f)
--------------------------------------------

00000000 00000000 00000000 00000100 (i)

第4行代码的执行过程如下:

  00000000 00000000 00000000 00000100  (i)
& 00000000 00000000 00000000 00000000 (i>>>8)
--------------------------------------------

00000000 00000000 00000000 00000100

第5行代码的执行过程如下:

  00000000 00000000 00000000 00000100  (i)
& 00000000 00000000 00000000 00000000 (i>>>16)
--------------------------------------------

00000000 00000000 00000000 00000100 (i)

第6行代码的执行过程如下:

  00000000 00000000 00000000 00000100  (i)
& 00000000 00000000 00000000 00111111 (0x3f)
--------------------------------------------

00000000 00000000 00000000 00000100 (i=4)

6.4 public static int rotateLeft(int i, int distance)

将数的二进制码向左旋转,代码如下:

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

假设i=-139,distance=5,那么计算过程如下:

  11111111 11111111 11101110 10100000 (i<<5)
| 00000000 00000000 00000000 00011111 (i>>>-5)
--------------------------------------------

11111111 11111111 11101110 10111111

其实算法的思路就是先左移distance个位,此时distance后面的位全部是0。然后无符号右移-distance个位,把左移之前的位提取出来。最后按位或就得到了左旋转的结果。(PS:右旋转也是同样的套路,不再复述

6.5 public static int 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;
}

这个算法的思想和6.3的算法差不多(看到这里应该知道0x55555555,0x33333333,0x0f0f0f0f代表什么意思了)。就是先2位2位的一组,交换前后各一半,接着4位4位的一组,交换前后各一半,依此类推。下面举例说明:为简单起见,假设i的总共就8位,i的二进制位的下标为12345678。

先看(i & 0x55555555) << 1 | (i >>> 1) & 0x5555555。这句其实相当于(i & 0x55) << 1 | (i & 0xAA ) >> 1。0x55其实就是01010101, 0xAA就是10101010。那么i&0x55就成了02040608,而i&0xAA就成了10305070,然后(i&0x55)<<1就成了20406080,(i&0xAA)>>>1就成了01030507。然后合体就成了21436587。这样就每2位为一组,每组的前后各一半进行交换。后面的过程可以以此类推。这套路帧的骚~~~

智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告