Java——Integer与二进制算法

1、位翻转

Integer有两个静态方法，可以按位进行翻转：

/* 将一个 int类型的二进制表示按位反转（reverse bits） 5 -> 00000000 00000000 00000000 00000101 按位翻转 -> 10100000 00000000 00000000 00000000 -> -1610612736 */System.out.println(Integer.reverse(5));//-1610612736/* 将 int的 4 个字节顺序反转，只反转“字节”，不反转单个 bit，即 byte3 byte2 byte1 byte0 转换为-> byte0 byte1 byte2 byte3 5 -> 00000000 00000000 00000000 00000101 按位翻转 -> 00000101 00000000 00000000 00000000 -> 83886080 */System.out.println(Integer.reverseBytes(5));//83886080

位翻转就是将int当作二进制，左边的位与右边的位进行互换，reverse是按位进行互换， reverseBytes是按byte进行互换，我们来看个例子：

publicstaticvoidmain(String[]args){inta=0x12345678;System.out.println(Integer.toBinaryString(a));intr=Integer.reverse(a);System.out.println(Integer.toBinaryString(r));intrb=Integer.reverseBytes(a);System.out.println(Integer.toHexString(rb));// 10010001101000101011001111000// 11110011010100010110001001000// 78563412}

a是整数，用十六进制赋值，首先输出其二进制字符串，接着输出reverse后的二进制，最后输出reverseBytes后的十六进制。

reverseBytes是按字节翻转，78是十六进制表示的一个字节，12也是，所以结果78563412是比较容易理解的。二进制翻转初看是不对的，这是因为输出不是32位，输出时忽略了前面的0，我们补齐32位再看：

0001001000110100010101100111100000011110011010100010110001001000

这次结果就对了。

这两个方法是怎么实现的呢？先来看reverseBytes的代码：

publicstaticintreverseBytes(inti){return((i>>>24))|((i>>8)&0xFF00)|((i<<8)&0xFF0000)|((i<<24));}

代码比较晦涩，以参数i等于0x12345678为例，我们来分析执行过程：

1. i>>>24无符号右移，最高字节挪到最低位，结果是0x00000012；

00010010 00110100 01010110 01111000 >>>24 00000000 00000000 00000000 00100100

2. (i>>8) & 0xFF00，左边第二个字节挪到右边第二个，i>>8结果是0x00123456，再进行& 0xFF00，保留的是右边第二个字节，结果是0x00003400；

00010010 00110100 01010110 01111000 >> 8 00000000 00010010 00110100 01010110 & 即（0x00123456） 00000000 00000000 11111111 00000000 -> 00000000 00000000 00110100 00000000 即 （0x00003400）

3. (i << 8) & 0xFF0000，右边第二个字节挪到左边第二个，i<<8结果是0x34567800，再进行& 0xFF0000，保留的是右边第三个字节，结果是0x00560000；

00010010 00110100 01010110 01111000 << 8 00110100 01010110 01111000 00000000 & 即（0x00123456） 00000000 11111111 00000000 00000000 -> 00000000 01010110 00000000 00000000 即 （0x00560000）

4. i<<24，结果是0x78000000，最右字节挪到最左边。

00010010001101000101011001111000<<2401111000000000000000000000000000即（0x78000000）

这4个结果再进行或操作|，结果就是0x78563412，这样，通过左移、右移、与和或操作，就达到了字节翻转的目的。

我们再来看reverse的代码：

publicstaticintreverse(inti){// HD, Figure 7-1i=(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);returni;}

这段代码虽然很短，但非常晦涩，到底是什么意思呢？代码第一行是一个注释，HD表示的是一本书，书名为Hacker’s Delight，中文版为《算法心得：高效算法的奥秘》, HD是它的缩写，Figure 7-1是书中的图7-1,reverse的代码就是复制了这本书中图7-1的代码，书中也说明了代码的思路，我们简要说明。

高效实现位翻转的基本思路是：首先交换相邻的单一位，然后以两位为一组，再交换相邻的位，接着是4位一组交换、然后是8位、16位，16位之后就完成了。这个思路不仅适用于二进制，而且适用于十进制，为便于理解，我们看个十进制的例子。比如对数字12345678进行翻转。

第一轮，相邻单一数字进行互换，结果为：

21 43 65 87

第二轮，以两个数字为一组交换相邻的，结果为：

43218765

第三轮，以4个数字为一组交换相邻的，结果为：

87654321

翻转完成。

对十进制而言，这个效率并不高，但对于二进制而言，却是高效的，因为二进制可以在一条指令中交换多个相邻位。下面代码就是对相邻单一位进行互换：

x=(x&0x55555555)<<1|(x&0xAAAAAAAA)>>>1;

5的二进制表示是0101,0x55555555的二进制表示是：

01010101010101010101010101010101

x & 0x55555555就是取x的奇数位。

A的二进制表示是1010,0xAAAAAAAA的二进制表示是：

10101010101010101010101010101010

x & 0xAAAAAAAA就是取x的偶数位。

(x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >>> 1;

表示的就是x的奇数位向左移，偶数位向右移，然后通过|合并，达到相邻位互换的目的。这段代码可以有个小的优化，只使用一个常量0x55555555，后半部分先移位再进行与操作，变为：

(i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;

同理，如下代码就是以两位为一组，对相邻位进行互换：

i = (i & 0x33333333) << 2 | (i & 0xCCCCCCCC)>>>2;

3的二进制表示是0011,0x33333333的二进制表示是：

00110011001100110011001100110011

x & 0x33333333就是取x以两位为一组的低半部分。C的二进制表示是1100,0xCCCCCCCC的二进制表示是：

11001100110011001100110011001100

x & 0xCCCCCCCC就是取x以两位为一组的高半部分。

(i & 0x33333333) << 2 | (i & 0xCCCCCCCC)>>>2;

表示的就是x以两位为一组，低半部分向高位移，高半部分向低位移，然后通过|合并，达到交换的目的。同样，可以去掉常量0xCCCCCCCC，代码可以优化为：

(i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;

同理，下面代码就是以4位为一组进行交换。

i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;

到以8位为单位交换时，就是字节翻转了，可以写为如下更直接的形式，代码和reverse-Bytes基本完全一样。

i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24);

reverse代码为什么要写得这么晦涩呢？或者说不能用更容易理解的方式写吗？比如，实现翻转，一种常见的思路是：第一个和最后一个交换，第二个和倒数第二个交换，直到中间两个交换完成。如果数据不是二进制位，这个思路是好的，但对于二进制位，这个思路的效率比较低。

CPU指令并不能高效地操作单个位，它操作的最小数据单位一般是32位（32位机器）​，另外，CPU可以高效地实现移位和逻辑运算，但实现加、减、乘、除运算则比较慢。

reverse是在充分利用CPU的这些特性，并行高效地进行相邻位的交换，也可以通过其他更容易理解的方式实现相同功能，但很难比这个代码更高效。

2、循环位移

Integer有两个静态方法可以进行循环移位：

publicstaticintrotateLeft(inti,intdistance)publicstaticintrotateRight(inti,intdistance)

rotateLeft方法是循环左移，rotateRight方法是循环右移，distance是移动的位数。所谓循环移位，是相对于普通的移位而言的，普通移位，比如左移2位，原来的最高两位就没有了，右边会补0，而如果是循环左移两位，则原来的最高两位会移到最右边，就像一个左右相接的环一样。看个例子：

inta=0x12345678;intb=Integer.rotateLeft(a,8);System.out.println(Integer.toHexString(b));intc=Integer.rotateRight(a,8);System.out.println(Integer.toHexString(c))

b是a循环左移8位的结果，c是a循环右移8位的结果，所以输出为：

34567812 78123456

这两个函数的实现代码为：

publicstaticintrotateLeft(inti,intdistance){return(i<<distance)|(i>>>-distance);}publicstaticintrotateRight(inti,intdistance){return(i>>>distance)|(i<<-distance);}

这两个函数中令人费解的是负数，如果distance是8，那i>>>-8是什么意思呢？其实，实际的移位个数不是后面的直接数字，而是直接数字的最低5位的值，或者说是直接数字&0x1f的结果。之所以这样，是因为5位最大表示31，移位超过31位对int整数是无效的。

11111111111111111111111111111000

其最低5位是11000，十进制表示就是24，所以i>>>-8就是i>>>24, i<<8 | i>>>24就是循环左移8位。上面代码中，i>>>-distance就是i>>>(32-distance), i<<-distance就是i<<(32-distance)。

3、valueOf的实现

在前面，我们提到，创建包装类对象时，可以使用静态的valueOf方法，也可以直接使用new，但建议使用valueOf方法，为什么呢？我们来看Integer的valueOf的代码（基于Java 8）​：

publicstaticIntegervalueOf(inti){if(i>=IntegerCache.low&&i<=IntegerCache.high)returnIntegerCache.cache[i+(-IntegerCache.low)];returnnewInteger(i);}

它使用了IntegerCache，这是一个私有静态内部类，如代码所示。

privatestaticclassIntegerCache{staticfinalintlow=-128;staticfinalinthigh;staticfinalIntegercache[];static{// high value may be configured by propertyinth=127;StringintegerCacheHighPropValue=sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");if(integerCacheHighPropValue!=null){try{inti=parseInt(integerCacheHighPropValue);i=Math.max(i,127);// Maximum array size is Integer.MAX_VALUEh=Math.min(i,Integer.MAX_VALUE-(-low)-1);}catch(NumberFormatExceptionnfe){// If the property cannot be parsed into an int, ignore it.}}high=h;cache=newInteger[(high-low)+1];intj=low;for(intk=0;k<cache.length;k++)cache[k]=newInteger(j++);// range [-128, 127] must be interned (JLS7 5.1.7)assertIntegerCache.high>=127;}privateIntegerCache(){}}

IntegerCache表示Integer缓存，其中的cache变量是一个静态Integer数组，在静态初始化代码块中被初始化，默认情况下，保存了-128～127共256个整数对应的Integer对象。

在valueOf代码中，如果数值位于被缓存的范围，即默认-128～127，则直接从Integer-Cache中获取已预先创建的Integer对象，只有不在缓存范围时，才通过new创建对象。

通过共享常用对象，可以节省内存空间，由于Integer是不可变的，所以缓存的对象可以安全地被共享。Boolean、Byte、Short、Long、Character都有类似的实现。这种共享常用对象的思路，是一种常见的设计思路，它有一个名字，叫享元模式，英文叫Flyweight，即共享的轻量级元素。