循环减法会超时, 用倍增法, 预处理出来 2*b, 4*b, 8*b, … 2^30*b 的所有值, 然后从大到小去减

由于INT_MIN取绝对值后无法用int表示, 所以把 a 和 b 都转成负数来处理.
几个特殊情况要特判:

• INT_MIN 除以 -1 会溢出
• INT_MIN 除以 1 在累加的时候也会溢出
• 在预处理的时候, i + i 也可能溢出

class Solution {
public:
    int divide(int a, int b) {
        int sign = 1;
        if (a == INT_MIN && b == -1) return INT_MAX;
        if (a == INT_MIN && b == 1) return INT_MIN;

        if (a < 0 && b > 0 || a > 0 && b < 0) sign = -1;
        if (a > 0) a = -a;
        if (b > 0) b = -b;

        vector<int> exp;
        for (int i = b; i >= a; i = i + i) {
            exp.push_back(i);
            if (i < INT_MIN / 2) break; // 防止i+i溢出
        } 

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