两数相除

难度: Medium

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

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2³¹, 2³¹− 1] 。本题中，如果商 严格大于 2³¹− 1 ，则返回 2³¹− 1 ；如果商 严格小于 -2³¹ ，则返回 -2³¹。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

-2³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Submission

运行时间: 204 ms

内存: 14.8 MB

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if (dividend < 0 and divisor) > 0 or (dividend > 0 and divisor < 0):
            sign = -1
        else:
            sign = 1

        divisor = abs(divisor)
        dividend = abs(dividend)

        def mul(a, b):
            ans = 0
            while b != 0:
                if b & 1 != 0:
                    ans += a
                a <<= 1
                b >>= 1
            return ans

        l = 0
        r = dividend
        while l < r:
            mid = l + (r - l + 1) // 2
            if mul(mid, divisor) <= dividend:
                l = mid
            else:
                r = mid - 1
        ans = sign * l
        if ans > (1 << 31) - 1 or ans < -1 << 31:
            return (1 << 31) - 1
        return ans

Explain

这个题解使用二分查找的方法来找出商。首先判断结果的正负号。然后将被除数和除数都转为正数。在二分查找的过程中，使用自定义的 mul 函数来计算中间结果 mid 乘以除数是否小于等于被除数。mul 函数通过位运算来实现乘法，避免使用乘号。最后根据正负号返回二分查找的结果 l，并判断是否溢出。

时间复杂度: O(log n * log b)

空间复杂度: O(1)

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 判断结果的正负号
        if (dividend < 0 and divisor) > 0 or (dividend > 0 and divisor < 0):
            sign = -1
        else:
            sign = 1
        
        # 将被除数和除数都转为正数
        divisor = abs(divisor)
        dividend = abs(dividend)
        
        # 自定义乘法函数，用位运算实现
        def mul(a, b):
            ans = 0
            while b != 0:
                if b & 1 != 0:
                    ans += a
                a <<= 1
                b >>= 1
            return ans
        
        # 二分查找
        l = 0
        r = dividend
        while l < r:
            mid = l + (r - l + 1) // 2
            if mul(mid, divisor) <= dividend:
                l = mid
            else:
                r = mid - 1
        
        # 根据正负号返回结果
        ans = sign * l
        
        # 判断是否溢出
        if ans > (1 << 31) - 1 or ans < -1 << 31:
            return (1 << 31) - 1
        return ans

Explore

二分查找通过迭代缩小搜索的范围来找到正确的商。在每次迭代中，计算中点 mid，并使用自定义的 mul 函数来检查 mid 乘以除数是否小于等于被除数。这个过程继续直到搜索范围缩小到无法继续缩小（即 l 和 r 相邻或相等）。针对边界条件，特别是被除数等于除数的情况，二分查找通过从 l 到 r 的范围中持续查找确保可以找到精确的商。此外，通过设置 r = dividend 并令 mid = l + (r - l + 1) // 2 确保在接近边界时可以正确地处理。

mul 函数使用位运算实现乘法，其效率依赖于乘数 b 的位数。对于较大的 b 值，函数需要更多的迭代来完成乘法，因为它每次迭代只处理 b 的一个位。当 b 的值非常大时，这会导致效率问题，尤其是在乘以较大的 a 值时。因此，尽管避免了乘号的使用，但在处理大数乘法时，性能可能会受到影响，特别是在 b 的二进制表示中有较多位设置为 1 的情况下。

在二分查找中，通过不断调整 l 和 r 的值逐渐缩小搜索范围。当 mid * divisor 小于等于 dividend 时，将 l 设为 mid，因为这意味着可能的商至少为 mid；如果 mid * divisor 大于 dividend，则将 r 设为 mid - 1，因为这意味着商必然小于 mid。通过不断迭代，直到 l 和 r 相遇或相邻，这样可以保证找到最接近且不超过实际商的整数值。这个过程特别在 mid * divisor 接近 dividend 时显得非常重要，因为它保证了即使在这种边界情况下，也能够找到正确的商。

目前的算法实现确实在最终结果计算前仅检查是否超出了 32 位整数的范围。然而，理论上在 mul 函数中的乘法过程也可能发生溢出，尤其是当 a 和 b 都非常大时。尽管 Python 的整数类型可以自动处理大数，但在其他语言或环境中，这种乘法实现可能需要额外的检查来确保在中间计算步骤中不会发生溢出。在严格的环境下，应该在 mul 函数中加入检查以避免中间结果的溢出，特别是在位操作和加法操作中。