题目
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
链接
https://leetcode-cn.com/problems/divide-two-integers/
代码
class Solution {
public int divide(int dividend, int divisor) {
// 当除数为1，直接返回被除数
if (divisor == 1) {
return dividend;
}
// 当除数为-1且被除数为Integer.MIN_VALUE时，将会溢出，返回Integer.MAX_VALUE
if (divisor == -1 && dividend == Integer.MIN_VALUE) {
return Integer.MAX_VALUE;
}
// 把被除数与除数调整为正数,为防止被除数Integer.MIN_VALUE转换为正数会溢出，使用long类型保存参数
if (dividend < 0 && divisor < 0) {
return divide(-(long) dividend, -(long) divisor);
} else if (dividend < 0 || divisor < 0) {
return -divide(Math.abs((long) dividend), Math.abs((long) divisor));
} else {
return divide((long) dividend, (long) divisor);
}
}
public int divide(long dividend, long divisor) {
// 如果被除数小于除数，结果明显为0
if (dividend < divisor) {
return 0;
}
long sum = divisor; // 记录用了count个divisor的和
int count = 1; // 使用了多少个divisor
while (dividend >= sum) {
// 每次翻倍
sum <<= 1;
count <<= 1;
}
// 此时dividend < sum
sum >>>= 1;
count >>>= 1;
// 此时dividend >= sum
// 将count个divisor从dividend消耗掉，剩下的还需要多少个divisor交由递归函数处理
return count + divide(dividend - sum, divisor);
}
public static void main(String[] args) {
Solution s = new Solution();
int a = 10;
int b = 3;
int c = s.divide(10,3);
System.out.println(c);
}
}
思路
首选32位整数 加减乘除 注意边界
java边界
Integer.MAX_VALUE
Integer.MIN_VALUE
最小值负数 Integer.MIN_VALUE -2147483648
最大值正数，即2147483647。
负数 1111111
整数 0111111
如果最小值 + 1的话，就会发生溢出，编程最大值。
其次，这道题 除法是采用 循环减法的方式 实现 除法求商Quotient
因此要 考虑 当 divisor 为 1 的时候 ，直接返回 dividend 被除数就好了。
另外，为了区分divided 和 divisor 正负的情况，建议统一将其转为 正数，然后采用 减法的形式。
但是注意 int的MIN值 是没有对应的 MAX的值的，因此，应该将次放在开始的特殊CASe。
这里，被减数 是 通过位移动实现的
比如。求10除以3的quotient
10 / 3
10 / 6
10 / 12返回
然后 10 - 6 = 4
4/3
4/6 返回
6 = 2 * 3
4 = 1 * 3
最终结果 = 2 + 1 = 3
首先处理特殊情况, 边缘问题 1 和 最大最小值
然后将 正负 全部转为 正
最后 采用循环减法
减法是通过 循环 减法 + 迭代
只要 10 dividend 大于 这边divisor加倍
就 count 加倍，divisor加倍
直到不行了，然后退一步，留下count
dividend减去退下的值，对剩余的值进行 循环减法。
References
https://blog.csdn.net/qq_39590763/article/details/85764780
