Divide Two Integers

发表于 | 分类于

[Leetcode] Divide Two Integers

Divide two integers without using multiplication, division and mod operator.（在不使用乘法，除法和取余操作的情况下实现整数的除法运算。）

If it is overflow, return MAX_INT.

解题思路
最简单的方法就是用被除数一直减去除数，知道差小于除数，则循环次数等于商，最后的差为余数，这个算法时间复杂度为O(n)的。除了这个方法，还可以使用移位运算。

例如 f(32,5)=32/5=20/5+10/5+2/5=4+2+0=6

5左移2位就是20，而左移3位就是40超过了32，因此第一部分商为2*2=4.

对余数12再进行分析，左移2位是20，超过了12，则第二部分的商为2*1=2.

对余数2再进行分析，发现5不需要移位就比2大，因此第二部分商为0.

加和可得，商为6,余数为2

该题还需要注意边界值的处理，除数为0时，结果为int最大值，当被除数为最小int值且除数为-1时，结果为int最大值。

同时符号的处理也需要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 0:
            return 2147483647;
        if dividend == 0:
            return 0;
        if dividend == -2147483648 and divisor == -1:
            return ~dividend
        if (dividend < 0 and divisor > 0)or (dividend > 0 and divisor < 0):
            sign = -1
        else:
            sign = 1
        dividend = abs(dividend)
        divisor = abs(divisor)
        n = 0 #商
        while(dividend >= divisor):
            index = 1
            while (dividend > divisor << index):
                index +=1
            index -=1
            dividend -= divisor << index
            n += 2**index
        return n * sign