leetcode29两数相除

jiezi

5 年前

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

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

示例 1:

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

示例 2:

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

说明：

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

解题思路来自评论区的 foxleezh 大神。题目中明确不能使用/, 我们可以右移模拟除法，右移可以等价于下面的等式

右移 1 位，等价于，除以 2 的 1 次方。
右移 2 位，等价于，除以 2 的 2 次方。
右移 3 位，等价于，除以 2 的 3 次方。

a / 2 === a >> 1
a / 4 === a >> 2
a / 8 === a >> 3

被除数 / 除数 === 商……余数 等价于 ➡️ 被除数 === (商 * 除数) + 余数 等价于 ➡️ (被除数 - 余数) / 商 === 除数

假设，我们的被除数等于 100，除数等于 5。

根据等式 (被除数 - 余数) / 商 == 除数，我们首先要找到，100 除以多少 最接近于除数（或者说，除以多少时会大于等于除数）。

当 100 除以 2^31 时，结果相较于除数会非常的小。我们使用循环逐渐减少右移的位数，逐渐逼近除数，当 100 >>> 4（100 / 16）时等于 6，大于等于 5。

这时，我们可以肯定 商是大于 16（2 的四次方）的某个数（或者说，100 至少包含 16 个 5）。

我们使用 被除数 = 被除数 - 16 * 除数 等于还剩下的没有除干净的数。目前还剩下 20。我们再次使用上述的方法，再次逼近除数（获取 20 里还有几个 5）。最终得到最后的结果。


/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    
    // 判断结果是否为负数
    const isNegative = (dividend ^ divisor) < 0
    
    // 统一按正数处理
    dividend = Math.abs(dividend)
    divisor = Math.abs(divisor)
    
    if (dividend === 0) {return 0}
    
    if (dividend === 2147483648 && divisor === 1) {
        // 避免结果溢出
        return isNegative ? -dividend/divisor : dividend/divisor - 1
    }
    
    let result = 0
    
    for (let i = 31; i >= 0; i--) {
        // 注意这里需要使用无符号右移
        if ((dividend >>> i) >= divisor) {result += Math.pow(2, i)
            dividend -= Math.pow(2, i) * divisor
        }
    }
    
    return isNegative ? -result : result
};

leetcode29两数相除

原题

思路

代码