给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是
[−231, 231 − 1]。本题中，如果除法结果溢出，则返回231 − 1。
思路
- 使用二进制位运算、减法实现
- 先左移扩大除数到被除数最大范围内
- 然后用减法去获取商，然后更新商
实现
class Solution {
public:
/*
dividend 被除数
divisor 除数
*/
int divide(int dividend, int divisor) {
if (dividend == 0) return 0;
// 转换为long long型计算，防止 INT32_MIN / -1 溢出
long long lldividend = dividend, lldivisor = divisor;
long long cur_bit = 1, result = 0;
// 转换为整数计算，最后判断符号
lldividend = abs(lldividend);
lldivisor = abs(lldivisor);
// 先将被除数放大 2^cur_bit 倍，减少时间复杂度
// 但是要保证被除数 <= 除数
while (lldividend >= lldivisor << 1) {
lldivisor <<= 1;
cur_bit <<= 1;
}
// 除数依次减去被除数的 cur_bit 倍
// 右移 cur_bit 循环执行减法
// 直到 除数为 0 或者 cur_bit == 0
while (cur_bit > 0 && lldividend > 0) {
if (lldividend >= lldivisor) {
lldividend -= lldivisor;
result += cur_bit;// 更新商
}
cur_bit >>= 1;
lldivisor >>= 1;
}
// 判断 result 符号
result = (dividend > 0 && divisor < 0 ||
dividend < 0 && divisor > 0) ? - result : result;
// 判断是否会溢出，并返回结果
if (result > INT32_MAX) return INT32_MAX;
return (int) result;
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
