获取大于等于一个整数的最小2次幂算法（HashMap#tableSizeFor）

一、需求

给定一个整数，返回大于等于该整数的最小2次幂（2的乘方）。

例： 输入   输出

         -1         1

          1         1

          3         4

          9         16

          15       16

二、分析

当遇到这个需求的时候，我们可能会很容易想到一个"笨"办法：通过对数函数求解。

假设输入数字为num，那么我们先判断num是不是2的乘方，如果是的话就直接返回了；否则需要计算：首先找到以2为底num的对数，既然num不是2的乘方，那么这个对数就不是整数，我们找到大于这个对数的最近一个整数（也就是强转int，再加1），再来求2的乘方。

在实施这个方法之前，得有个问题需要解决：怎么找到以2为底num的对数？java里面没有提供这样的函数，但是提供了求自然对数的接口。所以我们可以使用我们中学学的换底公式（具体推导过程可以自行百度哈）：

 

我们把公式中的c换成常数e，就能使用java提供给我们的接口了。代码实现如下：

public static int rebuildNum(int num) {
        if (num <= 0) {
            //如果num<=0，直接返回2的0次幂
            return 1;
        } else if ((num & (num - 1)) == 0) {
            //如果num是2的乘方，则直接返回num
            return num;
        } else {
            //找到大于以2为底num的对数最近的整数
            //例：num=7,以2为底7的对数为：2.807...，强转int再加1结果为：3
            int tmp = (int) (Math.log(num) / Math.log(2)) + 1;
            //求2的tmp次幂
            return (int) Math.pow(2, tmp);
        }
}

三、优化

虽然上面我们解决了问题，但是总感觉效率"不高"！在我们程序猿(媛)的眼中，2，总是一个很特殊的数字，其缘归于2进制。我们也知道计算机的任何运算都会以二进制为基础运算，按位操作的效率才是最高的。所以我们要想一下怎么能够优化这个算法？或者换一个解决思路？（关于二进制的详细介绍可以戳这里）

首先我们要明确一些“事实”，在java中，int占4个字节，也就是32位，最高位为符号位，那么能存下的最大的2的乘方就是：2的30次幂，也就是：1<<30：01000000 00000000 00000000 00000000

而2的乘方最大的特点就是，只有一位是1，其它全为0。我们可以根据这个找到思路：先把最高位以下的所有低位全"变"成1，然后再加1，比如：十进制的10，转化为二进制为：

                                                00000000 00000000 00000000 00001010

把最高位以下的所有低位变成1之后：

                                                00000000 00000000 00000000 00001111

然后再加1：

                                                00000000 00000000 00000000 00010000

结果就是十进制的16，达到了我们的要求。

但是这个方法有另外一个问题，比如我们输入的数本身就是2的乘方呢？比如我们输入16，其二进制为：

                                                00000000 00000000 00000000 00010000

把最高位以下的所有低位变成1之后：

                                                00000000 00000000 00000000 00011111

然后再加1：

                                                00000000 00000000 00000000 00100000

我们看到得到的结果是32，这就不是我们的预期：找到大于等于输入数的最小2乘方，也就是如果输入本身就是2的乘方，我们需要返回该输入本身。明显这里得到的结果应该是16才对。可是怎么处理呢？很简单，我们只需要把输入数在处理之前做一个减1操作即可，为什么这样做呢？

原因很简单，如果一个数不是2的乘方，那么它本身减1之后，最高位的位置是不会变的，而我们后续会把最高位后的所有低位都变成1，所以这些低位本身是1或者是0都是不重要的。比如(这里只写8位)：00001101-1=00001100，不论是原值还是减一之后的值，经过我们的“变1”操作之后都是：00001111.

而如果输入数本身就是2的乘方，那么我们减1之后，最高位的位置会往右移动一位（剩余都是1），我们把它+1之后，又变成了它“原来的模样”，符合我们的要求。

可是变成1的操作该这么实施呢？还是很简单，只需要通过移位和按位或操作即可。我们结合具体例子讲解一下：

输入数：十进制的10，二进制为：00000000 00000000 00000000 00001010

step1：减1操作，得到：00000000 00000000 00000000 00001001（虽然我们说了，减1主要针对本身就是2的乘方的数，可是这步操作还是要做哈，少写个if-else判断噻）

step2：将上一步的输出和其本身无符号右移1位的结果做或操作：

             00000000 00000000 00000000 00001001（step1得到的结果）

                                     按位或

             00000000 00000000 00000000 00000100（step1得到的结果无符号右移1位的结果）

    得到结果：

             00000000 00000000 00000000 00001101

是不是发现已经把最高位的紧邻低位变成了1？这时我们已经能确保有2个1了(本例中)。

step3：将上一步的输出和其本身无符号右移2位的结果做或操作：

             00000000 00000000 00000000 00001101（step2得到的结果）

                                    按位或

             00000000 00000000 00000000 00000011（step2得到的二级果无符号右移1位的结果）

     得到结果：

             00000000 00000000 00000000 00001111

同理，这个时候我们就能够确保有4个1了(本例中)，由于int一共占32位，所以我们还需要做类似的操作3次，也就是接下来的操作（注：在本例中step4到step6的操作对结果无影响，因为原始输入的最高位并没有超过第4位。同理如果最高位不超过第8位，step5到step6对结果也不会有影响）：

step4：将step3的输出和其本身无符号右移4位的结果做或操作）

step5：将step4的输出和其本身无符号右移8位的结果做或操作

step6：将step5的输出和其本身无符号右移16位的结果做或操作

step7：最后我们只需要判断一下，如果结果是负数，那么我们返回1就可以了，如果结果大于了能够存储的最大2的乘方，返回该最大值就可以了，否则就返回+1的结果。可是为什么会有这些"异常情况"呢？因为我们上面的所有右移操作都是无符号右移，二进制数在系统中的存储是以补码方式存储的，最高位表示符号位，所以我们通过无符号右移再做或操作得到的结果可能会是任何可能的值（int能存的下的）。

接下来我们用代码实现以上逻辑（其实java中的HashMap也是采取这个算法计算的，感兴趣的可以去看一下）：

public static int rebuildNum(int num){
    int max = 1 << 30;
    int n = num - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return n < 0 ? 1 : (n >= max ? max : n + 1);
}

 

 

 

 

分享到：