题目描述
给定两个整数,被除数 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
思路
- 两数相除可以改成每次减去除数,减去去的次数就是商,我们对每次减去除数这一步进行优化,每次利用二进制相减 商用二进制相加的形式表示出来 除数 = 被除数(2^1 + 2^2 …) 乘进去然后不断相减
- 符号和数值分开计算 注意2个地方的溢出
res += 1LL << i;
和res > INT_MAX || res < INT_MIN
class Solution {
public:
/*
两数相除, 不使用 * / %
二进制方式来减
1.符号和数值分开计算 x/y = t
x = ty + 余数 将b, 2b, 4b, 8b, ...2nb的所有小于a的数值存在exp.push_back()里面
2. 从exp链表元素从末端开始枚举若 a>=exp[i]表示 t 包含 1LL << i 这个数值将2^i加入到res中并且更新a
商用二进制相加的形式表示出来 除数 = 被除数(2^1 + 2^2 ...) 乘进去然后不断相减
倍增思想: 每次减去一个大于除数的倍数,那么时间复杂度就能够得到优化
,同时该除数的倍数大小即为一次性减去该除数的个数
*/
int divide(int x, int y) {
typedef long long LL;
vector<LL> exp;
//默认为正号
bool is_minus = false;
if(x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;
LL a = abs((LL) x), b = abs((LL) y);
// i = i + i 的意思是 i*2 预处理出来所有商可能的二进制 就是 << 1位 预处
for(LL i = b; i <= a; i = i + i) exp.push_back(i);
LL res = 0;
for(int i = exp.size() - 1; i >= 0; i --){
//2^i 为 exp[i]
if(a >= exp[i]){
a -= exp[i];
//这里要注意 为1LL 防止溢出
res += 1LL << i;
}
}
if(is_minus) res = -res;
// -2^31 / -1 溢出
if(res > INT_MAX || res < INT_MIN) res = INT_MAX;
return res;
}
};