java深入理解包装类の剖析Integer与二进制算法

文章目录

• • 1、位翻转
  • 2、循环移位

1、位翻转

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

    public static int reverse(int i)public static int reverseBytes(int i)

位翻转就是将int当作二进制，左边的位与右边的位进行互换，reverse是按位进行互换（换的单位是1bit），reverseBytes是按byte进行互换（换的单位是8bit），例如：

        int a = 0x12345678;System.out.println("----a的二进制为----");System.out.println(Integer.toBinaryString(a));int r = Integer.reverse(a);System.out.println("----按位翻转之后a的二进制为----");System.out.println(Integer.toBinaryString(r));int rb = Integer.reverseBytes(a);System.out.println("----按字节翻转之后a的二进制为----");System.out.println(Integer.toHexString(rb));

输出：

----a的二进制为----
10010001101000101011001111000
----按位翻转之后a的二进制为----
11110011010100010110001001000
----按字节翻转之后a的二进制为----
78563412

reverseBytes是按字节翻转的，78是十六进制表示的一个字节（十六进制1位是4个bit）,12也是，78563412是可以理解的。
二进制的翻转乍一看不对，这是因为输出的不是32位的，输出后忽略了前面的0，补全之后如下：

00010010001101000101011001111000
00011110011010100010110001001000

结果就对了。
reverseBytes实现的代码：

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

以i=0x12345678为例：
1）i>>>24 无符号右移，最高字节挪到最低位，结果是0x00000012; (也就是把第1个字节上的数，挪到第4个字节上，需要挪动3个字节的距离，也就是3*8=24位。)

2)(i >> 8 & 0xFF00)：左边第二个字节挪到右边第二个字节，i >>8结果是0x00123456，再进行& FF00（写全就是0x0000FF00，和1进行&运算，可以保留）,保留的是右边第二个字节，结果是0x00003400;(也就是先把左边第二个字节挪到右边第二个字节，然后把除了右边第二个字节之外的数全部置为0)；

'保留原位置上二进制数字的方法：'
0 & 1 = 0;   
1 & 1 = 1;
0 | 0 = 0;
1 | 0 = 1;'把某些位置上置为0：(将其与0进行&运算)'
0x1234 && 0xFFFF = 0'只保留某个位置上的字节数值：(只保留右边第二个字节)'
0x12345678 & 0x0000FF00 = 0x00005600

3）i << 8 & 0xFF0000)：右边第二个字节挪到左边第二个字节，i << 8 , 左移8位（左移一个字节），结果是0x34567800，再进行0xFF0000(补全就是0x00FF0000),结果就0x00560000(只保留从左边第二个字节)

4）i << 24：结果是0x78000000,最右边字节挪到最左边。

然后将这4个结果在进行或操作|，保留每一步留下的数字，结果就是0x78563412.这样就完成了字节翻转操作。
（可以看出依次经过无符号右移24(i>>>24)、左边第二个字节挪到右边第二个字节,并只保留右边第二个字节（i >> 8 & 0xFF00），右边第二个字节挪到左边第二个字节，并只保留左边第二个字节（i << 8 & 0xFF0000)），左移24位（i << 24）完成了字节翻转操作）。
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;}

高效实现位翻转的基本思路是：首先交换相邻的单1位，然后以两位为1组，再交换相邻的位。接着是4位一组交换、然后是8位、16位，16位之后就完成了。这个思路不仅适用于二进制，也适用于十进制。

如：十进制12345678：
第一轮：交换相邻单一位： 21 43 65 87
第二轮：以两个数字交换相邻：43 21 87 65
第三轮：以4个数字位1组交换相邻的：87 65 43 21
翻转完成

对于十进制而言不是高效的，但是对于二进制来言，却是高效的，因为二进制中一条指令中交换多个相邻位：

如:
1、实现相邻单一位进行交换：

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

5的二进制是0101,0x55555555的二进制是01010101010101010101010101010101。
x & 0x55555555可以表示为取x的奇数位

A的二进制是1010,0xAAAAAAAA的二进制是10101010101010101010101010101010.
x & 0xAAAAAAAA可以表示为取x的偶数位

