今日算法之_38_两数相除
前言
Github：https://github.com/HealerJean
1、两数相除
给定两个整数，被除数
a和除数b。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数
a除以除数b` 得到的商。
示例 1:
输入: a = 10, b = 3
输出: 3
解释: 10/3 = = 3
示例 2:
输入: a = 7, b = -3
输出: -2
解释: 7/-3 = = 3
提示：
被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
1.1、解题思路
1.1.1、位移解题
如：7 * 13 = 7 * (8 + 4 + 1) = 7 * 8 + 7 * 4 + 7 * 1
其中 8, 4, 1分别是2的 3, 2, 0 次幂 =>
7 * 13 = 7 << 3 + 7 << 2 + 7 << 0
比如： a/b = x => b * x = a：求 x
例子： 3 * x = 10，肉眼一看结果就是 3
第一次：
第一步： j = 1 ; 3 << j = 6 ; 6小于10,继续 j ++ => j = 2
j = 2 ; 3 << j = 12; 12大于10，
此时确定j的值，j因为多走了一下，所以此时选择 j = 2 - 1 = 1；
总结：a = 10 - (3 << 1) = 4 ; b = 3 ; (4 > 3) => (a > b) ; 这个时候除数比被除数大，继续
求 b * x = 4 => 3 * x = 4 ;
此时j = 1 => reuslt = 1 << j = 1 << 1 = 2
第二次：
第一步：j = 1 ; 3 << 1 = 6 6大于4，
此时确定j的值，j因为多走了一下，所以此时选择 j = 1 - 1 = 0
第二步：a = 4 - (3 >> 0) = 1 ; b = 3 ; (1 < 3) => a < b ；这个时候 除数 比被除数小，结束
此时 j = 0 ; result = result + 1 << j = result + 1 << 0 = 2 + 1 = 3
也就是最终结果：x = 2^1 + 2^0 = 2 + 1 = 3
1.1.2、边界问题
最小负数：Integer.MIN_VALUE = -2147483648
最大正数：Integer.MAX_VALUE = -2147483647
1.1.2.1、除数为最小负数除以-1，结果溢出（超过了最大正数）
//第一个极端情况，必须满足同时成立
// a = -2^31, b = -1, a/b = 2^31 内存溢出（Integer.MIN_VALUE/-1 = 2147483648 内存溢出），返回 Integer.MAX_VALUE
if (a == Integer.MIN_VALUE && b == -1) {
return Integer.MAX_VALUE;
}
1.1.2.2、 被除数为最小负数，一般没有人能够除开它，除了它自己
//负数最大值为被除数的时候。讨论极端情况
// a != -2^31, b = -2^31, a/b = 0 ，就没有任何数可以处以最小的负数，因为负数的绝对值太大了，所以返回 0
if (b == Integer.MIN_VALUE) {
// a = -2^31, b = -2^31, a/b = 1， 下面 while (b <= (a >> j)){ 除了
//除了它自己能除以自己，没人能除以它
if (a == Integer.MIN_VALUE) {
return 1;
}
return 0;
}
1.1.2.2、最小负数为参与运算，绝对值溢出（超过了最大正数）
//当a是最大的负数的时候，绝对值内存就溢出了，
// 所以想办法让他不溢出，那就是让他变成正数的时候数字变小。加上正数，减去小数 。最后结果计算完事了，在加或者减回来
// 比如 -7 / 3 => 7-3 = 4 4/3 = 1 => -1 - 1 = -2
// 比如 7 / 3 => 7-3 = 4 4/3 = 1 => 1 + 1 = 2
int buwei = 0;
if (a == Integer.MIN_VALUE) {
if (b > 0) {
a = a + b;
buwei = -1;
} else {
a = a - b;
buwei = 1;
}
}
1.2、算法
/**
* a是除数 b是被除数 a/b = result
*/
public int divide(int a, int b) {
//第一个极端情况，必须满足同时成立
// a = -2^31, b = -1, a/b = 2^31 内存溢出（Integer.MIN_VALUE/-1 = 2147483648 内存溢出），返回 Integer.MAX_VALUE
if (a == Integer.MIN_VALUE && b == -1) {
return Integer.MAX_VALUE;
}
//负数最大值为被除数的时候。讨论极端情况
// a != -2^31, b = -2^31, a/b = 0 ，就没有任何数可以处以最小的负数，因为负数的绝对值太大了，所以返回 0
if (b == Integer.MIN_VALUE) {
// a = -2^31, b = -2^31, a/b = 1， 下面 while (b <= (a >> j)){ 除了
//除了它自己能除以自己，没人能除以它
if (a == Integer.MIN_VALUE) {
return 1;
}
return 0;
}
//当a是最大的负数的时候，绝对值内存就溢出了，
// 所以想办法让他不溢出，那就是让他变成正数的时候数字变小。加上正数，减去小数 。最后结果计算完事了，在加或者减回来
// 比如 -7 / 3 => 7-3 = 4 4/3 = 1 => -1 - 1 = -2
// 比如 7 / 3 => 7-3 = 4 4/3 = 1 => 1 + 1 = 2
int buwei = 0;
if (a == Integer.MIN_VALUE) {
if (b > 0) {
a = a + b;
buwei = -1;
} else {
a = a - b;
buwei = 1;
}
}
//false 表示结果为负数，true表示结果为正数
boolean flag = false;
if ((b > 0 && a > 0) || (b < 0 && a < 0)) {
flag = true;
}
//将 a 和 b 都变成正数
if (a < 0) {
a = -a;
}
if (b < 0) {
b = -b;
}
int result = 0 ;
//从我们的解决思路逆推
while (a >= b) {
// 左移个数
int j = 1;
//你像思维，a不断右移（也就是不断除以2） 如果比a大的话，就继续执行，直到比b小
while (b <= (a >> j)){
j++;
}
//上面j多走了一下
j = j -1 ;
a = a - (b << j);
//结果相加
result = result + (1 << j) ;
}
//下面这种情况是一步步增大 值，很容易溢出，数字比较小还行，数字一大，就完蛋了
// while (a >= b) {
// // 左移个数
// int j = 1;
// while ((b << j) < a) {
// j++;
// }
// //j 在上面多加了1，真正的应该减去1
// j = j - 1;
// a = a - (b << j);
// //结果相加
// result = result + (1 << j) ;
// }
return (flag ? result : -result) + buwei;
}
1.3、测试
@Test
public void test() {
System.out.println(divide( Integer.MIN_VALUE, 1));
}
-2147483648
