29. Divide Two Integers

Total Accepted: 70841 Total Submissions: 448890 Difficulty: Medium

 

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

If it is overflow, return MAX_INT.

 

思路：

dividend=a₁*divisor+a₂*divisor+...+a_n*divisor（a_x为2^k）。

以下情况造成溢出：

1.除数为0

2.被除数=INT_MIN，除数为-1

 

 

代码：

代码中只使用了int类型。注意INT_MIN=-2147483648，INT_MAX=2147483647。

1 class Solution { 2 public: 3     int divide(int dividend, int divisor) { 4         if(divisor==0||(dividend==INT_MIN&&divisor==-1)){ 5             return INT_MAX; 6         } 7         if(divisor==1){ 8             return dividend; 9         }10         if(dividend==INT_MIN){11             if(divisor&1){12                 return divide(dividend+1,divisor);13             }14             else{15                 return divide(dividend>>1,divisor>>1);16             }17         }18         if(divisor==INT_MIN){19             return 0;20         }21         //符号判断22         bool sign=(dividend<0)^(divisor<0);23         //这里要防止溢出，因此到这里要满足dividend!=INT_MIN，divisor!=INT_MIN24         if(dividend<0) dividend=-dividend;25         if(divisor<0) divisor=-divisor;26         int result=0,temp,tempd;27         while(dividend>=divisor){28             tempd=divisor;29             temp=1;30             //溢出判断31             while(INT_MAX>>1>=tempd&&dividend>=tempd){32                 tempd=tempd<<1;33                 temp<<=1;34             }35             if(dividend
     
      >=1;37                 temp>>=1;38             }39             dividend-=tempd;40             result+=temp;41         }42         return sign?-result:result;43     }44 };
     

 

 

或者：

1 class Solution { 2 public: 3     int divide(int dividend, int divisor) { 4         if (!divisor || (dividend == INT_MIN && divisor == -1)) 5             return INT_MAX; 6         int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; 7         long long dvd = labs(dividend); 8         long long dvs = labs(divisor); 9         int res = 0;10         while (dvd >= dvs) { 11             long long temp = dvs, multiple = 1;12             while (dvd >= (temp << 1)) {13                 temp <<= 1;14                 multiple <<= 1;15             }16             dvd -= temp;17             res += multiple;18         }19         return sign == 1 ? res : -res; 20     }21 };