Multiplication of two ints overflowing to result in a negative number

Consider this snippet from the Java language specification.

class Test {
    public static void main(String[] args) {
        int i = 1000000;
        System.out.println(i * i);
        long l = i;
        System.out.println(l * l);
    }
}

The output is

-727379968
1000000000000

Why is the result -727379968 for (i*i)? Ideally it should be 1000000000000.

I know the range of Integer is from –2147483648 to 2147483647. so obviously 1000000000000 is not in the given range.

Why does the result become -727379968?

Solution 1:

Java (like most computer architectures these days) uses something called two's complement arithmetic, which uses the most significant bit of an integer to signify that a number is negative. If you multiply two big numbers, you end up with a number that's so big it sets that highest bit, and the result ends up negative.

Solution 2:

You might want to check Integer overflow as a general concept. Overflow and underflow are handled differently depending on the language, too. Here is an article on Integer overflow and underflow in Java.

As for the reason why this is so in the Java language, as always, it's a tradeoff between simplicity in the language design and performance. But in Java puzzlers (puzzle 3), the authors criticize the fact that overflows are silent in Java:

The lesson for language designers is that it may be worth reducing the likelihood of silent overflow. This could be done by providing support for arithmatic that does not overflow silently. Programs could throw an exception instead of overflowing, as does Ada, or they could switch to a larger internal representation automatically as required to avoid overflow, as does Lisp. Both of these approaches may have performance penalties associated with them. Another way to reduce the likelyhood of silent overflow is to support target typing, but this adds significant complexity to the type system.

Solution 3:

Lets look at the binary:

1000000 is 1111 0100 0010 0100 0000.
1000000000000 is 1110 1000 1101 0100 1010 0101 0001 0000 0000 0000

However, the first two sections of 4 bits won't fit in an int (since int is 32-bits wide in Java,) and so they are dropped, leaving only 1101 0100 1010 0101 0001 0000 0000 0000, which is -727379968.

In other words, the result overflows for int, and you get what's left.

Solution 4:

Some of the other answers explain correctly why this is happening (ie. signed two's compliment binary logic).

The actual solution to the problem and how to get the correct answer in Java when using really big numbers is to use the BigInteger class, which also works for long values.

package com.craigsdickson.scratchpad;

import java.math.BigInteger;

public class BigIntegerExample {

    public static void main(String[] args) {

        int bigInt = Integer.MAX_VALUE;
        // prints incorrect answer
        System.out.println(bigInt * bigInt);

        BigInteger bi = BigInteger.valueOf(bigInt);
        // prints correct answer
        System.out.println(bi.multiply(bi));

        long bigLong = Long.MAX_VALUE;
        // prints incorrect answer
        System.out.println(bigLong * bigLong);

        BigInteger bl = BigInteger.valueOf(bigLong);
        // prints correct answer
        System.out.println(bl.multiply(bl));

    }

}