Java: why does multiplying large positive number cause negative results?

Question

I’m seeing some strange behavior multiplying integers with Java. I was doing some coding exercises and came upon the following fizz buzz type of exercise. The requirements: Given an integer, write a function that finds the product of every multiple of 3 which is smaller than the given integer, except any multiple of 5. Eg, given 17 we want to return 12*9*6*3 (= 1944). I wrote the following:

public int findProduct(int limit) { 
    int product = 1;
    for(int n = 3; n < limit; n = n + 3) {
        if (n % 5 != 0) {
            product = product * n;
        }
    }
    return product;
}

This works just fine for small numbers. However in testing I found that once you get above 33 somehow the return value is way off. For example if I call the function with a limit of 36, it returns -1.466221696E9. This is where I get confused. I am multiplying positive integers and the result is somehow negative.

However, I discovered that if you declare a double it seems to always return the correct result.

public double findProduct(int limit) { 
    double product = 1;
    for(int n = 3; n < limit; n = n + 3) {
        if (n % 5 != 0) {
            product = product * n;
        }
    }
    return product;
}

My question is: Why is this happening with the integers and what is different about the double type that makes it perform correctly?

Answer 1

Let's examine this by taking an example of Integer.

Integer.MAX_VALUE can be represented as 01111111111111111111111111111111 which is a 32 bit long string(including sign bit). Now if you happen to add 1 to the above string, it results in 10000000000000000000000000000000 which is same as Integer.MIN_VALUE. This is called overflow of Integer.

System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));
// 1111111111111111111111111111111

According to Integer#toBinaryString:

The unsigned integer value is the argument plus 2³² if the argument is negative; otherwise it is equal to the argument. This value is converted to a string of ASCII digits in binary (base 2) with no extra leading 0s.

So that's why you can't see the sign bit but the real value of Integer.MAX_VALUE is 01111111111111111111111111111111. Now take a look at this code:

System.out.println(Integer.toBinaryString(Integer.MAX_VALUE + 1));
// 10000000000000000000000000000000
System.out.println(Integer.toBinaryString(Integer.MIN_VALUE));
// 10000000000000000000000000000000

The output of both the numbers is same. Java doesn't protect against Integer overflow. It is the developer who should take care of this. So what could be the possible solution to this problem? You can use other data types such as long or BigInteger. Here are the max values you might be interested in:

System.out.println(Integer.MAX_VALUE); // 2147483647
System.out.println(Long.MAX_VALUE); // 9223372036854775807
System.out.println(Double.MAX_VALUE); // 1.7976931348623157E308
System.out.println(Float.MAX_VALUE); // 3.4028235E38

Once the Integer reaches MAX_VALUE it will start to overflow and you will end up in negative value.

Answer 2

This is called integer overflow. Essentially, your numbers become too large for the data type that you're storing the solution in. When this happens, the numbers wrap around to negative numbers because of twos-complement. A double is a larger data type but if you go large enough, it too will become negative.

See these articles on two's complement and integer overflow. They'll thoroughly explain it.

Edit: A simplified explanation from the wiki article. I still recommend you read this. Suppose we had a 3-bit architecture (000 through 111). In two's complement, we say that the leading bit determines whether the number is positive/negative. If it's negative, then the following digits add positively to the negative number. Here's a simple counting example:

+---------+--------+
| Decimal | Binary |
+---------+--------+
|       0 |    000 |
|       1 |    001 |
|       2 |    010 |
|       3 |    011 |
|      -4 |    100 | <----- note this isn't negative 0, or +4.
|      -3 |    101 | <----- note this isn't -1, or +5
|      -2 |    110 | <----- note this isn't +6
|      -1 |    111 |<----- note this isn't -3, or +7
|       0 |    000 |
+---------+--------+

And the pattern repeats...

So for a bigger system, the same rule applies (32bit, or 64bit). The numbers will wrap around at 2^(n-1) where n represents how many bits the number has (e.g. for a 3-bit system as shown above, it wraps at 2^(3-1) = 2^2 = 4). Note that using two's complement means, that the range of positive space is halved. For a 3-bit unsigned integer, normally you'd be able to count from 0 to 7, now you can only count between -4 and 3 (still 8 numbers total).

Now try multiplying two positive numbers: +2 * +3 = ?

Normally this would be +6, or 110. But in two's complement, this is actually -2.

Answer 3

If you wanted to completely avoid the integer overflow problem, try using BigInteger:
https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
This allows arbitrary length integers.

(Actually from looking at the source code for BigInteger, it seems there is a maximum size, i.e. the int[] which stores the BigInteger of:

Integer.MAX_VALUE / Integer.SIZE + 1

Much bigger than anyone could reasonably want!)

Answer 4

exceed the range of Double.MAX_VALUE thats why result is coming negative

example:

for four digit binary data is.

00001 here left most bit reserved for sign bit, [0 means +, 1 means -], and rest of 4 bits are used for storing value. so 00001 binary= decimal +1

so for 4 bit we will be able to write maximum 15 decimal value.

Now if I want to write 16 then overflowing the value range.

so if I convert the decimal 16 to binary data, it will be 10000, so sign bit is 1 now. and final result will be negative