如何将最大的n位无符号整数分配给Java中的BigInteger

Question

我有一个场景,我正在使用大整数(例如160位),并试图创建最大可能的无符号整数,可以n在运行时用位数表示.在程序开始执行并从配置文件中读取值之前,不知道n的确切值.例如,n可能是160,或128,或192,等等......

最初我的想法是这样的:

BigInteger.valueOf((long)Math.pow(2, n));

但后来我才意识到,转换为long会发生这种情况有点失败的目的,因为长时间内没有足够的位来存储结果.有什么建议？

Answer 1

在最大的n位无符号数上

我们先来看看这个数字是什么,数学上.

在无符号二进制表示中,最大的n位数将所有位设置为1.让我们看一些示例:

1₍₂₎= 1 = 2 ¹ - 1
11₍₂₎= 3 = 2 ² - 1
111₍₂₎= 7 = 2 ³ - 1
:
1………1₍₂₎= 2 ⁿ -1
   ⁿ

请注意,这也类似于十进制.最大的3位数字是:

10³- 1 = 1000 - 1 = 999

因此,找到最大n位无符号数的子问题是计算2 ⁿ.

关于2的计算能力

由于以下模式,现代数字计算机可以有效地计算两个幂:

2 ⁰ = 1₍₂₎
2 ¹ = 10₍₂₎
2 ² = 100₍₂₎
2 ³ = 1000₍₂₎
:
2 ⁿ= 10………0₍₂₎
       ⁿ

也就是说,2 ⁿ只是一个数字,其位n设置为1,其他所有设置为0(请记住,这些位编号为零基索引).

解

综上所述,我们可以使用这个简单的解决方案来解决BigInteger我们的问题:

final int N = 5;
BigInteger twoToN   = BigInteger.ZERO.setBit(N);
BigInteger maxNbits = twoToN.subtract(BigInteger.ONE);

System.out.println(maxNbits); // 31

如果我们使用long,那么我们可以这样写:

// for 64-bit signed long version, N < 64
System.out.println(
    (1L << N) - 1
); // 31

没有定义"设置位n "操作long,因此传统上使用位移.事实上,BigInteger这种移位技术的类比也是可能的:

System.out.println(
    BigInteger.ONE.shiftLeft(N).subtract(BigInteger.ONE)
); // 31

也可以看看

• 维基百科/二进制数字系统
• 比特扭曲黑客

其他BigInteger提示

BigInteger确实有一种pow计算任意数字的非负功率的方法.如果你在一个模块化环工作,也有modPow和modInverse.

你可以单独setBit,flipBit或只testBit.你可以获得整体bitCount,and与另一个BigInteger和shiftLeft/ shiftRight等等按位执行.

作为奖励,您还可以计算gcd或检查数字isProbablePrime.

总是要记住BigInteger,就像String,是不可改变的.您无法在实例上调用方法,并期望修改该实例.相反,始终将方法返回的结果分配给变量.