如何计算比给定数字大的2的幂数

举例

比如3，计算后得出4，比如6，计算后得出8，

这种根据人类最直观的想法，当然一下能看出来，因为我们会去估计大于这个数字的2^n方是多少，但是数字大了就不是人类该做的事情了

如果根据最简单的思维，从2的0次方开始，增加n值，一个个循环试过去，也可以找到这个值，但是效率显然很低，我从源码里找到了两种高效的计算方式：

第一种计算方法

   int tableSizeFor(int source) {
        int maxCapacity = 1 << 30;
        int n = source- 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= maxCapacity ) ? maxCapacity : n + 1;
    }

接下来分析一下这个过程：
假设所求数字source = 20,那么n = 19

n=19
0000 0000 0000 0000 0000 0000 0001 0011
n>>>1
0000 0000 0000 0000 0000 0000 0000 1001
n |= n >>> 1
0000 0000 0000 0000 0000 0000 0001 1011
n>>>2
0000 0000 0000 0000 0000 0000 0000 0110
n |= n >>> 2
0000 0000 0000 0000 0000 0000 0001 1111
n>>>4
0000 0000 0000 0000 0000 0000 0000 0001
n |= n >>> 4
0000 0000 0000 0000 0000 0000 0001 1111
n>>>8
0000 0000 0000 0000 0000 0000 0000 0000
n |= n >>> 8
0000 0000 0000 0000 0000 0000 0001 1111
n>>>16
0000 0000 0000 0000 0000 0000 0000 0000
n |= n >>> 16
0000 0000 0000 0000 0000 0000 0001 1111
(n < 0) ? 1 : (n >= maxCapacity ) ? maxCapacity : n + 1
0000 0000 0000 0000 0000 0000 0010 0000

最后算出的结果就是32，过程很清晰了，那这是一个什么原理呢，其实就是通过位移31次（1+2+4+8+16）以及或运算，把当前最高位下面的二进制都填满1，这样再加1以后就能得到比原先高一位的数字，这个算法不可谓不高明。不知道有没有同学能认出来这个算法是出自于哪一段源码的呢？

第二种计算方法

int tableSizeFor(int source) {
        int n = 1;
        if (source >>> 16 == 0) {
            n += 16;
            source <<= 16;
        }
        if (source >>> 24 == 0) {
            n += 8;
            source <<= 8;
        }
        if (source >>> 28 == 0) {
            n += 4;
            source <<= 4;
        }
        if (source >>> 30 == 0) {
            n += 2;
            source <<= 2;
        }
        n -= source >>> 31;
        return 1<<(32-n);
}

过程分析：
假设source = 20

source 
0000 0000 0000 0000 0000 0000 0001 0100

右移16位 等于0 --> n+=16=17
0000 0000 0000 0000 0000 0000 0000 0000

左移16位 source当前值
0000 0000 0001 0100 0000 0000 0000 0000

右移24位 等于0 --> n+=8=25
0000 0000 0000 0000 0000 0000 0000 0000

左移8位 source当前值
0001 0100 0000 0000 0000 0000 0000 0000

右移28位 不等于0 --> n和source都不变
0000 0000 0000 0000 0000 0000 0000 0001

右移30位 等于0 --> n+=2=27
0000 0000 0000 0000 0000 0000 0000 0000

左移2位 source当前值
0101 0000 0000 0000 0000 0000 0000 0000

source右移31位,等于0
0101 0000 0000 0000 0000 0000 0000 0000

n -= source >>> 31

最后得出n=27，1<<(32-n)=32，这个算法比较繁冗一点，理解起来也稍微困难些，这个算法的目的在于先求出当前数字的左边高位有多少个0，然后用32减去这个0的数量就是所需要的幂了。
这当中求0的数量的过程是个重点，也是通过位移来实现，先向右位移16次，如果等于0了，那说明前面16个高位都是0，n可以加16，如果不等于0，可以继续往下走，最后总归能让你等于0，这样计算累加下去就可以求出前面0的数量。
上面那段源码我没改方法名，可能有人能猜出代码的出处，那这段代码谁能猜到出自哪段源码呢？

源码出处：

• 第一段代码是HashMap里求threshold的过程，方法名就叫tableSizeFor
• 第二段代码是出自Integer类的numberOfLeadingZeros方法，目的就是求出当前数字的左边高位有多少个0。这个方法调用的地方很多，ForkJoinPool，BigInteger，ConcurrentHashMap等等

单从求高一阶幂数这点来说，第一种算法更精妙一点，第二种略显笨拙，但是第二种算法也很好，用处也多。不管怎么说，位移始终是最贴近计算机的操作，是最快速的方法。