给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

def divide(dividend, divisor):
    if dividend == 0:
        return 0
    
    # 只能存储 32 位有符号整数，其数值范围是 [−2**31,  2**31 − 1]。本题中，如果除法结果溢出，则返回 2**31 − 1
    if dividend == -2 ** 31 and divisor == -1:
        return 2 ** 31 -1
    
    s1 = dividend > 0
    s2 = divisor > 0
    same_s = s1 == s2
    
    abs_dividend = abs(dividend)
    abs_divisor = abs(divisor)
    
    # 尝试减去1、2、4、8……个除数
    def divide_part(a, b):
        if a < b:
            return 0
        res = 1
        value = b
        while a >= value + value:
            value += value # 用加法代替乘2
            res += res
        return res + divide_part(a - value, b)
    
    result = divide_part(abs_dividend, abs_divisor)
    result = result if same_s else -result
    
    return result