class Solution {
public:
    int divide(int x, int y) {
        typedef long long LL;
        vector<LL> exp;//指数项
        bool is_minus = false;//负号
        if (x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;//异号相除的结果为负
        //预处理2*b^i
        LL a = abs((LL)x), b = abs((LL)y);//先直接用正数算，到时候结果加上负号就可以
        for (LL i = b; i <= a; i = i + i) exp.push_back(i);//i从除数开始，只要i还小于被除数a，就倍增i，然后将指数项插入到exp数组里

        LL res = 0;//存答案
        for (int i = exp.size() - 1; i >= 0; i -- )//从大到小开始减
            if (a >= exp[i]) {//还可以做减法
                a -= exp[i];//减去对应的数
                res += 1ll << i;//左移一位，相当于乘以2，因为是基于倍增的思想，所以能减多少次，就左移多少次即可得到结果
            }

        if (is_minus) res = -res;//负号的话就直接取反

        if (res > INT_MAX || res < INT_MIN) res = INT_MAX;//处理溢出的情况

        return res;
    }
};