Java Integer变态(bit)函数浅析-IT面试星球

前阵子分享过Integer的几个特殊方法,没提原理. 今天来填个坑, 解释下Integer中的几个奇葩函数是怎么工作的.

取正负性(signum)

先看最简单的方法, 根据数字的±,返回[0,1,-1].

这个如果我们自己写的版本应该是这样的:

i>0?1:i==0?0:-1

如果看官方写法, 则是这样的.

return (i >> 31) | (-i >>> 31);

要解释这个, 需要回忆下>>和>>>的差别,>>>是无符号右移, 左侧会补0,>>是普通右移, 左侧补的是符号位. 正数,二者没差别,差别主要在负数上.

正数>>31==0, 正数>>>31 ==0
负数>>31==-1, 负数>>>31 ==1

这个代码的正确性显然没问题, i==0 结果必然正确

i>0 时候,左侧必定为0,式子右半部分起作用, 返回1
i<0 时候, 式子的左半部分起作用,右侧必定为0, 返回-1

翻转

特殊函数里, 有趣的还是bit翻转部分.看这段代码,需要先上一个辅助函数, 把数字int转成32位的,方便查看.

// 打印二进制
static void logBin(int i){
System.out.println(String.format("%32s", Integer.toBinaryString(i)).replace(" ","0"));
}

翻转byte

这个比较好写，我们自己实现的话，可能是这样：

用掩码取出4个byte
手动安排这4个byte
合并成数字

(i & 0x000000ff) << 24|        这是右一的byte挪到了左一
    (i & 0x0000ff00) << 8 |    这是右二的byte挪到了左二
    (i & 0x00ff0000) >> 16 |   这是左二的byte移到右二
    (i & 0xff000000) >>> 24    这是左一的byte移到右一

写法没啥大猫病，除了每次取byte用的掩码都不一样，有点浪费.官方的写法是这样的。

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

比较好解释的:

i<<24 左移24位, 右侧补零，左边的24个byte都丢了，不用掩码也没事，可以省略
(i & 0xff00) << 8 先用掩码保字节，后移位
(i >>> 8) & 0xff00 先移位，后保字节
i >>> 24 无符号右移24位，右面的都要丢掉，不用掩码也没事

代码和上面的简单版本是一样的，关键变动是2，3句，为了只使用0xff00这一个掩码，省一个变量的内存。标准库王者，强悍如斯。

用途

这个代码主要是对字节序进行处理，大端和小端问题会涉及到翻转的操作，在网络相关代码里会有用到。比如说有一个小有名气的网络包netty, 大量用到了nativeByteOrder ? value : Integer.reverseBytes(value)来处理字节序相关内容。

翻转bit

翻转bit的代码，其实也没什么好办法。要是我来写，可能会这样：

[1-32]先16bit一组对翻，变成[17-32，1-16]
[1-16]进行8bit一组对翻，变成[9-16,1-8]
[1-8]进行4bit一组对翻，变成[5-8,1-4]
[1-4]进行2bit一组对翻
[1-2]翻

理论上,按照对数考虑, 32bit应该5次内就翻完了. 写出来是这样的.

        i = i >>> 16 | i << 16;
        i = (i & 0xff00ff00) >>> 8 | (i & 0x00ff00ff) << 8;
        i = (i & 0xf0f0f0f0) >>> 4 | (i & 0x0f0f0f0f) << 4;
        i = (i & 0xcccccccc) >>> 2 | (i & 0x33333333) << 2;
        i = (i & 0xaaaaaaaa) >>> 1 | (i & 0x55555555) << 1;
        return i;

然后对比了下官方写法… 我乐了.咱们是自顶向下拆的写法. 官方是从下往上, 1,2,4先翻出来一个8bit的版本,然后,最后几行,不就是翻转byte吗?

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

这里官方又把掩码给优化掉了.我们用了8个掩码, 官方用了4个. 内存这块,官方拿捏的确实到位.

用途

这个方法其实也是数据流相关的. 如果反了, 就会出现需要用这个函数反过来的情况.目前只在H2数据库和Java9的CRC32类里见到过.

bit特征

前导0数量(numberOfLeadingZeros)

0前面32个0, 负数开头符号位是1根本没0.

这里只需要处理正数,算法部分,则是一个熟悉的算法.

如果i大于 16bit能表示的最大值, 那在剩下16bit的内容里搜索就行.问题缩小到16bit的规模
如果i大于8bit能表示的最大值, 那在剩下的8bit内容里搜索
…..
直到最后,在一个2bit大小的空间里处理就好了,问题搞定.

public static int numberOfLeadingZeros(int i) {
    // HD, Count leading 0's
    if (i <= 0)
        return i == 0 ? 32 : 0;
    int n = 31;
    if (i >= 1 << 16) { n -= 16; i >>>= 16; }
    if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
    if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
    if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
    return n - (i >>> 1);
}

这部分写法基本都是对半往下减, 就算64bit也不会多太多运算的.

后缀0数量

public static int numberOfTrailingZeros(int i) {
    // HD, Count trailing 0's
    i = ~i & (i - 1);
    if (i <= 0) return i & 32;
    int n = 1;
    if (i > 1 << 16) { n += 16; i >>>= 16; }
    if (i > 1 <<  8) { n +=  8; i >>>=  8; }
    if (i > 1 <<  4) { n +=  4; i >>>=  4; }
    if (i > 1 <<  2) { n +=  2; i >>>=  2; }
    return n + (i >>> 1);

关键在第一步:~n&(n-1), 这个玩法可以把尾部的0全都变为1.

比如 1100,经过这个操作~(1100)&(1100-1)=0011&(1011)=0011,就变成了尾部一堆1.如果我们愿意使用bitCount的话, 就可以直接出结果了.

后面的写法和上面前缀1的写法很像,就不分析了.

最靠前的1 highestOneBit

这块有两个写法.

// Java8写法  从下往上构造
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
        
//Java17写法,这个写法切换到了用前导0的函数
i & (MIN_VALUE >>> numberOfLeadingZeros(i));

这函数估计很多人都很熟悉…因为这其实就是HashMap里的TableSizeFor.

看过 Java8 版本 HashMap 源码的都知道, 里面有一段神奇的代码tableSizeFor, 用来计算内部table的大小.

J K L，公众号：K字的研究冰山一角之tableSizeFor方法从哪里来?

新的HashMap实现里,这块也换成了类似的前导0实现.

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}