Leetcode 29. Divide Two Integers

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_MIN
24         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<tempd){
36                 tempd>>=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 };