Integer与二进制算法1、位翻转2、循环位移3、valueOf的实现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){inta0x12345678;System.out.println(Integer.toBinaryString(a));intrInteger.reverse(a);System.out.println(Integer.toBinaryString(r));intrbInteger.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((i24))|((i8)0xFF00)|((i8)0xFF0000)|((i24));}代码比较晦涩以参数i等于0x12345678为例我们来分析执行过程i24无符号右移最高字节挪到最低位结果是0x0000001200010010 00110100 01010110 01111000 24 00000000 00000000 00000000 00100100(i8) 0xFF00左边第二个字节挪到右边第二个i8结果是0x00123456再进行 0xFF00保留的是右边第二个字节结果是0x0000340000010010 00110100 01010110 01111000 8 00000000 00010010 00110100 01010110 即0x00123456 00000000 00000000 11111111 00000000 - 00000000 00000000 00110100 00000000 即 0x00003400(i 8) 0xFF0000右边第二个字节挪到左边第二个i8结果是0x34567800再进行 0xFF0000保留的是右边第三个字节结果是0x0056000000010010 00110100 01010110 01111000 8 00110100 01010110 01111000 00000000 即0x00123456 00000000 11111111 00000000 00000000 - 00000000 01010110 00000000 00000000 即 0x00560000i24结果是0x78000000最右字节挪到最左边。000100100011010001010110011110002401111000000000000000000000000000即0x78000000这4个结果再进行或操作|结果就是0x78563412这样通过左移、右移、与和或操作就达到了字节翻转的目的。我们再来看reverse的代码publicstaticintreverse(inti){// HD, Figure 7-1i(i0x55555555)1|(i1)0x55555555;i(i0x33333333)2|(i2)0x33333333;i(i0x0f0f0f0f)4|(i4)0x0f0f0f0f;i(i24)|((i0xff00)8)|((i8)0xff00)|(i24);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(x0x55555555)1|(x0xAAAAAAAA)1;5的二进制表示是0101,0x55555555的二进制表示是01010101010101010101010101010101x 0x55555555就是取x的奇数位。A的二进制表示是1010,0xAAAAAAAA的二进制表示是10101010101010101010101010101010x 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的二进制表示是00110011001100110011001100110011x 0x33333333就是取x以两位为一组的低半部分。C的二进制表示是1100,0xCCCCCCCC的二进制表示是11001100110011001100110011001100x 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而如果是循环左移两位则原来的最高两位会移到最右边就像一个左右相接的环一样。看个例子inta0x12345678;intbInteger.rotateLeft(a,8);System.out.println(Integer.toHexString(b));intcInteger.rotateRight(a,8);System.out.println(Integer.toHexString(c))b是a循环左移8位的结果c是a循环右移8位的结果所以输出为34567812 78123456这两个函数的实现代码为publicstaticintrotateLeft(inti,intdistance){return(idistance)|(i-distance);}publicstaticintrotateRight(inti,intdistance){return(idistance)|(i-distance);}这两个函数中令人费解的是负数如果distance是8那i-8是什么意思呢其实实际的移位个数不是后面的直接数字而是直接数字的最低5位的值或者说是直接数字0x1f的结果。之所以这样是因为5位最大表示31移位超过31位对int整数是无效的。11111111111111111111111111111000其最低5位是11000十进制表示就是24所以i-8就是i24, i8 | i24就是循环左移8位。上面代码中i-distance就是i(32-distance), i-distance就是i(32-distance)。3、valueOf的实现在前面我们提到创建包装类对象时可以使用静态的valueOf方法也可以直接使用new但建议使用valueOf方法为什么呢我们来看Integer的valueOf的代码基于Java 8​publicstaticIntegervalueOf(inti){if(iIntegerCache.lowiIntegerCache.high)returnIntegerCache.cache[i(-IntegerCache.low)];returnnewInteger(i);}它使用了IntegerCache这是一个私有静态内部类如代码所示。privatestaticclassIntegerCache{staticfinalintlow-128;staticfinalinthigh;staticfinalIntegercache[];static{// high value may be configured by propertyinth127;StringintegerCacheHighPropValuesun.misc.VM.getSavedProperty(java.lang.Integer.IntegerCache.high);if(integerCacheHighPropValue!null){try{intiparseInt(integerCacheHighPropValue);iMath.max(i,127);// Maximum array size is Integer.MAX_VALUEhMath.min(i,Integer.MAX_VALUE-(-low)-1);}catch(NumberFormatExceptionnfe){// If the property cannot be parsed into an int, ignore it.}}highh;cachenewInteger[(high-low)1];intjlow;for(intk0;kcache.length;k)cache[k]newInteger(j);// range [-128, 127] must be interned (JLS7 5.1.7)assertIntegerCache.high127;}privateIntegerCache(){}}IntegerCache表示Integer缓存其中的cache变量是一个静态Integer数组在静态初始化代码块中被初始化默认情况下保存了-128127共256个整数对应的Integer对象。在valueOf代码中如果数值位于被缓存的范围即默认-128127则直接从Integer-Cache中获取已预先创建的Integer对象只有不在缓存范围时才通过new创建对象。通过共享常用对象可以节省内存空间由于Integer是不可变的所以缓存的对象可以安全地被共享。Boolean、Byte、Short、Long、Character都有类似的实现。这种共享常用对象的思路是一种常见的设计思路它有一个名字叫享元模式英文叫Flyweight即共享的轻量级元素。