前言

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

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

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

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

分析

对于这种题目，我们如何处理呢？

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

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< 是把1左移i位，每次左移一位就是乘以2，所以1<的结果是1乘以2的i次方。

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

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次方即是我们所要求的值。

相关代码如下：

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<算出要求的值。

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

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方法源码：

/**
 * 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的高次幂。

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为例。

// 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

// 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。大致如下：

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进行全覆盖（位或操作）。

测试

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

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耗时:1064ms
//由于方法2耗时实在无法接受，便不再展示。调用Math.pow方法，同学们可实际测试下。
方法3耗时:1097ms
方法4耗时:2232ms
方法5耗时:3885ms
方法6耗时:155ms

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

结语

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

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

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

SakuraTears的博客

JDK里那些有趣的代码（2）

前言

分析

正文

测试

结语