在 Java 中,如何找到大于或等于一个整数的最小的 2 的幂(乘方)呢?

像下面这种:

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

这里列举了两个方法:

  1. 利用对数运算;
  2. 利用补码的「移位」和「按位或」操作。

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

一、利用对数运算

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

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

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

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 位):

转换数25-8位

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

转换数32false.png

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

转换数32true.png

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

  • 如果一个数不是 2 的幂,那么它本身减 1 之后,其补码的最高位的位置是不变的。而后续的操作会把最高位及以下的所有低位都变成 1,所以这些低位本身是 1 还是 0 都是不影响最终结果的。例如对于上面的数 25:[0001 1001] - 1 = [0001 1000] , 无论是原值还是减 1 之后的值,经过我们的「变 1」操作之后都会变成:0001 1111即对于任意正的十进制数 x,我们只需要根据其补码的最高位判断其所属区间 2n-1 < x < 2n 即可,在这区间的数经过「变 1」操作之后,都会得到一个相同的结果 2n
  • 如果输入数本身就是 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 的操作:

转换25-32位完整过程.png

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

数274821133.png

进行转换的操作:

转换数274821133完整过程.png

得到的结果是十进制的 229 = 536870912 ,符合我们的要求。


(完)如有问题,欢迎交流~

评论