Divide Two Integers

题目描述

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

If it is overflow, return MAX_INT.

解决方法

方法一

不断地减去被除数，直到小于被除数，可以得到结果，但是会超时

方法二，类似二分法

• 左移是乘以2， 我们可以想到不断地将divisor乘以2的结果保存为变量a，直到a大于dividend
• 将dividend减去a >> 1还小于dividend的值，并且记录下这里将divisor乘以了多少倍， dividend = divident - a
• 再继续loop, 直到 divident < divisor结束

Solution

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = 1
        if (dividend < 0) ^ (divisor < 0):
            sign = -1

        if dividend == 0:
            return 0
        if divisor == 0:
            return

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

        result = 0

        while dividend >= divisor:
            i = 0
            a = divisor 
            while a <= dividend:
                a = a << 1
                i += 1
            result += (1 << (i-1))
            dividend -= (a >> 1)

        result = result * sign
        if result > 2147483647:
            return 2147483647
        else:
            return result

注意点

• 决定正负的时候，dividend和divisor有且只有一个为负才为负数，可以用^
• overflow的range
• 对于中间记录i的时候，因为我是从i=0看来是，并且i表示乘以了几个2， 所以result += (1 << (i-1))

Reference

• 博客园