Leetcode 29 Divide Two Integer

2017-03-13

Leetcode 算法题 29
题名：Divide Two Integers
https://leetcode.com/problems/divide-two-integers/#/description

题目描述：不使用乘除模运算来求两个整数的除法，越界的情况返回MAX_INT
Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解题思路：对于不能使用乘除元算来计算整数的除法问题，很显然有一个最容易想到的方法就是将被除数一直减去除数直到被除数小于0,计算相减的次数，但是这样的话复杂度就是Ｏ(n),复杂度太高。因此还可以使用简化的方法，整数int的最大值是2**31-1,可以使用位运算，将被除数减去一个较大的整数，保存减去的值。

Python代码如下

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        maxint = 2**31-1
        size = 31
        sum = 0

        if divisor == 0:
            return maxint


        if (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0):
            sign = -1
        else:
            sign = 1

        dividend, divisor = abs(dividend), abs(divisor)

        while size >= 0:
            if dividend >= divisor<<size:
                sum += 1<<size
                dividend -= divisor<<size
            size -= 1

        ret = sign * sum
        if ret>maxint or ret<-1*maxint-1:
            return maxint
        else:
            return ret