力扣上的剑指offer第一道“简单”题,提交了n遍心态已崩,下面代码是题解中的代码
代码如下:
(使用减法代替除法,这里采用2倍增的方法减小复杂度)
class Solution {
public:
int divide(int a, int b) {
if (a == INT_MIN && b == -1) return INT_MAX;
//注意一种特殊情况:当a为最小值b为-1的时候,两者相除就会超出最大值,此时除法结果溢出
int sign = (a > 0) ^ (b > 0) ? -1 : 1;
//使用异或的方法判断除法结果的正负
if (a > 0) a = -a;
if (b > 0) b = -b;
//因为将 -2147483648 转成正数会越界,但是将 2147483647 转成负数,则不会
// 所以,我们将 a 和 b 都转成负数
unsigned int res = 0;
while (a <= b) {
int value = b;
// 如果不用 unsigned 的话,那么当 a = -2147483648, b = 1 的时候,k 会越界
unsigned int k = 1;
// 0xc0000000 是十进制 -2^30 的十六进制的表示
// 判断 value >= 0xc0000000 的原因:保证 value + value 不会溢出
// 可以这样判断的原因是:0xc0000000 是最小值 -2^31 的一半,
// 而 a 的值不可能比 -2^31 还要小,所以 value 不可能比 0xc0000000 小
while (value >= 0xc0000000 && a <= value + value) {
k += k;
value += value;
}
a -= value;
res += k;
}
// bug 修复:因为不能使用乘号,所以将乘号换成三目运算符
return sign == 1 ? res : -res;
}
};
- unsigned:int分为无符号unsigned和signed有符号两种类型,默认是有符号的,二者的区别是无符号类型能保存两倍有符号类型的数据,所以k使用无符号类型,避免导致除法结果溢出。
思路:对照上面的图片,value+=value,此时k+=k,当被除数大于等于value的时候就一直进行此循环,当小于时,就退出循环,注意外面还有一层大循环,就是当被除数>除数的时候就一直让被除数-除数,此时k=1。最后k就是除法结果。注意一种特殊情况除法结果溢出,还要注意避免其他结果除法溢出
采用位运算:
代码如下:
int divide(int a, int b) {
if (a == INT_MIN && b == -1) return INT_MAX;
int sign = (a > 0) ^ (b > 0) ? -1 : 1;
//转换成正数要定义为unsigned类型否则可能会导致溢出
unsigned int ua = abs(a);
unsigned int ub = abs(b);
unsigned int res = 0;
//从int存储最大的数开始,即从2的31次方开始
for (int i = 31; i >= 0; i--) {
if ((ua >> i) >= ub) {
ua = ua - (ub << i);
res += 1 << i;
}
}
// bug 修复:因为不能使用乘号,所以将乘号换成三目运算符
return sign == 1 ? res : -res;
}
- 左移右移:A<<B代表A*2的B次方;A>>B代表A/2的B次方