How to assign the largest n bit unsigned integer to a BigInteger in Java

Question

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?

Answer 1

I think there is pow method directly in BigInteger. You can use it for your purpose

Answer 2

The quickest way I can think of doing this is by using the constructor for BigInteger that takes a byte[].

BigInteger(byte[] val) constructs the BigInteger Object 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 like val = "111111111111111111111111111111111111111" and then call BigInteger 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.

Answer 3

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:

BigInteger largestNBitInteger = BigInteger.ZERO.setBit(n).subtract(BigInteger.ONE);

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 smallestNPlusOneBitInteger = BigInteger.ZERO.setBit(n);

Answer 4

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:

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

Note that this is analogous in decimal too. The largest 3 digit number is:

10³- 1 = 1000 - 1 = 999

Thus, a subproblem of finding the largest n-bit unsigned number is computing 2ⁿ.

---

On computing powers of 2

Modern digital computers can compute powers of two efficiently, due to the following pattern:

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

That is, 2ⁿ 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 BigInteger for our problem:

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

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

If we were using long instead, then we can write something like this:

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

There is no "set bit n" operation defined for long, so traditionally bit shifting is used instead. In fact, a BigInteger analog of this shifting technique is also possible:

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

See also

• Wikipedia/Binary numeral system
• Bit Twiddling Hacks

---

Additional BigInteger tips

BigInteger does have a pow method to compute non-negative power of any arbitrary number. If you're working in a modular ring, there are also modPow and modInverse.

You can individually setBit, flipBit or just testBit. You can get the overall bitCount, perform bitwise and with another BigInteger, and shiftLeft/shiftRight, etc.

As bonus, you can also compute the gcd or check if the number isProbablePrime.

ALWAYS remember that BigInteger, like String, 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.