Fork me on GitHub

JDK里那些有趣的代码(2)

前言

JDK里那些有趣的代码这篇文章。

今天我们来看下另一个比较有意思的代码部分。

在说这个之前,我们先来研究一道比较有意思的题目。

使用Java程序 获取下一个最小的比入参n大的2的高次幂

这个题的意思就是:比如入参为10,则最小的比入参大的2的高次幂为 ${2}^{4} = {16}$;入参为100,则最小的比入参大的2的高次幂为${2}^{7}={128}$。

分析

对于这种题目,我们如何处理呢?

最简单的是想到循环,2,4,8…..逐渐增大值,并与入参进行对比,相关代码如下:

1
2
3
4
5
6
7
8
9
public static int getNum1(int n){
for(int i=0;i<= 31;i++){
int b = 1<<i;
if(b > n){
return b;
}
}
return -1;
}

如上方法 1<<i 是把1左移i位,每次左移一位就是乘以2,所以 1<<i 的结果是1乘以2的i次方。

当然我们也可以使用Java自带的Math.pow或者乘法算法方法,不过显然这种方法效率要低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int getNum2(int n){
for(int i=0;i<= 31;i++){
double b = Math.pow(2,i);
if(b > n){
return (int)b;
}
}
return -1;
}
public static int getNum3(int n){
int k = 1;
for(int i=0;i<= 31;i++){
if(k > n){
return k;
}
k *= 2;
}
return -1;
}

或者我们可以想到将入参每次除以2,直到小于1,记录次数i,然后2的i次方即是我们所要求的值。

相关代码如下:

1
2
3
4
5
6
7
8
public static int getNum4(int n){
int i = 0;
while (n > 0) {
n = n >> 1;
i++;
}
return 1<<i;
}

可以看到我们仍使用了移位运算, n = n >> 1 每次将n向右移一位即除以2,当n <= 0 时记录次数 i,并使用 1<<i 算出要求的值。

当然我们也可以使用普通的除法算法,但这种效率要低些,代码如下:

1
2
3
4
5
6
7
8
public static int getNum5(int n){
int i=1;
while (n>1){
n /=2;
i++;
}
return 1<<i;
}

其实上面几种情况原理都是类似的。

还有什么别的方法么?

正文

很巧,在JDK相关源码中也有类似的问题,即获取下一个最小的比入参n大的2的高次幂

在哪儿会用到呢?

当然是HashMap了,HashMap在扩容时,扩容指定的大小就是下一个最小的比入参n大的2的高次幂

下面是具体tableSizeFor方法源码:

1
2
3
4
5
6
7
8
9
10
11
12
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

我们可以在CourrentHashMap、ForkJoinPool中发现类似的处理逻辑,这种处理的优点体现在哪儿呢?

我们把上面的代码在整理下,如下,对于入参n,该方法可以计算出最小的比入参n大的2的高次幂。

1
2
3
4
5
6
7
8
public static int getNum6(int n){
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return n < 0 ? 1 : n + 1;
}

PS:我们忽略源码中的int n = cap - 1; 这一步的作用是对于入参比如8,tableSizeFor方法会返回8,而getNum6会返回16,其实主要看题目怎么出,这儿我们找的是比入参n大的数,不包括n。

我们先来手动计算一下,以32和2000为例。

1
2
3
4
5
6
7
// 32 = 100000 = 0100000
n|=n>>>1;// n=n|(n>>>1) = 0100000|0010000 = 0110000 = 48
n|=n>>>2;// n=n|(n>>>2) = 0110000|0001100 = 0111100 = 60
n|=n>>>4;// n=n|(n>>>4) = 0111100|0000011 = 0111111 = 63
n|=n>>>8;// n=n|(n>>>8) = 0111111|0000000 = 0111111 = 63
n|=n>>>16;// n=n|(n>>>16) = 0111111|0000000 = 0111111 = 63
// n + 1 =64
1
2
3
4
5
6
7
// 2000 = 11111010000 = 11111010000
n|=n>>>1;// n=n|(n>>>1) = 11111010000|01111101000 = 11111111000 = 2040
n|=n>>>2;// n=n|(n>>>2) = 11111111000|00111111110 = 11111111110 = 2046
n|=n>>>4;// n=n|(n>>>4) = 11111111110|00001111111 = 11111111111 = 2047
n|=n>>>8;// n=n|(n>>>8) = 11111111111|00000000111 = 11111111111 = 2047
n|=n>>>16;// n=n|(n>>>16) = 11111111111|00000000000 = 11111111111 = 2047
// n + 1 =2048

