(27) 剖析包装类 (中) / 计算机程序的思维逻辑-演道网
查看历史文章,请点击上方链接关注公众号。
本节继续探讨包装类,主要介绍Integer类,下节介绍Character类,Long与Integer类似,就不再单独介绍了,其他类基本已经介绍完了,不再赘述。
一个简单的Integer还有什么要介绍的呢?它有一些二进制操作,我们来看一下,另外,我们也分析一下它的valueOf实现。
为什么要关心实现代码呢?大部分情况下,确实不用关心,我们会用它就可以了,我们主要是为了学习,尤其是其中的二进制操作,二进制是计算机的基础,但代码往往晦涩难懂,我们希望对其有一个更为清晰深刻的理解。
我们先来看按位翻转。
位翻转
用法
Integer有两个静态方法,可以按位进行翻转:
public static int reverse(int i)
public static int reverseBytes(int i)
位翻转就是将int当做二进制,左边的位与右边的位进行互换,reverse是按位进行互换,reverseBytes是按byte进行互换。我们来看个例子:
int a = 0x12345678;
System.out.println(Integer.toBinaryString(a));int r = Integer.reverse(a);
System.out.println(Integer.toBinaryString(r));int rb = Integer.reverseBytes(a);
System.out.println(Integer.toHexString(rb));
a是整数,用十六进制赋值,首先输出其二进制字符串,接着输出reverse后的二进制,最后输出reverseBytes的十六进制,输出为:
10010001101000101011001111000
11110011010100010110001001000
78563412
reverseBytes是按字节翻转,78是十六进制表示的一个字节,12也是,所以结果78563412是比较容易理解的。
二进制翻转初看是不对的,这是因为输出不是32位,输出时忽略了前面的0,我们补齐32位再看:
00010010001101000101011001111000
00011110011010100010110001001000
这次结果就对了。
这两个方法是怎么实现的呢?
reverseBytes
来看reverseBytes的代码:
public static int reverseBytes(int i) {
return ((i >>> 24) ) |
((i >> 8) & 0xFF00) |
((i << 8) & 0xFF0000) |
((i << 24));
}
以参数i等于0x12345678为例,我们来分析执行过程:
i>>>24 无符号右移,最高字节挪到最低位,结果是 0x00000012。
(i>>8) & 0xFF00,左边第二个字节挪到右边第二个,i>>8结果是 0x00123456,再进行 & 0xFF00,保留的是右边第二个字节,结果是0x00003400。
(i << 8) & 0xFF0000,右边第二个字节挪到左边第二个,i<<8结果是0x34567800,再进行 & 0xFF0000,保留的是右边第三个字节,结果是0x00560000。
i<<24,结果是0x78000000,最右字节挪到最左边。
这四个结果再进行或操作|,结果就是0x78563412,这样,通过左移、右移、与和或操作,就达到了字节翻转的目的。
reverse
我们再来看reverse的代码:
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;
}
这段代码虽然很短,但非常晦涩,到底是什么意思呢?
代码第一行是一个注释, “HD, Figure 7-1″,这是什么意思呢?HD表示的是一本书,书名为Hacker’s Delight,HD是它的缩写,Figure 7-1是书中的图7-1,这本书中,相关内容如下图所示:
可以看出,Integer中reverse的代码就是拷贝了这本书中图7-1的代码,这个代码的解释在图中也说明了,我们翻译一下。
高效实现位翻转的基本思路,首先交换相邻的单一位,然后以两位为一组,再交换相邻的位,接着是四位一组交换、然后是八位、十六位,十六位之后就完成了。这个思路不仅适用于二进制,十进制也是适用的,为便于理解,我们看个十进制的例子,比如对数字12345678进行翻转,
第一轮,相邻单一数字进行互换,结果为:
21 43 65 87
第二轮,以两个数字为一组交换相邻的,结果为:
43 21 87 65
第三轮,以四个数字为一组交换相邻的,结果为:
8765 4321
翻转完成。
对十进制而言,这个效率并不高,但对于二进制,却是高效的,因为二进制可以在一条指令中交换多个相邻位。
这行代码就是对相邻单一位进行互换:
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;
同理,下面代码就是以四位为一组,进行交换。
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
到以八位为单位交换时,就是字节翻转了,可以写为如下更直接的形式,代码和reverseBytes基本完全一样。
i = (i << 24) | ((i & 0xff00) << 8) |
((i >>> 8) & 0xff00) | (i >>> 24);
reverse代码为什么要写的这么晦涩呢?或者说不能用更容易理解的方式写吗?比如说,实现翻转,一种常见的思路是,第一个和最后一个交换,第二个和倒数第二个交换,直到中间两个交换完成。如果数据不是二进制位,这个思路是好的,但对于二进制位,这个效率比较低。
CPU指令并不能高效的操作单个位,它操作的最小数据单位一般是32位(32位机器),另外,CPU可以高效的实现移位和逻辑运算,但加减乘除则比较慢。
reverse是在充分利用CPU的这些特性,并行高效的进行相邻位的交换,也可以通过其他更容易理解的方式实现相同功能,但很难比这个代码更高效。
循环移位
用法
Integer有两个静态方法可以进行循环移位:
public static int rotateLeft(int i, int distance)
public static int rotateRight(int i, int distance)
rotateLeft是循环左移,rotateRight是循环右移,distance是移动的位数,所谓循环移位,是相对于普通的移位而言的,普通移位,比如左移2位,原来的最高两位就没有了,右边会补0,而如果是循环左移两位,则原来的最高两位会移到最右边,就像一个左右相接的环一样。我们来看个例子:
int a = 0x12345678;
int b = Integer.rotateLeft(a, 8);
System.out.println(Integer.toHexString(b));int c = Integer.rotateRight(a, 8);
System.out.println(Integer.toHexString(c))
b是a循环左移8位的结果,c是a循环右移8位的结果,所以输出为:
34567812
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);
}
这两个函数中令人费解的是负数,如果distance是8,那 i>>>-8是什么意思呢?其实,实际的移位个数不是后面的直接数字,而是直接数字的最低5位的值,或者说是直接数字 & 0x1f的结果。之所以这样,是因为5位最大表示31,移位超过31位对int整数是无效的。
理解了移动负数位的含义,我们就比较容易上面这段代码了,比如说,-8的二进制表示是:
11111111111111111111111111111000
其最低5位是11000,十进制就是24,所以i>>>-8就是i>>>24,i<<8 | i>>>24就是循环左移8位。
上面代码中,i>>>-distance就是 i>>>(32-distance),i<<-distance就是i<<(32-distance)。 按位查找、计数
Integer中还有其他一些位操作,包括:
public static int signum(int i)
查看符号位,正数返回1,负数返回-1,0返回0
public static int lowestOneBit(int i)
找从右边数第一个1的位置,该位保持不变,其他位设为0,返回这个整数。比如对于3,二进制为11,二进制结果是01,十进制就是1,对于20,二进制是10100,结果就是00100,十进制就是4。
public static int highestOneBit(int i)
找从左边数第一个1的位置,该位保持不变,其他位设为0,返回这个整数。
public static int bitCount(int i)
找二进制表示中1的个数。比如20,二进制是10100,1的个数是2。
public static int numberOfLeadingZeros(int i)
左边开头连续为0的个数。比如20,二进制是10100,左边有27个0。
public static int numberOfTrailingZeros(int i)
右边结尾连续为0的个数。比如20,二进制是10100,右边有两个0。
关于其实现代码,都有注释指向Hacker’s Delight这本书的相关章节,本文就不再赘述了。
valueOf的实现
上节我们提到,创建包装类对象时,可以使用静态的valueOf方法,也可以直接使用new,但建议使用valueOf,为什么呢?我们来看valueOf的代码:
public static Integer valueOf(int i) {
assert IntegerCache.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 property
int h = 127;
String integerCacheHighPropValue =
sun.misc.VM.getSavedProperty(“java.lang.Integer.IntegerCache.high”);
if (integerCacheHighPropValue != null) {
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);
}
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都有类似的实现。这种共享常用对象的思路,是一种常见的设计思路,在<设计模式>这本著作中,它被赋予了一个名字,叫享元模式,英文叫Flyweight,即共享的轻量级元素。
小结
本节介绍了Integer中的一些位操作,位操作代码比较晦涩,但性能比较高,我们详细解释了其中的一些代码,如果希望有更多的了解,可以根据注释,查看Hacker’s Delight这本书。我们同时介绍了valueOf的实现,介绍了享元模式。
下一节,让我们来探讨Character。
———-
更多好评原创文章
— 长文连载,未完待续,敬请关注(点击文章头部公众号链接,或公众号搜索”老马说编程”或”laoma_shuo”,或长按下图二维码关注)
原创文章,保留所有版权,转载请联系后台。
转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn