Divide Two Integers

Description

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

If it is overflow, return MAX_INT.

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

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

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

Solution

 1func abs(n int) int {
 2    if n < 0 {
 3        return -n
 4    }
 5    return n
 6}
 7
 8func divide(dividend int, divisor int) int {
 9    if divisor == 0 {
10        // 被除数为0!?
11        return 0
12    } else if divisor == 1 {
13        return dividend
14    } else if divisor == -1 {
15        // 边界检查
16        if dividend == math.MinInt32 {
17            return math.MaxInt32
18        }
19
20        return -dividend
21    }
22
23    r, n := 0, 1
24    a, b := abs(dividend), abs(divisor)
25
26    if a < b {
27        return 0
28    }
29
30    // 指数逼近
31    for a >= b {
32        a = a - b // 减去n个b
33        r += n    // 结果加上n
34
35        b = b << 1 // 移位替代乘法
36        n = n << 1
37    }
38
39    // 判断结果是否为负数
40    if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
41        r = -r
42    }
43
44    // 余数大于被除数,继续相除
45    if a >= abs(divisor) {
46        if r < 0 {
47            return r + divide(a, -abs(divisor))
48        } else {
49            return r + divide(a, abs(divisor))
50        }
51    }
52
53    return r
54}