Divide Two Integers

Description

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

If it is overflow, return MAX_INT.

不使用乘法、除法、取余实现两个整数相除。

根据除法的原理,基本思路是使用减法获得结果。将被除数变为被减数,除数变为减数。被减数循环减去减数直到被减数比减数小,中间减去的个数即为除法结果。

考虑被除数比除数大很多的情况,为了提升效率,被减数需要指数增加。

Solution

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func abs(n int) int {
    if n < 0 {
        return -n
    }
    return n
}

func divide(dividend int, divisor int) int {
    if divisor == 0 {
        // 被除数为0!?
        return 0
    } else if divisor == 1 {
        return dividend
    } else if divisor == -1 {
        // 边界检查
        if dividend == math.MinInt32 {
            return math.MaxInt32
        }

        return -dividend
    }

    r, n := 0, 1
    a, b := abs(dividend), abs(divisor)

    if a < b {
        return 0
    }

    // 指数逼近
    for a >= b {
        a = a - b // 减去n个b
        r += n    // 结果加上n

        b = b << 1 // 移位替代乘法
        n = n << 1
    }

    // 判断结果是否为负数
    if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
        r = -r
    }

    // 余数大于被除数,继续相除
    if a >= abs(divisor) {
        if r < 0 {
            return r + divide(a, -abs(divisor))
        } else {
            return r + divide(a, abs(divisor))
        }
    }

    return r
}