29.Divide Two Integers¶
Tags: Medium
Math
Bit Manipulation
Links: https://leetcode.com/problems/divide-two-integers/
Given two integers dividend
and divisor
, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend
by divisor
.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Note:
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
class Solution {
public:
int divide(int dividend, int divisor) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long m = labs(dividend), n = labs(divisor);
if (m < n) return 0;
long tmp = n, p = 1, res = 0;
while (m > (tmp << 1)) {
tmp <<= 1;
p <<= 1;
}
res += p + divide(m - tmp, n);
if ((dividend < 0) ^ (divisor < 0)) res = -res;
return res > INT_MAX ? INT_MAX : res;
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Divide Two Integers.
Memory Usage: 8.4 MB, less than 14.00% of C++ online submissions for Divide Two Integers.
循环的部分的思路其实就是在模拟竖式除法。判断符号通过异或运算得出。
之所以需要判断是否大于INT_MAX
,是因为存在INT_MIN / (-1)
的情况。