2015年9月19日星期六

Leetcode 29 Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

Solution 1: Use long
 public class Solution {  
   public int divide(int dividend, int divisor) {  
     return divide((long) dividend, (long) divisor);  
   }  
   private int divide(long a, long b) {  
     boolean pos=true;  
     if (a<0) pos=!pos;  
     if (b<0) pos=!pos;  
     a=Math.abs(a);  
     b=Math.abs(b);  
     int i=0;  
     while (a>=b<<i) i++;  
     i--;  
     long res=0; //res need to be long  
     while (i>=0) {  
       if (a>=b<<i) {  
         a-=b<<i;  
         res|=(long)1<<i; //pay attention here, otherwise 2147483648 will be negtive  
       }  
       i--;  
     }  
     if (!pos) res=-res;  
     if (res>Integer.MAX_VALUE || res<Integer.MIN_VALUE) return Integer.MAX_VALUE;  
     return (int)res;  
   }  
 }  
Solution 1: Do not use long but deal corner case first.
 public class Solution {  
   public int divide(int dividend, int divisor) {  
     boolean pos=true;  
     boolean min=false;  
     if (divisor==0) return Integer.MAX_VALUE;  
     if (divisor==Integer.MIN_VALUE) {  
       if (dividend==Integer.MIN_VALUE) return 1;  
       else return 0;  
     }  
     if (dividend==Integer.MIN_VALUE) {  
       if (divisor==1) return Integer.MIN_VALUE;  
       else if (divisor==-1) return Integer.MAX_VALUE;  
       else {  
         min=true;  
         dividend+=Math.abs(divisor);  
       }  
     }  
     if (dividend<0) {  
       dividend=-dividend;  
       pos=!pos;  
     }  
     if (divisor<0) {  
       divisor=-divisor;  
       pos=!pos;  
     }  
     int i=0;  
     while (dividend>>i>=divisor) i++;  
     i--;  
     int res=0;  
     for (; i>=0; i--) {  
       if (dividend>=divisor<<i) {  
         dividend-=divisor<<i;  
         res|=1<<i;  
       }  
     }  
     if (min) res++;  
     if (!pos) res=-res;  
     return res;  
   }  
 }  

没有评论:

发表评论