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

原文发表时间:2016-07-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

最小生成树判断唯一

题意:若最小生成树唯一则输出权值和,若不唯一输出Not Not Unique! 运用prim算法将最小生成树求出,然后在依次枚举删除最小生成树中的每一条边,判断...

3434
来自专栏xcywt

《Linux命令行与shell脚本编程大全》第二十二章 gawk进阶

gawk是一门功能丰富的编程语言,你可以通过它所提供的各种特性来编写好几程序处理数据。  22.1 使用变量 gawk编程语言支持两种不同类型的变量: 内建变量...

2166
来自专栏简书专栏

Pandas入门2

对于DataFrame,对齐会同时发生在行和列上,两个DataFrame对象相加后,其索引和列会取并集,缺省值用NaN。

2392
来自专栏Petrichor的专栏

tensorflow编程: Variables

tf.moving_average_variables tf.global_variables_initializer tf.local_variabl...

1721
来自专栏杂七杂八

Matlab中的括号()[]{}

Matlab中经常会用到括号去引用某Array或者是cell的内容,但三者有什么具体区别呢? [ ] 中括号用来构建向量(Vectors)或者是矩阵(Ma...

3037
来自专栏微信公众号:Java团长

Java 泛型详解

泛型是Java中一个非常重要的知识点,在Java集合类框架中泛型被广泛应用。本文我们将从零开始来看一下Java泛型的设计,将会涉及到通配符处理,以及让人苦恼的类...

1171
来自专栏mukekeheart的iOS之旅

No.004 Median of Two Sorted Arrays

4. Median of Two Sorted Arrays Total Accepted: 104147 Total Submissions: 539044 ...

2279
来自专栏琦小虾的Binary

map 学习(下)——C++ 中的 hash_map, unordered_map

map 学习(下)——C++ 中的 hash_map, unordered_map 接上篇《map 学习(一)——C++中 map 的使用》。 一、hash_m...

3.1K7
来自专栏移动开发面面观

快速排序法及优化

1684
来自专栏和蔼的张星的图像处理专栏

70. 二叉树的层次遍历 II借助stack

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)。 原题见这里 这是另外一个题的扩展,见69题...

1213

扫码关注云+社区

领取腾讯云代金券