[leetcode] Divide Two Integers

Divide Two Integers

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

If it is overflow, return MAX_INT.

思路：类似二分查找算法，只不过我们做的是对除数的倍增或者倍减。

注意点：

1，提前判断除数与被除数的正负，用来判断最后结果的正负性。

2，为了防止溢出，将int型转换为long long类型进行运算，最后将结果转换为int型。

例如：100 / 3

第一步：因为100 > 3，得到 dividend = 100 - 3 = 97, dividor = 3 + 3 = 6, pre_ret = 1, ret = 1;

第二步：因为97 > 6，得到 dividend = 97 - 6 = 91, dividor = 6 + 6 = 12, pre_ret = 1 + 1 = 2, ret = 1 + 2 = 3;

第三步：因为91 > 12，得到 dividend = 79, dividor = 24, pre_ret = 4, ret = 7;

第四步：因为79 > 24，得到 dividend = 55, dividor = 48, pre_ret = 8, ret = 15;

第五步：因为55 > 48，得到 dividend = 7, dividor = 96, pre_ret = 16, ret = 31;

（因为此时dividend > dividor了，所以dividor的倍增此处结束，接下来做倍减）

第六步：因为7 < 96，得到 dividend = 7, dividor = 48, pre_ret = 8, ret = 31;

第四步：因为7 < 48，得到 dividend = 7, dividor = 24, pre_ret = 4, ret = 31;

第四步：因为7 < 24，得到 dividend = 7, dividor = 12, pre_ret = 2, ret = 31;

第四步：因为7 < 12，得到 dividend = 7, dividor = 6, pre_ret = 1, ret = 31;

第四步：因为7 > 6，得到 dividend = 1, dividor = 3, pre_ret = 0, ret = 33;

此时 1 小于最原始的除数3，终止循环，根据除数与被除数的正负关系返回ret值即可。

 1 class Solution
 2 {
 3 public:
 4   int divide(int dividend, int dividor)
 5   {
 6     if(dividend == INT_MIN && dividor == -1)
 7       return INT_MAX;
 8  
 9     auto sign = [=] (int x) -> int { return x>0? 1 : -1;};
10     int p1 = sign(dividend);
11     int p2 = sign(dividor);
12  
13     long long n1 = abs(static_cast<long long>(dividend));
14     long long n2 = abs(static_cast<long long>(dividor));
15  
16     long long ret = 0;
17     long long pre_ret = 0;
18     while(n1 >= n2)
19     {
20       if(ret == 0 && pre_ret == 0)
21       {
22         pre_ret = 1;
23         ret = 1;
24       }
25       else
26       {
27         pre_ret += pre_ret;
28         ret = pre_ret + ret;
29       }
30  
31       n1 -= n2;
32       n2 += n2;
33     }
34  
35     while(n2 >= abs(static_cast<long long>(dividor)) && n1 >= abs(static_cast<long long>(dividor)))
36     {
37       if(pre_ret == 0)
38       {
39         ret += 1;
40         break;
41       }
42  
43       if(n1 < n2)
44       {
45         n2 = n2 >> 1;
46         if(n1 == n2)
47         {
48           ret += pre_ret;
49           break;
50         }
51         pre_ret = pre_ret >> 1;
52       }
53       else
54       {
55         n1 -= n2;
56         n2 = n2 >> 1;
57         if(n1 == n2)
58         {
59           ret += pre_ret;
60           break;
61         }
62         ret = pre_ret + pre_ret + ret;
63         pre_ret = pre_ret >> 1;
64       }
65     }
66  
67     if(p1 == p2)
68       return ret;
69     else
70       return -ret;
71   }
72 };