题目:输入2个int型整数，它们进行除法计算并返回商，要求不得使 用乘号'*'、除号/及求余符号'%'。当发生溢出时，返回最大的整数值。假设 除数不为0。例如，输入15和 2，输出 15/2的结果，即7。
注意:
- 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2 ^ 31, 2 ^ 31 − 1]。本题中，如果除法结果溢出，则返回 2 ^ 31 − 1
示例 1：
// 输入：a = 15, b = 2
// 输出：7
// 解释：15/2 = truncate(7.5) = 7
示例 2：
// 输入：a = 7, b = -3
// 输出：-2
// 解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
// 输入：a = 0, b = 1
// 输出：0
示例 4：
// 输入：a = 1, b = 1
// 输出：1
提示:
- -2 ^ 31 <= a, b <= 2 ^ 31 - 1
- b != 0
注意：本题与LeetCode 29 题相同。
思路分析
本题的思路优先考虑位运算。在考虑使用位运算之前，我们首先来考虑一下一些边界问题。比如当a为最小值，b为-1的时候，这时候a / b 一定是最大值，也就不满足题意。所以需要返回满足题意的最大值。伪代码如下:
const min = -Math.pow(2,31),
max = Math.pow(2,31) - 1;
if(a <= min && b === -1){
return max;
}
if(a <= min && b === 1){
return min;
}
接着，我们还需要判断符号是否同号，同号为正，异号为负，因此我们需要使用一个变量来表示符号。伪代码如下:
// 默认是正数，为1
let sign = 1;
if((a > 0 && b < 0) || (a < 0 && b > 0)){
sign = -1;
}
接着还有一点，我们需要知道首先被除数a可以是0，但是除数b是不能为0的，这是一个特别的条件。但其实我们可以包含在a < b这个条件中的。因为如果a < b，则a / b一定等于0。因此我们还需要加入这个判断。伪代码如下:
// 由于不知道a和b哪个为正，哪个为负，因此可以用三元表达式判断一下将a和b都转成正数
a = a < 0 ? -a : a;
b = b < 0 ? -b : b;
//或者也可以使用库的转成绝对值的函数，例如js中的Math.abs
if(a < b){
return 0;
}
边界问题考虑完成之后，接下来我们来考虑如何使用位运算。首先根据题意，我们不能考虑乘除法来解答，那么我们是不是可以考虑减法来替代。当然如果只是单纯的循环去做减法，则时间复杂度一定很高，因此我们是不可能如此做的。那么此时位运算就有了用武之地，并且我们应该知道使用位运算之后我们是不需要考虑处理小数的。当然如果不熟悉位运算的话，我们是并不知道应该使用哪个位运算的。我们先不考虑使用位运算，我们用减法来替代的话，应该可以写出如下的伪代码:
let res = 0
while(a >= b){
a -= b;
res++;
}
可以看到使用减法来代替除法还是比较简单的，这在a和b的值都比较小时还比较适用，但是如果a和b都很大的时候，以上的解法的时间复杂度就比较高。因此我们需要使用位运算来代替。那么这里我们应该使用哪个位运算操作符呢？观察a -= b，我们可以发现实际上相当于每次都是对a做一次减b，也就相当于减去b的倍数，直到满足a < b为止。而每次b增大一倍，如果转换成二进制数，实际上就相当于左移了一位，因此我们就可以想到了本题需要使用左移操作符(<<),而我们应该知道二进制位最多只有31位，也就是说我们最多只能左移31位，此时迭代值i的起始值我们就知道了。因此以上的伪代码我们可以替换如下:
let res = 0
for(let i = 31;i >= 0;i--){
// 大于等于b的时候才需要减去b
if(a >= b){
a -= (b << i);
res += (1 << i);
}
}
我们再尝试优化一下循环中的判断，a < b 并且每次a都对b做倍数减法，因此我们可以理解成a向右移动第i位然后再判断是否小于b。因此我们可以改写如下:
let res = 0
for(let i = 31;i >= 0;i--){
// 大于等于b的时候才需要减去b
if((a >>> i) >= b){
a -= (b << i);
res += (1 << i);
}
}
最后，我们综合一下如上分析的伪代码，即可解答本题。
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var divide = function(a, b) {
let res = 0,
min = -Math.pow(2,31),
max = Math.pow(2,31) - 1,
sign = 1;
if(a <= min && b === -1){
return max;
}
if(a <= min && b === 1){
return min;
}
// 判断符号
if((a > 0 && b < 0) || (a < 0 && b > 0)){
sign = -1;
}
// 将a和b都转成正数
a = a < 0 ? -a : a;
b = b < 0 ? -b : b;
if(a < b){
return 0;
}
for(let i = 31;i >= 0;i--){
if((a >>> i) - b >= 0){
a -= (b << i);
res += (1 << i);
}
}
// 返回res
return sign === -1 ? -res : res;
};
以上算法的时间复杂度和空间复杂度分析如下:
- 时间复杂度 O(1)： 最差情况下，需循环 32 次，使用 O(1) 时间；每轮中的常数次位操作使用 O(1) 时间。
- 空间复杂度 O(1)： 使用常数大小的额外空间。
Comments