Overflow occurs when addition or sum of two int goes beyond limits of int i.e. Integer.MAX_VALUE i.e. 231-1.
Java code from java.lang.Math
Below is the source code from java.lang.Math for addition. It shows the logic used to detect overflow.
|
1 2 3 4 5 6 7 8 |
public static int addExact(int x, int y) { int r = x + y; // HD 2-12 Overflow iff both arguments have the opposite sign of the result if (((x ^ r) & (y ^ r)) < 0) { throw new ArithmeticException("integer overflow"); } return r; } |
Explanation of logic of overflow detection
In binary terms, overflow is when during addition of two binary numbers, leftmost bit produces carry. For ex:
Integer.MAX_VALUE + 1
|
1 2 3 4 |
2147483647 = 1111111111111111111111111111111 + 1 = 0000000000000000000000000000001 --------------------------------------------------- -2147483648 = "1"0000000000000000000000000000000 |
Integer.MIN_VALUE – 1
|
1 2 3 4 |
-2147483648 = 10000000000000000000000000000000 - 1 = 11111111111111111111111111111111 --------------------------------------------------- 2147483647 = "1"01111111111111111111111111111111 |
Here are some facts about overflow. Overflow NEVER happens when both int being added are having opposite signs. If one int is positive & one is negative, it can not cause overflow/underflow.
Overflow can occur ONLY if both int have same sign.
Now lets consider scenario where 2 int causes overflow similar to above shown example. In general their binary representation will be something like below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Example of 2 positive int causing overflow 01XXXXXXXX (First 0 indicates positive int, rest of bits are magnitude) + 01XXXXXXXX (First 0 indicates positive int, rest of bits are magnitude) ----------- 10XXXXXXXX (First bit became 1 due to carry so indicate negative, rest bits are magnitude) Example of 2 negative int causing overflow/underflow 11XXXXXXXX (First 1 indicates negative int, rest of bits are magnitude) + 11XXXXXXXX (First 1 indicates negative int, rest of bits are magnitude) ----------- 00XXXXXXXX (First bit became 0 due to carry so indicate positive, rest bits are magnitude) |
This means, if two positive int cause overflow, sum will be negative. If two negative int causes underflow, sum will be positive.
Now we have to find if sum has opposite sign as that of original integers being added. XOR logical operator’s truth table can help in this scenario. XOR gives 1 if both digits are different.
Steps to verify above facts:
- XOR both arguments with final sum:
- If leftmost sign bit of argument & sum are different then it will result in leftmost sign bit 1 as per XOR truth table.
- Otherwise it will result in leftmost sign bit as 0.
- AND both above results:
- If both above XOR results end up in leftmost sign bit as 1, means both arguments had different sign than sum.
- So doing AND will result with leftmost sign bit as 1 only when both XOR results had leftmost bit 1 i.e. negative result.
- Otherwise leftmost bit will be 0 i.e. positive result.
- Hence, if result is NEGATIVE, then this is overflow case.
Examples are below
Positive integers causing overflow
Positive int 2147483647 + 1 causing overflow with result -2147483648 (negative)
|
1 2 3 4 5 6 7 8 9 10 11 |
1) XOR of final sum with both arguments 2147483647 ^ -2147483648 = 11111111111111111111111111111111 1 ^ -2147483648 = 10000000000000000000000000000001 2) AND of both answers above 11111111111111111111111111111111 & 10000000000000000000000000000001 ------------------------------------- 10000000000000000000000000000001 = -2147483647 (NEGATIVE) |
Negative integers causing overflow
Negative int -2147483648 – 1 causing overflow with result 2147483647 (positive)
|
1 2 3 4 5 6 7 8 9 10 11 |
1) XOR of final sum with both arguments -2147483648 ^ 2147483647 = 11111111111111111111111111111111 -1 ^ 2147483647 = 10000000000000000000000000000000 2) AND of both answers above 11111111111111111111111111111111 & 10000000000000000000000000000000 ------------------------------------- 10000000000000000000000000000000 = -2147483648 (NEGATIVE) |
As you can see, in both cases above after XOR & AND operations, final answer came negative (i.e. first bit as 1). So we can check if final answer is less than 0, then it is an overflow scenario.