0%

JDK8 Integer 之 numberOfLeadingZeros 和 numberOfTrailingZeros

发表于

问题描述

最近翻看 JDK8 源码，发现 Integer 的两个有意思的方法：numberOfLeadingZeros 和 numberOfTrailingZeros。

这两个方法作用很好理解，就是返回一个二进制整数最左边或最右边连续的0的个数。

普通人的解法

粗略地想了下，我应该会这么实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int getIntegerLeadingZeros(int i) {
    if (i < 0)
        return 0;
    if (i == 0)
        return 32;
    int c = 0;
    while (i > 0) {
        i >>>= 1;
        c++;
    }
    return 32 - c;
}

public static int getIntegerTrailingZeros(int i) {
    if (i == 0)
        return 32;
    int c = 0;
    while (i != 0) {
        i <<= 1;
        c++;
    }
    return 32 - c;
}

JDK 的实现

但 JDK8 源码确实一堆位运算，咋一看还没看明白：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

public static int numberOfTrailingZeros(int i) {
    // HD, Figure 5-14
    int y;
    if (i == 0) return 32;
    int n = 31;
    y = i <<16; if (y != 0) { n = n -16; i = y; }
    y = i << 8; if (y != 0) { n = n - 8; i = y; }
    y = i << 4; if (y != 0) { n = n - 4; i = y; }
    y = i << 2; if (y != 0) { n = n - 2; i = y; }
    return n - ((i << 1) >>> 31);
}

其实就是用二分的思想来求解。因为上面我的写法的时间复杂度是 O(n)（n 是 32 - 左端或右端连续0的个数），用二分的解法可以达到 O(logn)。不得不说，JDK 作为基础库，充分考虑了性能。

如何理解上面这些位运算呢？

JDK 实现的理解

numberOfLeadingZeros

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int numberOfLeadingZeros(int i) {
    if (i == 0)
        return 32;
    int n = 1;
    // 如果从左往右第一个1出现在低16位，那么结果加16，然后把低16位移到高16位
    // 如：  0000 0000 0000 0000 0000 0000 0000 0010
    // 变为：0000 0000 0000 0010 0000 0000 0000 0000
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    // 如果从左往右第一个1出现在低8位，那么结果加8，然后把低8位移到高8位
    // 变为：0000 0010 0000 0000 0000 0000 0000 0000
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    // 如果从左往右第一个1出现在低4位，那么结果加4，然后把低4位移到高4位
    // 变为：0010 0000 0000 0000 0000 0000 0000 0000
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    // 如果从左往右第一个1出现在低2位，那么结果加2，然后把低2位移到高2位
    // 变为：10 0000 0000 0000 0000 0000 0000 0000 00
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    // 如果如果从左往右第一个1出现在倒数第2低位，那么结果需要减1，因为n的初始值为1
    n -= i >>> 31;
    return n;
}

上面 n 的初始值做了特殊处理，纯粹的二分可以写成如下：

1
2
3
4
5
6
7
8
9
10
11
public static int numberOfLeadingZeros2(int i) {
    if (i == 0)
        return 32;
    int n = 0;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    if (i >>> 31 == 0) { n +=  1; }
    return n;
}

numberOfTrailingZeros

求正数二进制表示右端连续0的个数的方法类似，不过求左端的0时要把左边的0右移判断结果是否为0，而求右端的0时需要把右端的0左移判断结果是否为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int numberOfTrailingZeros(int i) {
    int y;
    if (i == 0) return 32;
    int n = 31;
    // 如果从右往左第一个1出现在低16位，那么结果减16，然后把低16位移到高16位
    y = i <<16; if (y != 0) { n = n -16; i = y; }
    // 如果从右往左第一个1出现在低8位，那么结果减8，然后把低8位移到高8位
    y = i << 8; if (y != 0) { n = n - 8; i = y; }
    // 如果从右往左第一个1出现在低4位，那么结果减4，然后把低4位移到高4位
    y = i << 4; if (y != 0) { n = n - 4; i = y; }
    // 如果从右往左第一个1出现在低2位，那么结果减2，然后把低2位移到高2位
    y = i << 2; if (y != 0) { n = n - 2; i = y; }
    return n - ((i << 1) >>> 31);
}

上面 n 的初始也可以设为0，然后后面采用加法，只不过这样每次判断要进行两次位移，相比上面每次判断只进行一次位移比较高效。

1
2
3
4
5
6
7
8
9
10
11
public static int numberOfTrailingZeros2(int i) {
    if (i == 0) return 32;
    int n = 0;
    // 如果从右往左第一个1出现在高16位，那么结果加16，然后把高16位移到低16位
    if (i << 16 == 0) { n += 16; i >>>= 16; }
    if (i << 24 == 0) { n +=  8; i >>>=  8; }
    if (i << 28 == 0) { n +=  4; i >>>=  4; }
    if (i << 30 == 0) { n +=  2; i >>>=  2; }
    if (i << 31 == 0) { n +=  1; i >>>=  1; }
    return n;
}

可如果是这样的话，为何求左端的0的个数时不也采用类似做法，减少位移的次数？

引申问题

如下写法，用 numberOfTrailingZeros 的思想求 numberOfLeadingZeros：

1
2
3
4
5
6
7
8
9
10
11
public static int numberOfLeadingZeros3(int i) {
    int y;
    if (i == 0) return 32;
    int n = 31;
    // 如果从左往右第一个1出现在高16位，那么结果减16，然后把高16位移到低16位
    y = i >>>16; if (y != 0) { n = n -16; i = y; }
    y = i >>> 8; if (y != 0) { n = n - 8; i = y; }
    y = i >>> 4; if (y != 0) { n = n - 4; i = y; }
    y = i >>> 2; if (y != 0) { n = n - 2; i = y; }
    return n - (i >>> 1);
}

也许，numberOfTrailingZeros 和 numberOfLeadingZeros 实现思路是判断第一位1（不管是最左边还是最右边）是否在低 x 位吧，然后不断把这低 x 位移到高 x 位进行判断（x=16, 8, 4, 2）。

参考：