问题
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
解答1:二分答案+倍增乘法
class Solution {
public:
int divide(int dividend, int divisor) {
long a = dividend, b = divisor;
bool neg = (a ^ b) < 0; // 两个数异或,结果小于0则异号
if (a < 0) a = -a;
if (b < 0) b = -b;
long left = 0, right = a;
while (left < right) {
long mid = (left + right + 1) >> 1;
if (mul(mid, b) > a) right = mid - 1;
else left = mid;
}
long res = neg ? -left : left;
if (res > INT_MAX || res < INT_MIN) return INT_MAX;
return res;
}
private:
long mul(long a, long b) {
long res = 0;
while (b > 0) {
if (b & 1) res += a;
a += a;
b >>= 1;
}
return res;
}
};
重点思路
中间变量有使用long
,这样逻辑会清楚很多。首先统计是否异号,然后将两个数均置为正数。使用二分答案的方法缩小解的范围,二分中的check
函数使用倍增乘法的模版(类似快速幂),时间复杂度为\(O(log(a)) * O(log(b))\)。
解答2
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) return INT_MAX; // 唯一可能导致res溢出的输入
if (divisor == 1) return dividend; // 防止INT_MIN / 1时,div中的res溢出
bool neg = (dividend ^ divisor) < 0;
if (divisor > 0) divisor = -divisor; // 全部置为负数,保证处理INT_MIN相关计算时不会溢出
if (dividend > 0) dividend = -dividend;
int res = div(dividend, divisor);
return neg ? -res : res;
}
private:
int div(int a, int b) {
if (a > b) return 0;
int res = 1, step = b;
while (a - step <= step) {
step += step;
res += res;
}
return res + div(a - step, b);
}
};
重点思路
- 两种特殊情况直接输出;
- 全部置为负数,保证处理
INT_MIN
相关计算时不会溢出; - 在
div
函数中,需要注意a
和b
都是小于等于0的。