如何找到大于或等于一个整数的最小的 2 的幂？

在 Java 中，如何找到大于或等于一个整数的最小的 2 的幂（乘方）呢？例如：

输入         输出
 -1           1
 7            8
 16           16
 25           32
 274821133    536870912

这里列举了两个方法：

利用对数运算；
利用补码的「移位」和「按位或」操作。

显然方法 2 的效率会更高一些。

一、利用对数运算

对数，即对求幂的逆运算，我们可以利用对数运算来找到大于或等于一个整数的最小的 2 的幂。对于整数 x，设 y 表示大于或等于数 x 的最小的 2 的幂，则：

如果数 x 是 2 的幂，则直接返回 y = x 即可。
否则需要计算：因为 y = 2ⁿ ，所以我们只需要找到一个最小的满足要求的指数 n，然后就可以求得满足要求的 2 的幂了。首先求以 2 为底 x 的对数，既然 x 不是 2 的幂，那么这个对数就不会是整数，就需要找到大于这个对数的最近一个整数（即强转 int，然后加 1）即为 n，然后求 2 的幂即可。

另外有一个问题就是，Java 中没有求底数为 2 的对数函数，但是提供了求底数为自然常数 e 的对数函数 Math.log()：

此时可以利用对数的换底公式：

将公式中的 c 换成自然常数 e，就可以使用 Java 中提供的函数来计算了，代码实现如下：

 public static int powerTwo(int x){
     if (x <= 0){
         // 如果 x <= 0，直接返回 2 的 0 次幂
         return 1;
     } else if ((x & (x - 1)) == 0) {
         // 通过「按位与」操作来判断，如果 x 是 2 的幂，则直接返回 x
         return x;
     } else {
         // 计算大于以 2 为底 x 的对数的最小整数
         // 例如 x = 25，以 2 为底 25 的对数为 4.643...，强转 int 再加 1 的结果为 5
         int n = (int)(Math.log(x) / Math.log(2)) + 1;
         return (int)Math.pow(2, n);
     }
 }

二、利用补码的「移位」和「按位或」操作

在 Java 的 HashMap 源码中，有一段代码：

/**
 * 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;
}

就是利用补码的「移位」和「按位或」操作，来找到大于或等于整数 cap (capacity) 的最小的 2 的幂。这种方式显然效率更高。

1.操作原理

首先，对于任意一个整数，若它为 2 的幂，则会有一个特点：它的二进制数（补码）只有一位最高位是 1，其它位全是 0 。

根据这个特点可以找到思路：对于当前数的补码，先把最高位及以下的所有低位「变」成 1，然后再加 1 。例如，找到大于或等于 25 的最小的 2 的幂（这里只写 8 位）：

得到的结果是十进制的 32，即我们要求的结果。但是这个计算方法有一个问题：若输入的数本身就是 2 的幂，则会得到一个大于该数的最小的 2 的幂，而不是该输入数本身，不符合我们的要求。例如对于数 32（这里只写 8 位）：

得到的结果是十进制的 64，不是我们所预期的 32。这里的解决方法是：把输入数在处理之前做一个减 1 操作。即：

得到的结果是十进制的 32，符合我们的要求。这样做的原因是：

如果一个数不是 2 的幂，那么它本身减 1 之后，其补码的最高位的位置是不变的。而后续的操作会把最高位及以下的所有低位都变成 1，所以这些低位本身是 1 还是 0 都是不影响最终结果的。例如对于上面的数 25：[0001 1001] - 1 = [0001 1000] ，无论是原值还是减 1 之后的值，经过我们的「变 1」操作之后都会变成：0001 1111 。即对于任意正的十进制数 x，我们只需要根据其补码的最高位判断其所属区间 2^n-1 < x < 2ⁿ 即可，在这区间的数经过「变 1」操作之后，都会得到一个相同的结果 2ⁿ 。
如果输入数本身就是 2 的幂，根据其特点，在进行减 1 之后，其补码的最高位的位置会向低位移动一位（其余低位均为 1），经过「变1」操作后，最后再加一，又变成了该数本身，符合我们的要求。

2.对于补码的「变 1」操作

那么对于补码的「变 1」操作该如何实施呢？这里只需要通过「移位」和「按位或」操作即可。由于在 Java 中，int 占 4 个字节，即 32 位，最高位为符号位，所以我们操作的位数最高应到 32 位：

这里的 |= 运算符表示「按位或赋值」，例如 a |= b 表示 a = a | b 。同理，这里的 n |= n >>> 1 则表示 n = n | (n >>> 1) 。（符号 >>> 为「无符号右移」操作符）

Step 1： 对给定的输入数减 1 赋值给 n；（主要针对本身就是 2 的幂的数）
Step 2： n |= n >>> 1，对于 Step 1 的结果数 n 的补码，使得与最高位（含）紧邻的 2 位低位为 1；
Step 3： n |= n >>> 2，对于 Step 2 的结果数 n 的补码，使得与最高位（含）紧邻的 4 位低位为 1；
Step 4： n |= n >>> 4，对于 Step 3 的结果数 n 的补码，使得与最高位（含）紧邻的 8 位低位为 1；（PS： 若 n 的最高位没有超过 8 位，则只需将所有低位变成 1 即可，此时后续「移位」和「按位或」的操作不会影响这一步的结果。对于其它高位，依次类推）
Step 5： n |= n >>> 8，对于 Step 4 的结果数 n 的补码，使得与最高位（含）紧邻的 16 位低位为 1；
Step 6： n |= n >>> 16，对于 Step 5 的结果数 n 的补码，使得与最高位（含）紧邻的 32 位低位为 1；
Step 7： 进行判断，如果结果为负数，则返回 1；如果结果大于了能够存储的最大的 2 的幂，则返回该最大值；否则返回加 1 的结果。

例如，对于十进制数 x = 25 的操作：

得到的结果是十进制的 32，符合我们的要求。再例如，对于十进制数 x = 274821133 ：

进行转换的操作：

得到的结果是十进制的 2²⁹ = 536870912 ，符合我们的要求。

（完）如有问题，欢迎交流~