Divide Two Integers

Question

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

If it is overflow, return 2147483647

Thoughts

因为不能用乘除和module,一般肯定想到是用位操作 除法也可以是减法，每次减去被除数，可以得到结果

优化 每次减去被除数左移k位的数，被除数乘以2的k+1次方>dividend, 乘以2的k次方<= dividend

Solution

class Solution:
    # @param {int} dividend the dividend
    # @param {int} divisor the divisor
    # @return {int} the result
    def divide(self, dividend, divisor):
        # Write your code here
        if (dividend < 0) ^ (divisor < 0):
            sign = -1
        else:
            sign = 1
        #要都convert成正数来计算
        dividend = abs(dividend)
        divisor = abs(divisor)    

        if divisor == 0:
            return None
        result = 0
        while dividend >= divisor:
            i = 1
            tmp = divisor
            while dividend >= tmp:
                tmp = tmp << 1
                i += 1
            #这里左移几位的关系要处理好，可以用一个例子试一下
            result += (1 << (i - 2))
            dividend -= (divisor << (i - 2))

        #overflow的处理，对于python不用
        result *= sign
        if result > 2147483647:
            result = 2147483647

        return result