29. Divide Two Integers

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """

        # corner case:
        # 1.除数为0,返回无穷大
        # 2.被除数为int的负数最小值,除数为-1,返回int的正数最大值
        # 功能性,使用位运算
        # 两层while循环
        # 外层循环控制被除数,条件为被除数大于除数
        # 内层循环控制除数,条件为被除数大于除数左移shift次
        # 不断对内层循环的除数左移,直到比被除数大,记录shift,对1左移(shift-1)次,获得当前的除数倍
        # 外层循环被除数更新为 被除数 -= 除数<<(shift-1)
        
        if divisor == 0:
            return float("inf")
        if dividend == -2147483648 and divisor == -1:
            return 2147483647
        sign = 1
        if dividend < 0:
            sign *= -1
            dividend = - dividend
        if divisor < 0:
            sign *= -1
            divisor = - divisor

        res = 0
        while dividend >= divisor:
            shift = 1
            while dividend > divisor << shift:
                shift += 1
            dividend -= divisor << (shift-1)
            res += 1 << (shift-1)

        return res * sign

s = Solution()
res = s.divide(3, -1)
print(res)