29.md

Divide Two Integers

Description

link

---

Solution

首先是除法是基于减法的，那么这题第一时间想到的就是不停减去divisor，但是这样会TLE，所以通过bit操作来让divisor每次都左移一位，如果能减去，那么同样能被原始divisor除尽

---

Code

O(logn) ~ O(log^2(n))

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = 1 if dividend > 0 and divisor > 0 or dividend < 0 and divisor < 0 else -1
        dividend, divisor = abs(dividend), abs(divisor)
        
        res = 0
        while dividend >= divisor:
            tmp, i = divisor, 1
            while dividend >= tmp:
                dividend -= tmp
                res += i
                tmp <<= 1
                i <<= 1
            
        res = res * sign
        return res if -2**31 <= res <= 2**31 - 1 else 2**31 - 1