题目

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

If it is overflow, return MAX_INT.

题意

计算a/b的结果（计算机整数除法），不许用乘法，除法，取模计算。
如果越界，返回int的最大值

题解

初次做LeetCode，看见要算a/b,只许用加减，那应该是拿a不停减b了。范围在int的边界，如果朴素的做，来个1<<31和1瞬间就会爆。所以应该要优化一下。我们可以用二进制分解的想法来做。
a -= b
b += b
这样b的增长就会是指数级的，复杂度就会变成O(log(n))。然后用另一个变量c = 1，c+=c 来记录增长了多少次。然后减到a

有些细节也要注意，数字有正负，同时有边界，如果不拿long long转就会wa 。

Ｃ＋＋

class Solution {
public:
    int divide(int dividend, int divisor) {
    int ok = 0;
    long long a = dividend;
    long long b = divisor;
    long long div = divisor;
    if (a<0 && b<0) {
        a = 0LL - a;
        b = 0LL - b;
        div = 0 - div;
    }
    else if (a<0 && b >= 0) {
        ok = 1;
        a = 0LL - a;
    }
    else if (a >= 0 && b<0) {
        ok = 1;
        b = 0LL - b;
        div = 0 - div;
    }

    if (areturn 0;

    long long c = 1;
    while (a >= b) {
        a -= b;
        b += b;
        c += c;
    }
// printf("dividend = %lld divisor = %lld c = %lld\n", a, b ,c);
    if (ok == 0) {
        long long ans = c - 1 + divide(a, div);
        if (ans == 2147483648LL)
        {
            return ans - 1;
        }
        return ans;
    }
    else {
        long long ans = 0 - ((c - 1) + divide(a, div));
        return ans;
    }
}
};

看到Ｃ＋＋转来转去的太烦了。　。随手写了一个ｐｙｔｈｏｎ版的。

Python 2.7

class Solution(object):
    def divide(self, dividend, divisor):
        """
 :type dividend: int
 :type divisor: int
 :rtype: int
 """
        ok = 0
        if dividend <0 and divisor <0:
            dividend = 0 - dividend
            divisor = 0 - divisor
        elif dividend <0 and divisor >= 0:
            dividend = 0 - dividend
            ok = 1
        elif dividend >= 0 and divisor <0:
            divisor = 0 - divisor
            ok = 1
        if dividend             return 0
        b = divisor
        c = 1
        while dividend >= b:
            dividend = dividend - b
            b = b + b
            c = c + c

        if ok == 0:
            ans = c - 1 + Solution.divide(self, dividend, divisor)
            if ans == 2147483648:
                return ans - 1
            else:
                return ans
        else:
            return 0 - (c - 1 + Solution.divide(self, dividend, divisor))