题目描述 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 位有符号整数，其数值范围是
。本题中，如果除法结果溢出，则返回
。
思路1
我们知道，乘法可以由多次加法来模拟，那么除法也可以用减法来模拟，例如
20 / 3 = 6.....2
我们可以理解为
20 - 3 = 17 > 3
17 - 3 = 14 > 3
......
5 - 3 = 2 < 3 停止
那么我们可以用这种不断相减的思路，当减去除数，并令记录值count++，得到的值小于除数的时候，停止算法，返回count
代码实现
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
let res = 0
let sign_dividend = dividend > 0 ? 1 : -1
sign_divisor = divisor > 0 ? 1 : -1
let a = Math.abs(dividend)
let b = Math.abs(divisor)
while (a >= b) {
res++
a = a - b
}
let sign = sign_dividend * sign_divisor
res =
sign > 0
? Math.min(res, Math.pow(2, 31) - 1)
: Math.min(res, -Math.pow(-2, 31))
return res * sign
};
但是这种算法有一个明显的缺点，就是太慢了，假设被除数为而除数为
的时候，计算的次数非常大，从而会导致算法超时。
思路2
在思路1的基础上，我们可以进行一些优化。但是在优化之前我们还需要注意到，由于javascript定义的Number数据类型边界是，本来是不需要考虑本题溢出的情况的，但是为了使得逻辑通用，我们依然考虑边界情况，当被除数是
，除数为
时，得到的值是
，已经溢出了，所以我们可以把被除数和除数都转为负数进行运算，避免溢出。
针对思路1中的运算，我们每次都是减去一个除数，这样试探的效率太低，我们可以思考下面这张试探的思路
20 / 3 = 6......2
等价于
20 - (3 * 1) = 17, k = 1
20 - (3 * 2) = 20 - (3 + 3) = 14, k = 2
20 - (3 * 4) = 20 - (6 + 6) = 8, k =4
由于8 < 3 * 4，停止，开始令被除数为8
8 - 3 = 5, k = 1
8 - (3 * 2) = 2, k = 2
由于2 < 3 * 2，停止，开始令被除数为2
2 < 3，停止计算，返回结果 res = 4 + 2 = 6
代码实现
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function (a, b) {
let res = 0
const MIN = Math.pow(-2, 31),
MAX = Math.pow(2, 31) - 1
if (a === MIN && b === -1) return MAX
let sign = (a > 0) ^ (b > 0) ? -1 : 1
// 将a和b变为负数
if (a > 0) a = -a
if (b > 0) b = -b
while (a <= b) {
let value = b
let k = 1
while (a <= value + value) {
value += value
k += k
}
a -= value
res += k
}
return sign === 1 ? res : -res
}
注意到该算法的时间复杂度是。
结语
在思路2的基础上其实是可以再优化，使得时间复杂度为的，比如我们可以令
从
开始往下试探，当
时被除数小于除数，下一轮
继续开始向下试探，这样最多执行31次即可停止，时间复杂度为
