29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

AC代码：

class Solution(object):
    def divide(self, dividend, divisor):
        if divisor == 0: return -1
        is_positive, a, b = (dividend >= 0) ^ (divisor < 0), abs(dividend), abs(divisor)
        ret_num = 0
        while b <= a:
            c, d = b, 1
            while c <= a:
                ret_num += d; a -= c
                c, d = c << 1, d << 1
        return min(ret_num, 2147483647) if is_positive else max(-ret_num, -2147483648)

第一眼看，这题很简单嘛，不允许用除法和乘法，直接用被除数每次减一个除数，看一共能减多少个不就可以了。

本题Medium难度，用脚趾头想想也不可能这么简单。其实原题已经给出提示了，比如用MAX_INT除以1，要循环MAX_INT次，肯定是会超时的。

所以用类似于二分查找的思想，每次扣减的数翻倍，这样能快速迭代到达被除数的值。

注意到达临界点后需要继续重置因子继续迭代，所以是个二重循环。