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 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
解题思路
以17/3举例。
17 > 3 + 3 = 6, count = count * 2 = 2;
17 > 6 + 6 = 12, count = count * 2 = 4;
17 < 12+12 = 24, 不能继续往下除了。
返回 (count = 4) + ((17-12) = 5)/3的值。
这题要注意的是存在INT类型溢出的问题。那么什么情况有可能发生溢出呢？
- 被除数是Integer.MIN_VALUE, 除数是-1。这种情况是会发生溢出的。
- 上面的方式是正数的形式, 大小比较也是正数的比较。如果题目本身有正有负, 需要统一被除数和除数的符号, 那么统一用正号还是统一用负号？因为负数有可能存在Integer.MIN_VALUE, 这时无法用负数表示, 所以只能将被除数和除数统一表示为负数。
- 除数不断的乘2的过程, 可能会存在移除, 这个要加上溢出判断。
public int divide(int dividend, int divisor) {
if (divisor == -1 && dividend == Integer.MIN_VALUE) {
return Integer.MAX_VALUE; // 溢出
}
if (divisor == 1) return dividend;
if (divisor == -1) return -dividend;
// 先标记符号
int sign = 1;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
sign = -1;
// 都改为负号是因为int 的范围是[2^31, 2^31-1]，如果a是-2^32，转为正数时将会溢出
int a = dividend > 0 ? -dividend : dividend;
int b = divisor > 0 ? -divisor : divisor;
// 被除数的绝对值小于除数, 直接返回0
if (a > b) return 0;
// 求 a / b 的结果
int ans = div(a, b);
return sign == -1 ? -ans : ans;
}
// 这里要特别注意, 传进来的两个数字, 都是负数
int div(int a, int b) {
if (a > b) return 0;
int count = 1;
int tb = b;
// 相当于不断的乘2, 直到刚好不超过被除数
// tb + tb < 0 是为了保证不溢出 是因为溢出之后不再小于0
while (tb + tb >= a && tb + tb < 0) {
tb += tb;
count += count;
}
// 递归的求剩下的部分 a / b 的值
return count + div(a - tb, b);
}