Algorithms – Detect int addition/sum overflow or underflow

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.

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

Integer.MIN_VALUE – 1

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.

 

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)

Negative integers causing overflow

Negative int -2147483648 – 1 causing overflow with result 2147483647 (positive)

 

 

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.



 

Leave a Reply

Your email address will not be published.