力扣搜索LCR即为剑指Offer的所有题目。
题目规定只能用32位整数，所以取值范围在-2^31 ~ 2^31 - 1 之间。
这里的特殊情况为什么不考虑被除数和除数为最大值？
因为后面会将所有的数都转为负数，所以考虑复数的最小值就是在考虑最大值。后面都转为负数了，就和正常的一样了。
先考虑所有的特殊情况
- 如果被除数为最小值-2^31:
- 如果除数为1，则商为最小值-2^31
- 如果除数为-1，则商为2^31, 此时溢出，所以应该返回2^31 - 1
- 如果除数为最小值-2^31:
- 如果被除数为最小值-2^31，那么商为1
- 如果被除数为其他值，商为0
其余情况，会有除数为正负、被除数为正负四种情况，处理起来比较麻烦。
所以考虑将他们全转为正数或负数。
这里考虑当有值为-2^31时，转为正数会变成2^31溢出，所以需要全转为负数(实际和全为正数是一样的。)
再往后就是正常情况。设被除数为X 除数为Y 且X Y均为负数，商为Z，则满足
Y * Z <= X <= Y * (Z + 1)
所以可以在0-MAX之间二分Z，得到满足Y * Z <= X 的最大的Z。
由于不能用除法，所以二分在找mid时是left + (right - left) >> 1 实现的。
而且需要计算Y * Z的值，这里也不能用乘法，所以需要用到快速乘的方法。
class Solution {
public int divide(int a, int b) {
if(a == Integer.MIN_VALUE){
if(b == 1) return Integer.MIN_VALUE;
else if(b == -1) return Integer.MAX_VALUE;
}
if(b == Integer.MIN_VALUE){
if(a == Integer.MIN_VALUE) return 1;
else return 0;
}
boolean rev = false;
if(a > 0){
a = -a;
rev = !rev;
}
if(b > 0){
b = -b;
rev = !rev;
}
int l = 1, r = Integer.MAX_VALUE, ans=0;
while(l <= r){
int mid = l + ((r-l) >> 1);
if(quickAdd(b, mid, a)){ //小于等于
ans = mid;
// 注意溢出
if (mid == Integer.MAX_VALUE) {
break;
}
l = mid + 1;
}
else r = mid-1;
// System.out.println("l=" + l + " r=" + r + " mid=" + mid);
}
return rev ? -ans : ans; //如果需要取反就取反
}
// 快速乘
public static boolean quickAdd(int y, int z, int x) {
// x 和 y 是负数，z 是正数
// 需要判断 z * y >= x 是否成立
int result = 0, add = y;
while (z != 0) {
if ((z & 1) != 0) {
// 需要保证 result + add >= x
if (result < x - add) {
return false;
}
result += add;
}
if (z != 1) {
// 需要保证 add + add >= x
if (add < x - add) {
return false;
}
add += add;
}
// 不能使用除法
z >>= 1;
}
return true;
}
}