无乘除模运算符实现整数除法的Python代码错误排查

题目背景 #

给定两个整数dividend（被除数）和divisor（除数），在不使用乘法、除法、取模运算符的前提下实现两数相除，整数除法结果需向零截断。

测试调用divide(-10, -3)时期望返回3，实际返回-3，存在逻辑错误。

核心问题点 #

• 符号判断逻辑错误（直接导致本次测试用例失败）
  现有逻辑只要检测到被除数或除数为负，就将符号标记flag设为True，但正确规则是两数符号相异时结果为负，同号时结果为正。测试用例中-10和-3均为负数，两次给flag赋值True后标记仍为负，导致正确的计算结果3被加上负号返回-3。
• 判断条件与边界返回错误
  循环中判断累加值超过被除数使用的是>，当被除数和除数相等且值为1时（比如divide(1,1)），累加值等于被除数不会触发返回，循环结束后直接返回无意义的-1，结果完全错误。
• 算法效率不达标
  逐次累加除数的计数方式时间复杂度为O(n)，遇到大整数场景（比如2^31-1除以1）需要循环20亿次以上，会直接超时，无法通过题目全部测试用例。

修复后代码 #

def divide(dividend, divisor):
    # 处理32位整数溢出的题目边界要求
    INT_MAX = 2 ** 31 - 1
    INT_MIN = -2 ** 31
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX

    # 用异或逻辑正确判断结果符号：两数符号不同则结果为负
    is_negative = (dividend < 0) != (divisor < 0)

    # 转成正数计算
    dividend = abs(dividend)
    divisor = abs(divisor)

    result = 0
    # 位移实现快速累加，时间复杂度降到O(logn)
    while dividend >= divisor:
        current_val = divisor
        count = 1
        while dividend >= current_val << 1:
            current_val <<= 1
            count <<= 1
        dividend -= current_val
        result += count

    return -result if is_negative else result

内容的提问来源于stack exchange，提问作者goku