Discussion for Integer Overflow in Java

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));

}

About these ads