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

If it is overflow, return MAX_INT.

不用乘法，除法，求模运算来实现两个整数相除。正是之前提到的位运算。

思路：

首先，我们知道任何一个整数都可以表示成以2的幂为底的一组基的线性组合，即num = flag0 2^0 + flag1 2^1 + flag2 2^2 + … + flagn 2^n 其中，flag0, flag1, flag2, …, flagn 取值为0或1。

因此，如果令：dividend / divisor = num

dividend = divisor num = divisor (flag0 2^0 + flag1 2^1 + flag2 2^2 + … + flagn 2^n)

对于除数，使用移位操作<<使其每次翻倍，从而减少减法求商的次数。以下是步骤：

1.当被除数大于除数时，对除数乘2（代码中使用变量temp用于记录每次除数乘2），直到temp大于被除数为止。记录移位操作的次数i。
2.如果被除数大于除数，那么被除数减去temp。直到被除数小于除数。保存结果。
3.判断正负，输出结果res。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def divide(dividend, divisor):
        sign = (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0)  
        a, b = abs(dividend), abs(divisor)  
        res, temp = 0, 0  
        # 被除数大于除数
        while a >= b:  
            temp = b  
            i = 0  
            while a >= temp:  
                a -= temp  
                res += (1<<i)  
                i += 1  
                temp <<= 1  

        if sign:  
            res = -res  
        return min(max(-2147483648, res), 2147483647)

备注：int：-2147483648~2147483647 (4Bytes)