Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
这道题让我们求两数相除，而且规定我们不能用乘法，除法和取余操作，那么我们还可以用另一神器位操作Bit Operation，思路是，如果被除数大于或等于除数，则进行如下循环，定义变量t等于除数，定义计数p，当t的两倍小于等于被除数时，进行如下循环，t扩大一倍，p扩大一倍，然后更新res和m。这道题的OJ给的一些test case非常的讨厌，因为输入的都是int型，比如被除数是-2147483648，在int范围内，当除数是-1时，结果就超出了int范围，需要返回INT_MAX，所以对于这种情况我们就在开始用if判定，将其和除数为0的情况放一起判定，返回INT_MAX。然后我们还要根据被除数和除数的正负来确定返回值的正负，这里我们采用长整型long来完成所有的计算，最后返回值乘以符号即可，代码如下：
解法一：
class Solution { public: int divide(int dividend, int divisor) { if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX; long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; if (n == 1) return sign == 1 ? m : -m; while (m >= n) { long long t = n, p = 1; while (m >= (t << 1)) { t <<= 1; p <<= 1; } res += p; m -= t; } return sign == 1 ? res : -res; } };
我们可以使上面的解法变得更加简洁：
解法二：
class Solution { public: int divide(int dividend, int divisor) { long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0; if (m < n) return 0; while (m >= n) { long long t = n, p = 1; while (m > (t << 1)) { t <<= 1; p <<= 1; } res += p; m -= t; } if ((dividend < 0) ^ (divisor < 0)) res = -res; return res > INT_MAX ? INT_MAX : res; } };
我们也可以通过递归的方法来解，思路都一样：
解法三：
class Solution { public: int divide(int dividend, int divisor) { long long res = 0; long long m = abs((long long)dividend), n = abs((long long)divisor); if (m < n) return 0; long long t = n, p = 1; while (m > (t << 1)) { t <<= 1; p <<= 1; } res += p + divide(m - t, n); if ((dividend < 0) ^ (divisor < 0)) res = -res; return res > INT_MAX ? INT_MAX : res; } };
本文转自博客园Grandyang的博客，原文链接：两数相除[LeetCode] Divide Two Integers ，如需转载请自行联系原博主。
