[LeetCode] 029. Divide Two Integers (Medium) (C++/Python)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

029. Divide Two Integers (Medium)链接：

题目：https://oj.leetcode.com/problems/divide-two-integers/代码(github)：https://github.com/illuz/leetcode

题意：

实现除法，不能用乘、除和取模。

分析：

不能用乘、除和取模，那剩下的，还有加、减和位运算。

会想到的就是一次次去减，，不过这样会超时。在 1 的基础上优化下，跟快速幂一样，每次把除数翻倍（用位运算即可）。

这里有坑，就是结果可能超 int 范围，所以最好用 long long 处理，之后再转 int。

代码：

C++:

class Solution {public:int divide(int dividend, int divisor) {ll a = dividend >= 0 ? dividend : -(ll)dividend;ll b = divisor >= 0 ? divisor : -(ll)divisor;ll result = 0, c = 0;bool sign = (dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0);while (a >= b) {c = b;for (int i = 0; a >= c; i++, c <<= 1) {a -= c;result += (1<<i);}}if (sign) {return max((ll)INT_MIN, -result);} else {return min((ll)INT_MAX, result);}}};

Python:

class Solution:# @return an integerdef divide(self, dividend, divisor):sign = (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0)a, b = abs(dividend), abs(divisor)ret, c = 0, 0while a >= b:c = bi = 0while a >= c:a -= cret += (1<<i)i += 1c <<= 1if sign:ret = -retreturn min(max(-2147483648, ret), 2147483647)

销售世界上第一号的产品–不是汽车，而是自己。