如何计算 2 的幂 N 其中 N 是一个非常大的数

Question

我需要找到 2 的 N 次幂，其中 N 是一个非常大的数（Java BigInteger 类型）

Java BigInteger Class 有 pow 方法，但它只接受整数值作为指数。

于是，我写了一个方法如下：

static BigInteger twoToThePower(BigInteger n)
   {
      BigInteger result = BigInteger.valueOf(1L);

      while (n.compareTo(BigInteger.valueOf((long) Integer.MAX_VALUE)) > 0)
      {
         result = result.shiftLeft(Integer.MAX_VALUE);
         n = n.subtract(BigInteger.valueOf((long) Integer.MAX_VALUE));

      }

      long k = n.longValue();
      result = result.shiftLeft((int) k);

      return result;
   }

我的代码工作正常，我只是分享我的想法，很想知道是否还有其他更好的想法？

谢谢。

Answer 1

通过使用重复平方可以实现您的目标。我在下面发布了示例代码以了解重复平方的逻辑。

static BigInteger pow(BigInteger base, BigInteger exponent) {
    BigInteger result = BigInteger.ONE;
    while (exponent.signum() > 0) {
        if (exponent.testBit(0)) result = result.multiply(base);
        base = base.multiply(base);
        exponent = exponent.shiftRight(1);
    }
    return result;
}

Answer 2

您不能使用 BigInteger 来存储计算结果。来自 javadoc :

BigInteger must support values in the range -2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive) and may support values outside of that range.

这就是 pow 方法采用 int 的原因。在我的机器上，BigInteger.ONE.shiftLeft(Integer.MAX_VALUE) 抛出 java.lang.ArithmeticException（消息是 "BigInteger would overflow supported range"）。

Answer 3

一个有趣的问题。只是为了向可接受的答案添加更多信息，检查 BigInteger 的 openjdk 8 源代码表明这些位存储在数组 final int[] mag; 中。由于数组最多可以包含 Integer.MAX_VALUE 个元素，这立即对 2^{(32 * Integer.MAX_VALUE)} 的 BigInteger 的这个特定实现提出了理论上的限制。因此，即使您的 repeated left-shifting 方法最多也只能超过 int 的大小 32.

那么，您准备好自己实现 BigInteger 了吗？

Answer 4

Emmanuel Lonca 的回答是正确的。但是，根据 Manoj Banik 的想法，我也想分享我的想法。

我的代码以更快的方式执行与 Manoj Banik 的代码相同的操作。这个想法是初始化缓冲区，并将位 1 放入正确的位置。我在 1 个字节上使用左移运算符而不是 shiftLeft 方法。
这是我的代码：

    static BigInteger twoToThePower(BigInteger n){
        BigInteger eight = BigInteger.valueOf(8);
        BigInteger[] devideResult = n.divideAndRemainder(eight);
        BigInteger bufferSize = devideResult[0].add(BigInteger.ONE);
        int  offset = devideResult[1].intValue();
        byte[] buffer = new byte[bufferSize.intValueExact()];
        buffer[0] = (byte)(1 << offset);
        return new BigInteger(1,buffer);
    }

但还是比BigInteger.pow

慢

然后，我发现classBigInteger有个方法叫setBit。它还像 pow 方法一样接受参数类型 int。使用此方法比 BigInteger.pow.
更快代码可以是：

    static BigInteger twoToThePower(BigInteger n){
        return BigInteger.ZERO.setBit(n.intValueExact());
    }

Class BigInteger 也有一个名为 modPow 的方法。但它还需要一个参数。这意味着您应该指定 modulus，并且您的结果应该小于此 modulus。我没有对 modPow 进行性能测试，但我认为它应该比 pow 方法慢。

如何计算 2 的幂 N 其中 N 是一个非常大的数

How to calculate 2 to-the-power N where N is a very large number

java

biginteger

pow