Divide Two Integers

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

If it is overflow, return 2147483647

Example

Given dividend = 100 and divisor = 9, return 11.

Solution

(1) << 左移，每移动一位等于乘2，移动n 位 等于2 的 n 次方。

(2) >> 右移，每移动一位等于初2。

(3) 1 << shift 统计每次乘2 ，一共乘到多少可以等于结果值。

边界判断： 除数0，正负情况，左右移动处理前，需要把数字变成正数

class Solution(object):
    def divide(self, dividend, divisor):
        INT_MAX = 2147483647
        if divisor == 0:
            return INT_MAX
        neg = dividend > 0 and divisor < 0 or dividend < 0 and divisor > 0
        a, b = abs(dividend), abs(divisor)
        ans, shift = 0, 31
        while shift >= 0:
            if a >= b << shift:
                a -= b << shift
                ans += 1 << shift
            shift -= 1
        if neg:
            ans = - ans
        if ans > INT_MAX:
            return INT_MAX
        return ans