卖萌的弱渣

I am stupid, I am hungry.

Divide Two Integers

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

If it is overflow, return MAX_INT.

Solution

因为不能用乘除和module,一般肯定想到是用位操作 除法也可以是减法，每次减去被除数，可以得到结果 优化 每次减去被除数左移k位的数, 结果加上相应1<<k

(Divide-Two-Integers.py) download
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
        """
        max = 2147483647
        if divisor == 0:
            return max
        neg = (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0)
        a = abs(dividend)
        b = abs(divisor)

        ret = 0
        shift = 31

        while shift >= 0:
            if a >= (b<<shift):
                a -= b<<shift
                ret += 1<<shift
            shift -= 1

        if neg:
            ret = -ret
        if ret >= max:
            return max
        return ret