如何在Java中将最大的n位无符号整数分配给BigInteger
我有一个场景，我正在处理大整数（例如 160 位），并尝试创建可以在运行时用 n 位数字表示的最大可能无符号整数。在程序开始执行并从配置文件中读取值之前，n 的确切值是未知的。例如，n 可能是 160、或 128、或 192，等等...
最初我的想法是这样的：
BigInteger.valueOf((long)Math.pow(2, n));
但后来我意识到，转换为 long 会发生某种失败考虑到 long 首先没有足够的位来存储结果。有什么建议吗？
I have a scenario where I'm working with large integers (e.g. 160 bit), and am trying to create the biggest possible unsigned integer that can be represented with an n bit number at run time. The exact value of n isn't known until the program has begun executing and read the value from a configuration file. So for example, n might be 160, or 128, or 192, etcetera...
Initially what I was thinking was something like:
BigInteger.valueOf((long)Math.pow(2, n));
but then I realized, the conversion to long that takes place sort of defeats the purpose, given that long is not comprised of enough bits in the first place to store the result. Any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
关于最大的n位无符号数
我们首先从数学上看一下这个数是什么。
在无符号二进制表示中，最大的 n 位数字会将所有位设置为 1。让我们看一些示例：
请注意，这在十进制中也是类似的。最大的三位数是：
因此，找到最大n位无符号的子问题number 正在计算 2n。
关于 2 的计算能力
由于以下模式，现代数字计算机可以有效地计算 2 的幂：
也就是说，2n 只是一个设置了位 n 的数字为 1，其他所有设置为 0（请记住，位是使用从零开始的索引进行编号的）。
解决方案
将以上内容放在一起，我们使用 < 得到这个简单的解决方案code>BigInteger 对于我们的问题：
如果我们使用
long来代替，那么我们可以这样写：没有“设置位n”操作定义为
long，因此传统上使用位移位来代替。事实上，这种移位技术的BigInteger模拟也是可能的：另请参阅
其他
BigInteger提示BigInteger确实有一个pow方法来计算任意数字的非负幂。如果您在模块化环中工作，还有modPow和modInverse。您可以单独
setBit，flipBit或只是testBit。您可以获得总体bitCount，按位执行和与另一个BigInteger，以及shiftLeft/shiftRight等作为奖励，您还可以计算
gcd或检查数字是否isProbablePrime。始终记住，
BigInteger与String一样，是不可变的。您不能在实例上调用方法并期望该实例被修改。相反，始终将方法返回的结果分配给您的变量。On the largest n-bit unsigned number
Let's first take a look at what this number is, mathematically.
In an unsigned binary representation, the largest n-bit number would have all bits set to 1. Let's take a look at some examples:
Note that this is analogous in decimal too. The largest 3 digit number is:
Thus, a subproblem of finding the largest n-bit unsigned number is computing 2n.
On computing powers of 2
Modern digital computers can compute powers of two efficiently, due to the following pattern:
That is, 2n is simply a number having its bit n set to 1, and everything else set to 0 (remember that bits are numbered with zero-based indexing).
Solution
Putting the above together, we get this simple solution using
BigIntegerfor our problem:If we were using
longinstead, then we can write something like this:There is no "set bit n" operation defined for
long, so traditionally bit shifting is used instead. In fact, aBigIntegeranalog of this shifting technique is also possible:See also
Additional
BigIntegertipsBigIntegerdoes have apowmethod to compute non-negative power of any arbitrary number. If you're working in a modular ring, there are alsomodPowandmodInverse.You can individually
setBit,flipBitor justtestBit. You can get the overallbitCount, perform bitwiseandwith anotherBigInteger, andshiftLeft/shiftRight, etc.As bonus, you can also compute the
gcdor check if the numberisProbablePrime.ALWAYS remember that
BigInteger, likeString, is immutable. You can't invoke a method on an instance, and expect that instance to be modified. Instead, always assign the result returned by the method to your variables.只是为了澄清您想要最大 n 位数字（即，将所有 n 位设置）。如果是这样，以下内容将为您做到这一点：
这在数学上相当于 2^n - 1。您的问题是如何执行 2^n，它实际上是最小的 n+1 位数字。你当然可以这样做：
Just to clarify you want the largest n bit number (ie, the one will all n-bits set). If so, the following will do that for you:
Which is mathematically equivalent to 2^n - 1. Your question has how you do 2^n which is actually the smallest n+1 bit number. You can of course do that with:
我认为BigInteger中直接有pow方法。您可以将其用于您的目的
I think there is pow method directly in BigInteger. You can use it for your purpose
我能想到的最快方法是使用采用
byte[]的BigInteger构造函数。BigInteger(byte[] val)从字节数组构造BigInteger对象。然而，您正在处理位，因此为表示 2^40 - 1 的 39 位整数创建一个可能由 {127, 255, 255, 255, 255} 组成的 byte[] 可能有点乏味。您还可以使用构造函数
BigInteger(String val, int radix)- 如果您不介意解析字符串对性能造成影响，那么您的代码中发生的情况可能会更明显。然后，您可以生成一个类似val = "111111111111111111111111111111111111111"的字符串，然后调用BigInteger myInt = new BigInteger(val, 2);- 生成相同的 39 位整数。第一个选项需要考虑如何表示您的号码。该特定构造函数需要数字的二进制补码、大端表示。第二个可能会稍微慢一些，但更清晰。
编辑：更正数字。我以为你的意思是代表2^n，并且没有正确读取n位可以存储的最大值。
The quickest way I can think of doing this is by using the constructor for
BigIntegerthat takes abyte[].BigInteger(byte[] val)constructs theBigIntegerObject from an array of bytes. You are, however, dealing with bits, and so creating a byte[] that might consist of {127, 255, 255, 255, 255} for a 39 bit integer representing 2^40 - 1 might be a little tedious.You could also use the constructor
BigInteger(String val, int radix)- which might be readily more apparently what's going on in your code if you don't mind a performance hit for parsing a String. Then you could generate a string likeval = "111111111111111111111111111111111111111"and then callBigInteger myInt = new BigInteger(val, 2);- resulting in the same 39 bit integer.The first option will require some thinking about how to represent your number. That particular constructor expects a two's-compliment, big-endian representation of the number. The second will likely be marginally slower, but much clearer.
EDIT: Corrected numbers. I thought you meant represent 2^n, and didn't correctly read the largest value n bits could store.