BigInteger.bitLength() can return negative result

Dmitry Nadezhin Dmitry.Nadezhin at Sun.COM
Thu Oct 15 17:03:41 UTC 2009


BigInteger is a class implementing arbitrary-precision integers. Of 
course, it is an idealization. Let's look at implementation limits of 
this type.

The bits are stored in "int[] mag" array. This sets the maximum bit 
length 32*(2^31 - 1).

The "BigInteger.magSerializedForm()" converts bits to "byte[]" array. 
Serialization of BigInteger will throw an exception on values with bit 
length larger than 8*(2^31 - 1).

The methods "BigInteger.bitLength()", "BigInteger.bitCount()", 
"BigInteger.getLowestSetBit()" return result as "int".
So they may wrap around when bit length is larger than "2^31 - 1". The 
method "BigInteger.toByteArray()" can fail on such values because it 
uses "bitLength()".

In fact, the output of this program
public static void main(String[] args) {
BigInteger x = BigInteger.ONE.shiftLeft(Integer.MAX_VALUE); // x = 
2^Integer.MAX_VALUE;
System.out.println("bitLength="+x.bitLength());
try {
byte[] bytes = x.toByteArray();
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
is:
bitLength=-2147483648
java.lang.NegativeArraySizeException
at java_math.BigInteger.toByteArray(BigInteger.java:2689)

Shouldn't BigInteger.bitLength()" conform its specification on all 
possible values of BigInteger ?
This can be achieved in different ways:
a) Don't change code but write about the wrap around in the 
specification of "bitLength()" and other methods ;
b) Change the return type of "bitLength()" from "int" to "long";
c) "bitLength()" throws an exception when bit length is larger than 2^31 
- 1;
d) All BigInteger constructors ensure that the bit length is no larger 
than 2^31 - 1;

Which way is better ?





More information about the core-libs-dev mailing list