Divide Two Integers

整数处理往往涉及溢出，一般的处理方案就是将整数转为long以后进行处理。

判断整数溢出的方式为，如果两个正数相加返回负数，则溢出。如果两个负数相加返回正数则溢出

题目描述：

https://leetcode.com/problems/divide-two-integers/description/

解题思路：

除法无法使用，可以通过加法来模拟，题目中注意的问题是如果每次只是增加divisor，速度过慢，会超时，所以通过加分模拟乘法的方式来加快速度。

代码

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
public long findMultiply(long dividend, long divisor, boolean isNegative) {

    if (dividend < divisor) {
        return 0;
    }

    long sum = divisor;
    long result = isNegative ? -1 : 1;
    while ((sum + sum) <= dividend) {
        result += result;
        sum += sum;
    }
    return result + findMultiply(dividend - sum, divisor, isNegative);
}

public int divide(int dividend, int divisor) {
    long result = 0;
    long ldividend = dividend;
    long ldivisor = divisor;

    if (ldividend > 0 && ldivisor > 0) {
        result = findMultiply(ldividend, ldivisor, false);
    } else if (ldividend < 0 && ldivisor < 0) {
        result = findMultiply(Math.abs(ldividend), Math.abs(ldivisor), false);
    } else if (ldividend > 0 && ldivisor < 0) {
        result = findMultiply(Math.abs(ldividend), Math.abs(ldivisor), true);
    } else if (ldividend < 0 && ldivisor > 0) {
        result = findMultiply(Math.abs(ldividend), Math.abs(ldivisor), true);
    }

    if (result > Integer.MAX_VALUE) {
        result = Integer.MAX_VALUE;
    }

    return (int) result;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void stringtoint() {

        assert divide(10, 5) == 2;
        assert divide(42, 5) == 8;
        assert divide(11, 5) == 2;

        assert divide(-10, -5) == 2;
        assert divide(-11, -5) == 2;
        assert divide(-9, -5) == 1;

        assert divide(9, -5) == -1;
        assert divide(10, -5) == -2;

        assert divide(10, -5) == -2;
        assert divide(1000000000, -5) == 1000000000 / -5;

        assert divide(Integer.MAX_VALUE, 1) == Integer.MAX_VALUE;
        assert divide(Integer.MIN_VALUE, 1) == Integer.MIN_VALUE;
        assert divide(Integer.MAX_VALUE, -1) == Integer.MIN_VALUE + 1;
        assert divide(Integer.MIN_VALUE, -1) == Integer.MAX_VALUE;
    }