Today, I was reading an article for overflow and cannot stop myself from sharing the gist of it.

Let us discuss this solution of binary search tree.

public int binarySearchTree(int a[],int item) { int start=0; int end=a.length-1; while(start<=end) { int mid=(start+end)/2; if(a[mid]==item) return mid; else if(a[mid]<item) start=mid+1; else end=mid-1; } return -1; }

if we carefully check these lines of code, we will realize that the line mid=(start+end)/2 may result in overflow, what if start+end > Integer.MAX_VALUE then mid will have a -ve value. To overcome this sort of potential programming bug * (this bug is still existing in Java’s Arrays Binary search and it has been earlier reported by Joshua Bloch) *, it will be better to write this line of code as this,

1) mid= start + (end-start)/2;

or

2) mid = (start+high) >>>1; //since in java “>>>” is unsigned right shift operator.

Now let us try to write a utility class to check whether different arithmetic operation is overflow safe or not.

For this let us start to discuss which all arithmetic operation can result in overflow, here I will like to point out that any logical operation like &, | and ^ cannot result in overflow thats why we are only discussing arithmetic operation.

1) Addition: a+ b can result in overflow as we have seen in above discussion. So, we need to have a utility method for this.

2) Subtraction: same like for addition it can also result in overflow.

3) Multiplication: a*b, can easily result in overflow.

4) Division: consider this case Integer.MIN_VALUE/-1, this will result in overflow.

5) Negation: – (Integer.MIN_VALUE) can result in overflow again.

Here is the Utility class has methods to check the safety for each of the above discussed arithemetic operations:-

package org.aakash.pratice; public class OverflowCheckUtility { public static boolean isSafeToSubtract(int i,int j) { if(!isSafeToNegate(j)) return (i&Integer.MIN_VALUE)<0; return isSafeToAdd(i, -j); } public static boolean isSafeToNegate(int i) { return i!=Integer.MIN_VALUE; } public static boolean isSafeToAdd(int i,int j) { int k=i+j; if(((i^k)&(j^k))<0) return false; return true; } public static boolean isSafeToDivide(int i,int j) { if(i<=Integer.MAX_VALUE&j==-1) return false; return true; } public static boolean isSafeToMultiply(int i,int j) { int k=i*j; boolean expectedSign=((i&Integer.MIN_VALUE)^(j&Integer.MIN_VALUE))>=0?true:false; boolean actualsign=(k&Integer.MIN_VALUE)>=0?true:false; return expectedSign==actualsign; } /** Testing utility class for different boundry values * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int count=0; int n=Integer.MIN_VALUE; // int n=-1; while(n!=0) { n=(n-1)&n; count++; } System.out.println(count); System.out.println(Integer.MAX_VALUE*2); System.out.println(Integer.MAX_VALUE*-2); System.out.println(Integer.MIN_VALUE*2); System.out.println(Integer.MIN_VALUE*-1); System.out.println("::checking for multiply"); int i=-1; System.out.println(isSafeToMultiply(i, Integer.MIN_VALUE)); System.out.println(isSafeToMultiply(i, Integer.MAX_VALUE)); System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE/3)); System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE/2)); System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE)); System.out.println(isSafeToMultiply(-2, Integer.MIN_VALUE/2)); System.out.println("checking subtraction"); System.out.println(isSafeToSubtract(-1, Integer.MAX_VALUE)); System.out.println(isSafeToSubtract(-2, Integer.MAX_VALUE)); System.out.println(isSafeToSubtract(-5, Integer.MAX_VALUE)); System.out.println(isSafeToSubtract(1, Integer.MIN_VALUE)); System.out.println(isSafeToSubtract(-12, Integer.MIN_VALUE)); System.out.println(isSafeToSubtract(-1, Integer.MIN_VALUE)); System.out.println("checking addition"); System.out.println(isSafeToAdd(-1, Integer.MIN_VALUE)); // System.out.println(isSafeToSubtract(-2, Integer.MAX_VALUE)); // System.out.println(isSafeToSubtract(-5, Integer.MAX_VALUE)); // System.out.println(isSafeToSubtract(1, Integer.MAX_VALUE)); }