题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和模运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

样例

输入: dividend = 10, divisor = 3
输出: 3

输入: dividend = 7, divisor = -3
输出: -2

提示

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−23^1, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

算法

(倍增作减法) $O(\log dividend)$

1. 根据 dividend 和 divisor 的符号判断最终答案的符号。
2. 如果 dividend 或 divisor 为正数，则变为负数，因为负数的数域比正数多 1。
3. 如果每次暴力做减法去模拟除法，则时间复杂度为 $O(\frac{dividend}{divisor})$，在 divisor 较小，而 dividend 较大的情况下会超时。
4. 这里我们采用倍增的方式，首先通过自加预处理一个二元组倍增数组：(divisor, -1), (2 * divisor, -2), (4 * divisor, -4)，……， 直到 2^k * divisor 小于了 dividend，但中途注意判断越界。
5. 倒序遍历这个倍增数组，如果 dividend 小于当前项，则让 dividend 减去当前项，累计负答案，以此类推。

时间复杂度

• 倍增预处理最坏需要 $O(\log dividend)$ 的时间，遍历数组需要 $O(\log dividend)$ 的时间，故总时间复杂度为 $O(\log dividend)$。

空间复杂度

• 需要额外 $O(\log dividend)$ 的空间存储倍增数组。

C++ 代码

class Solution {
public:
    int divide(int dividend, int divisor) {
        const int HALF_INT_MIN = -1073741824;
        int x = dividend, y = divisor;

        bool sign = (x > 0) ^ (y > 0);

        if (x > 0) x = -x;
        if (y > 0) y = -y;

        vector<pair<int, int>> ys;

        for (int t1 = y, t2 = -1; t1 >= x; t1 += t1, t2 += t2) {
            ys.emplace_back(t1, t2);
            if (t1 < HALF_INT_MIN)
                break;
        }

        int ans = 0;
        for (int i = ys.size() - 1; i >= 0; i--)
            if (x <= ys[i].first) {
                x -= ys[i].first;
                ans += ys[i].second;
            }

        if (!sign) {
            if (ans == INT_MIN)
                return INT_MAX;
            ans = -ans;
        }

        return ans;
    }
};