计算过程比较简单,只要明白以下两点:

  • n>>>i 是指二进制的n的值向右移i位;

  • i|k指的是i和k进行位或运算,| 是把某两个二进制数中, 只要其中一个的某一位为1,则结果的该位就为1,与&运算相反。

我们来分析一下:

  • 首先,如果是2的整数次方数,其除最高位(指第一个不为0的数)外,其他位必然是0。比如 ${2}^{11}={2048}$,其二进制为 $100000000000$。
  • 则2的整数次方数-1必定最高位为0,其他位必然为1。大致如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    2   -1   =    000000010 -1   =  000000001
    4 -1 = 000000100 -1 = 000000011
    8 -1 = 000001000 -1 = 000000111
    16 -1 = 000010000 -1 = 000001111
    32 -1 = 000100000 -1 = 000011111
    64 -1 = 001000000 -1 = 000111111
    128 -1 = 010000000 -1 = 001111111
    256 -1 = 100000000 -1 = 011111111
    ......
  • 我们对于任意数,如21,二进制为 000010101,当使用移位+位或运算时,最终该值会逐渐增大到 000011111,而这个值加1就是我们要找的值。其实质是右传播最左侧的一位,来找到最大值。

  • 问:为什么右移位要按照1、2、4、8、16这样移动呢?而不是其他数字呢?

    答:这很好理解,我们拿 $128 (010000000)$来举例,比它大的最小的2的高次幂是256,则需要得到255。

    1
    2
    3
    4
    5
    010000000
    011000000 右移1位+位或
    011110000 右移2位+位或
    011111111 右移4位+位或
    ......

    可以看到我们用了一个最小值128,得到255,只需要最左侧的1右移(1、2、4)并进行位或操作。int最大32位,故右移最大16位即可保证最高位的1对右边的0进行全覆盖(位或操作)。

测试

到底高不高效还是取决于测试结果,我们写一个简单的测试方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public static void main(String[] args) {
//生成若干数量的随机数,找到它们的最小的2的高次幂
int [] a = new int[100000000];
Random random = new Random();
for (int i=0;i<a.length;i++){
a[i] = random.nextInt(1073741824);
}

//方法1
long start1 = System.currentTimeMillis();
for (int i=0;i<a.length;i++){
getNum1(a[i]);
}
System.out.println("方法1耗时:"+(System.currentTimeMillis()-start1)+"ms");
//方法2
long start2 = System.currentTimeMillis();
for (int i=0;i<a.length;i++){
getNum2(a[i]);
}
System.out.println("方法2耗时:"+(System.currentTimeMillis()-start2)+"ms");
//方法3
long start3 = System.currentTimeMillis();
for (int i=0;i<a.length;i++){
getNum3(a[i]);
}
System.out.println("方法3耗时:"+(System.currentTimeMillis()-start3)+"ms");
//方法4
long start4 = System.currentTimeMillis();
for (int i=0;i<a.length;i++){
getNum4(a[i]);
}
System.out.println("方法4耗时:"+(System.currentTimeMillis()-start4)+"ms");
//方法5
long start5 = System.currentTimeMillis();
for (int i=0;i<a.length;i++){
getNum5(a[i]);
}
System.out.println("方法5耗时:"+(System.currentTimeMillis()-start5)+"ms");
//方法6
long start6 = System.currentTimeMillis();
for (int i=0;i<a.length;i++){
getNum6(a[i]);
}
System.out.println("方法6耗时:"+(System.currentTimeMillis()-start6)+"ms");
}

某次结果如下:

1
2
3
4
5
6
方法1耗时:1064ms
//由于方法2耗时实在无法接受,便不再展示。调用Math.pow方法,同学们可实际测试下。
方法3耗时:1097ms
方法4耗时:2232ms
方法5耗时:3885ms
方法6耗时:155ms

经过多次测试其结果相差不大。可以看到方法6(也就是JDK里的tableSizeFor方法)确实高效。

结语

该方法在 Hacker’s Delight (高效程序的奥秘)一书 3.2节中有一些介绍,有兴趣的同学也可以去看看。

通过上面的讲解,我们可以看到JDK源码中使用高效算法的艺术,多读源码,对我们也受益匪浅。

今天就先到这里,有时间我们在分析JDK源码中比较有趣的一些代码。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%