问题描述
来源:LeetCode第29题
难度:中等
给定两个整数,被除数dividend和除数divisor。将两数相除,要求不使用乘法、除法和mod运算符。返回被除数dividend除以除数divisor得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如truncate(8.345)=8以及truncate(-2.7335)=-2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示:
被除数和除数均为32位有符号整数。
除数不为 0。
假设我们的环境只能存储32位有符号整数,其数值范围是[−2^31,2^31−1]。本题中,如果除法结果溢出,则返回2^31−1。
解法一
这题说的不能使用*,/,%等符号,那么只能使用减法了,一种方式就是不停的减,比如20/3,用20不停的减去3,但这种效率太差。可以用20减去3的倍数,我们发现20减去6要比减去3更快,当不够减的时候再用他减去3。我们还发现用20减去12的时候要比减去6更快,所以发现一个规律,就是把除数不停的往左移,当除数离被除数最近的时候就用被除数减去除数。
这里要注意的是他们的符号,可以先把他们转化为正数,还有一点要注意就是Integer.MIN_VALUE转化为正数的时候会溢出,可以都转化为long类型。
public int divide(int dividend, int divisor) {
int sign = (dividend ^ divisor) >= 0 ? 1 : -1;//判断符号
long dividendTemp = Math.abs((long) dividend);//求绝对值
long divisorTemp = Math.abs((long) divisor);
long res = 0;
while (dividendTemp >= divisorTemp) {
long tmp = divisorTemp;
long times = 1;//除数divisor的倍数
while (dividendTemp >= (tmp << 1)) {
tmp <<= 1;
times <<= 1;
}
//被除数减去除数的times倍
dividendTemp -= tmp;
//累加times
res += times;
}
//添加符号
res = sign > 0 ? res : -res;
//需要判断是否有溢出
return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) res;
}
解法二
上面的解法有一定的局限性,为了防止溢出我们可以把int转化为long类型,但如果题中给的数据是long类型,就束手无策了。实际上也可以不用转,我们看一下int类型的范围
-2147483648 到 2147483647
也就是说如果我们把一个负数转化为正数可能会出现溢出,但把一个正数转化为一个负数就不会出现溢出。所以我们可以先把被除数和除数转化为负数,然后让他们相减。
public int divide(int dividend, int divisor) {
int sign = (dividend ^ divisor) >= 0 ? 1 : -1;//判断符号
dividend = -Math.abs(dividend);//都转换为负数
divisor = -Math.abs(divisor);//都转换为负数
int res = 0;
//阈值,越界警告值
int threshold = Integer.MIN_VALUE >> 1;
while (dividend <= divisor) {
int tmp = divisor;
int times = 1;
//tmp >= threshold,防止tmp一直往左移导致溢出
while (tmp >= threshold && dividend <= (tmp << 1)) {
tmp <<= 1;
times <<= 1;
}
dividend -= tmp;
res -= times;
}
//是否有溢出
if (res == Integer.MIN_VALUE && sign == 1)
return Integer.MAX_VALUE;
return sign < 0 ? res : -res;
}
难度升级
这题说的是不能使用乘法,除法,求余运算符。如果在限制一下,除了上面3种运算符以外,还不能使用“+”,“-”符号,看下该怎么解,我们来把上面第二种答案修改一下,如下所示,没有使用任何加减乘除符号
public int divide(int dividend, int divisor) {
boolean sign = (dividend ^ divisor) >= 0;//判断符号
dividend = dividend < 0 ? dividend : ~subtraction(dividend, 1);
divisor = divisor < 0 ? divisor : ~subtraction(divisor, 1);
int res = 0;
int threshold = Integer.MIN_VALUE >> 1;
while (dividend <= divisor) {
int tmp = divisor;
int times = 1;
//tmp >= threshold,防止tmp一直往左移导致溢出
while (tmp >= threshold && dividend <= (tmp << 1)) {
tmp <<= 1;
times <<= 1;
}
dividend = subtraction(dividend, tmp);
res = subtraction(res, times);
}
//是否有溢出
if (res == Integer.MIN_VALUE && sign)
return Integer.MAX_VALUE;
return !sign ? res : ~subtraction(res, 1);
}
private int subtraction(int a, int b) {
if (b == 0)
return a;
int c = a & b;
a ^= c;
b ^= c;
return subtraction(a | b, b << 1);
}
提示:
求x的相反数:~(x-1)或者~x+1
联系客服