题目如下：

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT

题目大意

给定两个数字，求出它们的商，要求不能使用乘法、除法以及求余操作。

思路

题目要求不能使用乘法、除法以及求余操作。

我们知道，乘法是可以由加法来代替计算的，将除数一直累加直至超过被除数。但是仔细考虑之后发现，如果使用加法，那么时长可能会过长。假设给定1和10000000，由1加到10000000，最后的结果肯定是超时。

既然不能直接累加，那么还有什么新的方法呢？我们直到，二进制是可以表示所有数字的。那么在这题中使用二进制来逼近是较为迅速的办法。

假定商是l，那么l一定可以用二进制来表示，也即2的幂和，5=22+21。那么所需要做的也就是累加除数与2的幂次乘积，直至刚好超过被除数，然后从最大的次幂开始计算，如果当前的和加上该次幂大于被除数，那么放弃该次幂，如果加上该次幂仍然小于被除数，那么就加上该次幂。

举个例子，假设除数为3，被除数为16，那么商应该是5。我们从2的0次幂与除数的乘积也即20x3=3开始，幂次逐渐增加，直至超过被除数。可以看出，当幂次达到2时刚好超过16（3x20+3x21+3x22=21>16）。那么从3x22开始往下累加，3x22=12>16，那么记录下22=4。再看3x21，发现3x22+3x21=18>16，因此略过21=2。再看3x20，发现发现3x22+3x20=15<16，那么将20=1记录下。次幂累加结束，计算一下商，分别记录了4和1，因此结果4+1=5，此答案也即为最终的商。

算法大概的思路差不多讲完了，还需要注意的就是边界问题，只有一个边界特例需要考虑Integer.MIN_VALUE和-1。此时的结果超过了Integer所能表示的最大范围，因此需要特殊处理。其次，为了简单起见，我们将除数和被除数的符号进行记录，然后将其转换为正数进行计算，这也涉及到溢出的问题，Integer.MIN_VALUE转换为正数之后会超过32位Integer所能表示的范围，因此在代码中使用long类型进行计算防止溢出。

此算法时间复杂度是O(logn)。空间复杂度为O(logn)。Java版的代码如下，

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 int divide(int dividend, int divisor) {
    if(dividend == -2147483648 && divisor == -1){
    //防止溢出 
        return 2147483647;
    }
    ArrayList<Long> list = new ArrayList<>();
    int end = dividend > 0 ? 1 : 0;
    int sor = divisor > 0 ? 1 : 0;
    long a = Math.abs((long)dividend);
    long b = Math.abs((long)divisor);
    int ret = 0;
    list.add(b);
    long i = 1;
    //记录除数与二次幂的乘积
    while (b <= a){
        b += b;
        i += i;
        list.add(b);
    }
    long sum = 0;

    //累加
    for (int j = list.size() - 2; j >= 0; j --){
        i >>= 1;
        if (sum + list.get(j) <= a){
            ret += i;
            sum += list.get(j);
        }
    }
    //根据除数以及被除数的正负确定返回值正负
    if (end + sor == 1){
        return -ret;
    } else {
        return ret;
    }
}

提交结果如下：

提交结果
提交结果