x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >>>1;因此这个代码整体表示为取x的奇数位（偶数位置为0），左移，取x的偶数位（奇数位置为0），右移，然后进行或运算|，合并奇数位偶数位。就完成了相邻单一位互换的目的。
这个代码可以优化为：

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

(x >>>1) & 0x55555555,是右移，然后保留奇数位（相当于保留偶数位右移）
2、同理以下代码实现以两位为一组，对相邻位进行互换：

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

3的二进制是0011，0x33333333的二进制是00110011001100110011001100110011,i & 0x33333333就是取i的以两位为一组的低半部分。
C的二进制是1100，（i & 0xCCCCCCCC）就是取i的以两位为一组的高半部分。

i = (i & 0x33333333) << 2 | （i & 0xCCCCCCCC）>>>2;表示i以两位为一组，低半部分向高位移，高半部分向低位移，然后通过||合并，达到交换的目的：0011<<2=1100,1100>>>2 = 0011,1100||0011=1111.同样，代码可以优化为：

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

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

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

4、到以8位单位交换时，就是字节翻转了，可以写为如下更直接的形式，代码与reverseBytes基本完全一样：

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

reverse利用了CPU可以高效地实现移位和逻辑运算的特性，并行高效地进行相邻位的交换。

2、循环移位

Integer有两个静态方法实现循环移位：

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

rotateLeft方法是循环左移，rotateRight 方法是循环右移，distance是移位的位数。例如：

		int a = 0x12345678;int b = Integer.rotateLeft(a,8);System.out.println("----a循环左移位8位----");System.out.println(Integer.toHexString(b));int c = Integer.rotateRight(a,8);System.out.println("----a循环右移位8位----");System.out.println(Integer.toHexString(c));'结果：'----a循环左移位8位----
34567812
----a循环右移位8位----
78123456

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

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

其中i>>>-distance就是i>>>32-distance

----a二进制是----
10010001101000101011001111000
----a<<8=----
110100010101100111100000000000
----a>>-8=----
10010
----a循环左移位8位后二进制是----
110100010101100111100000010010

3、valueOf的实现

Integer a1 = 2; //相当于 new Integer(2)
Integer a = new Integer(2); //new Integer 已经被视为过时，可以直接写Integer a = 2; 
Integer b = new Integer(2);
Integer b1 = new Integer(200);
System.out.println(a == b);    // false
Integer m = Integer.valueOf(2);
Integer n = Integer.valueOf(2);
System.out.println(m == n);   // true
Integer o2 = Integer.valueOf(200);
Integer o1 = Integer.valueOf(200);
System.out.println(o1==o2);  // false
System.out.println(b1==o1); //false
System.out.println(b==o2); //false

，上面判断之所以不同是因为new Integer()与Integer.valueOf()是有区别的：new Interger()每次都会创建一个对象；而Integer.valueOf()则是使用缓冲池中的对象，如果缓冲池中（存在的值范围在-128~127内）存在这个值，即使多次调用也会取得同一个对象的引用，如果不存在则使用new创建。
缓冲池
以 Integer x = Integer.valueOf(2); 为例，首先先判断缓冲池中是否有当前数据，有就从InegerCache的缓存cache[] 数组中取出并返回，不同包装类的 cache[] 范围不同。

valueOf的实现源码：基于java 7

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

他使用了IntegerCache,这是一个私有静态内部类，代码如下：

private static class IntegerCache {static final int low = -128;static final int high;static final Integer cache[];static {// high value may be configured by propertyint 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_VALUEh = 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++);}private IntegerCache() {}}

IntegerCache表示Integer缓冲，其中cache变量是一个静态Integer数组，在静态方法初始化代码中被初始化，默认情况下，保存了-128~127共256个整数对应的Integer对象。
在valueOf代码中，如果数值位于被缓存的范围，即默认-128~127，直接从IntegerCache中获取已预先创建的Integer对象，只有不在缓存范围时，才通过new创建对象。

通过共享常用对象，可以节省内存空间，由于Integer是不可变的，所以缓存的对象可以安全被共享。Boolean、Byte、Short、Long、Character都有类似的实现。这种共享常用对象的思路是一种常见的思路，他有一个名字，叫做享元模式。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！