(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。

———-

更多好评原创文章

(1)  程序大概是怎么回事

(5)  小数计算为什么会出错?

(6)  如何从乱码中恢复 (上)?

(8)  char的真正含义

(12) 函数调用的基本原理

(17) 继承实现的基本原理

(18) 为什么说继承是把双刃剑?

(19) 接口的本质

(20) 为什么要有抽象类?

(21) 内部类的本质

(23) 枚举的本质

(24) 异常 (上)

(25) 异常 (下)

(26) 剖析包装类 (上)


— 长文连载,未完待续,敬请关注(点击文章头部公众号链接,或公众号搜索”老马说编程”或”laoma_shuo”,或长按下图二维码关注)


原创文章,保留所有版权,转载请联系后台。

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

发表评论

电子邮件地址不会被公开。 必填项已用*标注