题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3 输出: 3

示例 2:

输入: dividend = 7, divisor = -3 输出: -2

说明:

被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

一. 二分法

先将被除数和除数都转换为非负数，然后根据除法的定义，我们可以知道除法可以转换为被除数 被 除数 减的次数，即当被除数大于等于除数时，用被除数减去除数的值再赋值给被除数，重复进行，记录直到被除数小于除数时的次数，即为商。

但是，上述算法存在的问题时，运算诸如2147483647/2时会超时。现在改进此算法，我们相减时，如果将除数每次翻倍之后再减，那么记录增加的次数应该是翻倍后与原除数的倍数。当翻倍后的除数大于被除数，那么重置除数为原值，然后重新进行翻倍，重复上述计算，最后当被除数小于原除数时，结束结算，返回记录的次数，并注意符号。

js实现

/** * @param {number} dividend * @param {number} divisor * @return {number} */ var divide = function(dividend, divisor) { // 将被除数和除数都转换为正数 var sign = true if (dividend < 0) { dividend = - dividend sign = !sign } if (divisor < 0) { divisor = - divisor sign = !sign } var answer = 0 while (divisor <= dividend) { var count = 1 // 临时除数，每次扩大一倍 var temp_divisor = divisor while (temp_divisor <= dividend) { dividend -= temp_divisor answer += count count *= 2 temp_divisor *= 2 } } if (sign) { return Math.min(2147483647, answer) } else { return Math.max(-2147483648, -answer) } }

复杂度分析

时间复杂度：O(log(n))

空间复杂度：O(1)

测试结果

✔ Accepted ✔ 989/989 cases passed (76 ms) ✔ Your runtime beats 96.28 % of javascript submissions ✔ Your memory usage beats 82.35 % of javascript submissions (34.7 MB)