29. Divide Two Integers LeetCode Java

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Solution:

dividend=dividend* quotient + reminder= dividend(a0*2^0+ a1*2^1+...an*2^n) + reminder, where a0,a1...an will be either 0 or 1.

quotient is the result we want. So according to this, we can use bit operation to find the n, then from n to 1, we can calculate all an...a0, and calculate the quotient.

Several tips:

1. check if a number is Integer.MIN_VALUE before do Math.abs(); because it will cause Integer overflow and return Integer.MIN_VALUE

2. A trick to avoid Integer overflow when dividend== Integer.MIN_VALUE, assign the initial value of result to 1 and dividend+=divisor.

3. A trick to find n, compare with dividend/2 rather than directly with dividend, the benefits of doing this is 1) avoid Integer Overflow, 2) find the n directly and don't have to divided by 2 if directly compare with dividend
Time complexity: O(logn)

 public int divide(int dividend, int divisor) {  
    if(divisor==0) return Integer.MAX_VALUE;  
    if(dividend==0) return 0;  
    boolean pos=(dividend>0 && divisor>0) ||(dividend<0 && divisor<0);  
    if(divisor==Integer.MIN_VALUE) return (dividend==Integer.MIN_VALUE)? 1:0;  
     divisor=Math.abs(divisor);  
    int res=0;  
    if(dividend==Integer.MIN_VALUE){  
     if(divisor==1) return pos? Integer.MAX_VALUE : Integer.MIN_VALUE;  
     res=1;  
     dividend+=divisor;  
    }  
    dividend=Math.abs(dividend);  
    int d=0;  
    int factor=1;  
    while(divisor<=(dividend>>1)){  
      divisor=divisor<<1;  
      d++;  
      factor=factor<<1;  
    }  
    for(int i=0;i<=d;i++){  
      if(dividend>=divisor){  
        dividend-=divisor;  
        res+=factor;  
      }  
      divisor=divisor>>1;  
      factor=factor>>1;  
    }  
    return pos? res:-res;  
   }