JDK-6910473 : java.math.BigInteger.bitLength() may return negative "int" on large numbers
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.math
  • Affected Version: 6u16
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: solaris_nevada
  • CPU: x86
  • Submitted: 2009-12-15
  • Updated: 2017-05-16
  • Resolved: 2013-10-31
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 8
8 b115Fixed
Related Reports
Duplicate :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Description
FULL PRODUCT VERSION :
java version "1.6.0_16"
Java(TM) SE Runtime Environment (build 1.6.0_16-b01)
Java HotSpot(TM) Server VM (build 14.2-b01, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
SunOS opteron 5.11 snv_125 i86pc i386 i86pc


A DESCRIPTION OF THE PROBLEM :
It is possible to create BigInteger so large that its bit length larger than Integer.MAX_VALUE. In these case bitLength() method returns negative "int" value and toByteArray() method crashes.

IMHO, the range of possible BigInteger values should be limited either to a range
[-2^Integer.MAX_VALUE,2^Integer.MAX_VALUE-1] with bit length <= Integer.MAX_VALUE
or to a symmetrical range
[-2^Integer.MAX_VALUE+1,2^Integer.MAX_VALUE-1].

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1) Save "Source code for an executable test case" as TestLargeBigInteger.java
2) javac TestLargeBigInteger.java
3) java TestLargeBigInteger

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
I expect ArithmeticExceptionon when the result of shiftLeft() method is out of suggested BigInteger range.
--------------------
Exception in thread "main" java.lang.ArithmeticException: BigInteger overflow
        at java_math.BigInteger.<init>(BigInteger.java:949)
        at java_math.BigInteger.shiftLeft(BigInteger.java:2129)
        at TestLargeBigInteger.main(TestLargeBigInteger.java:6)

ACTUAL -
The bitLength() method returns negative result and toByteArray method throws an exception.
-------------------------
bitLength=-2147483648
java.lang.NegativeArraySizeException
	at java.math.BigInteger.toByteArray(BigInteger.java:2667)
	at TestLargeBigInteger.main(TestLargeBigInteger.java:9)


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.math.BigInteger;

public class TestLargeBigInteger {
    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);
        }
    }
}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
I am preparing a fix and a test for this bug:

http://kenai.com/projects/rigorousnum/sources/java_math/content/trunk/java_math/src/java_math/BigInteger.java?rev=17
http://kenai.com/projects/rigorousnum/sources/java_math/content/trunk/BigIntegerTests/src/HugeValues.java?rev=17
http://kenai.com/projects/rigorousnum/sources/java_math/content/trunk/BigIntegerTests/src/ExtremeShiftingTests.java?rev=17

However I'm going to test more before I submit a WebRev.

Comments
core-libs-dev comment from Joe: http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-July/018644.html
31-07-2013

As suggested by Dmitry in the issue description, one approach would be to limit the range of BigIntegers supported. Another possibility would be to throw an ArithmeticException when the overflow is encountered and to update the specification accordingly. There is some precedent for this in the {byte,short,int,long}ValueExact() methods which throw this exception when the BigInteger is out of the range of the destination primitive data type. The specifications of at least bitLength() and toByteArray() would be affected and it would need to be evaluated whether other methods which invoke bitLength() might encounter the problem as well.
13-06-2013

EVALUATION Yes, it is possible to create partially overflowed BigInteger values. Portions of this are addressed in JDK 7 with the fix for 6371401 java.math.BigInteger.shift(Integer.MIN_VALUE) throws StackOverflowError.
15-12-2009