参考题解1

贪心：
在每次做减法时，我们需要找到小于被除数的最大的除数的倍数。每次用被除数减去该最大的倍数，同时答案加上该倍数值，直到被除数小于除数。

class Solution {
public:
    int divide(int x, int y) {
        typedef long long LL;
        vector<LL> exp; //用来存  2^i * y的
        bool minus = false;
        if (x > 0 && y < 0 || x < 0 && y > 0) minus = true;
        LL a = abs((LL)x), b = abs((LL)y); // 这里必须强制类型转换 否则 <-INT_MIN的数, 取绝对值会溢出

        for (LL i = b; i <= a; i = i + i) exp.push_back(i); //这里LL i = b， 不是int i = b！！！！

        LL res = 0;
        for (int i = exp.size() - 1; i >= 0; i --) {
            if (a >= exp[i]) {
                a -= exp[i];
                res += 1ll << i;
            }
        }

        if (minus) res = -res;
        if (res > INT_MAX || res < INT_MIN) return INT_MAX; //本题中，如果除法结果溢出，则返回 2^31 − 1。

        return res;
    }
};