Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Subscribe to see which companies asked this question
解法1：因为题目限制不能用乘法、除法和取模操作，考虑到除法可以使用减法来做，因此可以让被除数不断减去除数，直到小于或者等于0，而循环累计次数就是结果。这样做效率不高，在被除数很小，而除数很大时会超时Time Limit Exceeded
class Solution { public: int divide(int dividend, int divisor) { if (divisor == 0) return 0; bool isNegative = dividend > 0 ^ divisor > 0; long long divd = abs((long long)dividend); long long divr = abs((long long)divisor); long long loop = 0; while (divd > 0) { ++loop; divd -= divr; } if (divd < 0) --loop; if (loop > INT_MAX) loop = INT_MAX; return isNegative ? -loop : loop; } };
注意在调用abs函数时应先将参数提升为long long类型，否则调用int abs(int, int)在输入INT_MIN时会得出错误结果。
解法2：考虑使用二分搜索。初始化被减数rem为被除数，减数d为除数，计数值cnt为1，然后减数不断翻倍，计数值自增，直到大于被除数rem，然后被减数减去减数，相当于被除数除了cnt次除数；然后被减数减去这个减数，重设减数和计数值，进行下一次循环，直至被减数小于减数。
class Solution { public: int divide(int dividend, int divisor) { if (divisor == 0) return 0; if(divisor == 1) return dividend; bool isNegative = dividend > 0 ^ divisor > 0; long long divd = abs((long long)dividend); long long divr = abs((long long)divisor); long long loop = 0, rem = divd; while (rem >= divr) { long long d = divr, l = 1; while ((d <<= 1) <= rem) l <<= 1; rem -= (d >> 1); loop += l; } if (loop > INT_MAX) loop = INT_MAX; return isNegative ? -loop : loop; } };
[LeetCode]74. Divide Two Integers除法运算
原文：http://www.cnblogs.com/aprilcheny/p/4959777.html