Multiplication of two ints overflows to result in 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);
}
}
Output signal
-727379968
1000000000000
Why is the result -727379968
for (i*i)
? Ideally, this should be 1,000,000,000,000.
I know the Integer range is -2147483648 to 2147483647 so obviously 1000000000000 is not in the given range.
Why the result -727379968
?
source to share
Java (like most computer architectures these days) uses something called two's complement , which uses the most significant bit of an integer to indicate that the number is negative. If you multiply two large numbers, you end up with a number that is so large that it sets the most significant bit, and the result ends in negative.
source to share
You might want to check for integer overflow as a general concept. Overflow and overflow are handled differently depending on the language. Below is an article about Integer Overflow and Overflow in Java .
As for the reason why this is the case in the Java language, as always, it is a tradeoff between simplicity in design and performance of the language. But in Java puzzlers (puzzle 3), the authors criticize the fact that overflow is silent in Java:
The lesson for language designers is that it may be wise to reduce the likelihood of silent overflow . This can be done by providing support for arithmetic that does not overflow silently. Programs can throw an exception instead of an overflow, like Ada, or they can switch automatically as needed to increase the internal representation of overflow, like Lisp. Both of these approaches can have performance penalties associated with them. Another way to reduce the likelihood of silent overflow is to support target input, but this adds significant complexity to the type system.
source to share
Let's take a look at the binary:
1,000,000 - 1111 0100 0010 0100 0000
.
1,000,000,000,0001110 1000 1101 0100 1010 0101 0001 0000 0000 0000
However, the first two sections of 4 bits will not fit in int
(as it int
is 32 bits wide in Java) and so they are discarded, leaving only 1101 0100 1010 0101 0001 0000 0000 0000
that is -727379968
.
In other words, the result overflows for int
and you get what's left.
source to share
Some of the other answers correctly explain why this is happening (i.e. signed the double logic of two compliments).
The actual solution to the problem and getting the right answer in Java when using really large 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));
}
}
source to share