Leetcode 29. Divide Two Integers

https://leetcode.com/problems/divide-two-integers/

When normal operations are banned, we can use bit operation. subtraction? Too slow.

Solution:

# T:O(lgn) S:O(1)
class Solution:
    # @return an integer
    def divide(self, dividend, divisor):
        NegSign = (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0)
        a, b = abs(dividend), abs(divisor)
        ret, c = 0, 0

        while a >= b:
            c = b
            i = 0
            while a >= c:
                a -= c
                ret += (1 << i)
                i += 1
                c <<= 1

        if NegSign:
            ret = -ret
        return min(max(-2147483648, ret), 2147483647)

Run Time: 68 ms