举例

比如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等等

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