不用乘除号实现除法（C++实现）LeetCode29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
题目来源：LeetCode29. 两数相除
链接：https://leetcode-cn.com/problems/divide-two-integers

倍增和二进制思想
举例： y x = k frac{y}{x} = k xy​=k，将 k k k转换为二进制如(11010)
再将二进制转换为十进制，即 y = 2 4 ∗ x + 2 3 ∗ x + 2 2 ∗ x y = 2^4 * x + 2^3 * x + 2^2 * x y=24∗x+23∗x+22∗x
由此得出可以预处理出 2 i ∗ x 2 ^ i * x 2i∗x，如果除数可以减去，则将该位置为1

由于题目要求只能使用int，将所有数转换为负数计算（因为负数可以映射到 0 至 2 31 0 至 2^{31} 0至231，正数只能到 2 31 − 1 2^{31} - 1 231−1）

class Solution {
public:
    int divide(int x, int y) {
        if (x == INT_MIN && y == -1) //题目特殊要求
            return INT_MAX;
        bool f = false;
        if (x > 0 && y < 0 || x < 0 && y > 0)
            f = true;
        if (x > 0) x = -x;
        if (y > 0) y = -y;
        vector a;
        a.push_back(y);
        while (y >= INT_MIN - y) { //预处理
            y += y;
            a.push_back(y);
        }
        int n = a.size();
        int ans = 0;
        while (n -- ) {
            ans += ans;
            if (x <= a[n]) {
                x -= a[n];
                ans -= 1;
            }
        }
        if (!f)
            ans = -ans;
        return ans;
    }
};