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

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.