BigInteger.bitLength() can return negative result (original) (raw)
Dmitry Nadezhin Dmitry.Nadezhin at Sun.COM
Thu Oct 15 17:03:41 UTC 2009
- Previous message: C system() equivalent method.
- Next message: BigInteger.bitLength() can return negative result
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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 ?
- Previous message: C system() equivalent method.
- Next message: BigInteger.bitLength() can return negative result
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]