leetcode 029. 两数相除

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

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

示例 1:
输入: dividend = 10, divisor = 3
输出: 3

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

说明:

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

class Solution:
    def divide(self, dividend, divisor):
        is_positive = 1 if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) else -1
        dividend = dividend if dividend > 0 else -dividend
        divisor = divisor if divisor > 0 else -divisor
        # 除数大于被余数，商为0
        if dividend < divisor:
            return 0
        # 除数为-1或1，商为被除数
        if divisor == 1:
            return is_positive * dividend if -2 ** 31 <= is_positive * dividend <= 2 ** 31 - 1 else 2 ** 31 - 1

        quotient = 0
        # 当被除数大于除数
        while dividend >= divisor:
            tmp = divisor
            cnt = 1
            # 除数左移一位（即乘以2的1次方），直到找到最大的除数(除数*cnt)
            while tmp << 1 <= dividend:
                cnt = cnt << 1
                tmp = tmp << 1
            # 如果商为上次商值+cnt，如果不左移cnt=1
            quotient += cnt
            # 被除数减去除数，如果不左移tmp=divisor
            dividend -= tmp
        return is_positive * quotient if -2 ** 31 <= is_positive * quotient <= 2 ** 31 - 1 else 2 ** 31 - 1