题目描述

题目链接

https://leetcode.cn/problems/divide-two-integers/

思路

前言
由于题目规定了「只能存储位整数」，本题解的正文部分和代码中都不会使用任何位整数。诚然，使用位整数可以极大地方便我们的编码，但这是违反题目规则的。题目规定：如果除法结果溢出，那么我们需要返回作为答案。因此在编码之前，我们首先对于溢出或容易出错的边界情况进行讨论：

• 当被除数为位有符号整数的最小值时：
  • 如果除数为，那么我们可以直接返回答案；
  • 如果除数为，那么答案为，产生了溢出。此时我们需返回。

• 当除数为位有符号整数的最小值时：
  • 如果被除数同样为，那么我们可以直接返回答案；
  • 对于其余的情况，我们返回答案。

• 当被除数为时，我们可以直接返回答案。

对于一般的情况，根据除数和被除数的符号，我们需要考虑种不同的可能性。因此，为了方便编码，我们可以将被除数或者除数取相反数，使得它们符号相同。

如果我们将被除数和除数都变为正数，那么可能会导致溢出。例如当被除数为时，它的相反数就产生了溢出。因此，我们将被除数和除数都变为负数，这样就不会溢出，在编码时只需要考虑种情况就可以了。如果我们将被除数和除数的其中（恰好）一个变为了正数，那么在返回答案之前，我们需要对答案也取相反数。

二分查找思路
根据「前言」部分的讨论，我们记被除数为，除数为，并且和都是负数。我们需要找出的结果。一定是正数或。根据除法以及余数的定义，我们可以将其改成乘法的等价形式，即：

因为是正数或而和都是负数，所以（正负得负），又因为对截取其小数部分得到的值肯定是小于或等于的，所以，例如。

我们可以使用二分查找的方法得到，即找出最大的使得成立。但由于我们不能使用乘法运算符，因此我们可以使用「快速乘」算法得到的值。快速乘算法与「快速幂」类似，前者通过加法实现乘法，后者通过乘法实现幂运算。快速幂算法可以参考 50. Pow(x, n) 的题解，快速乘算法只需要在快速幂算法的基础上，将乘法运算改成加法运算即可。

细节
由于我们只能使用位整数，因此二分查找中会有很多细节。

首先，二分查找的下界为，上界为。唯一可能出现的答案为的情况已经被我们在「前言」部分进行了特殊处理，因此答案的最大值为。如果二分查找失败，那么答案一定为。

在实现「快速乘」时，我们需要使用加法运算，然而较大的也会导致加法运算溢出。例如我们要判断是否小于时（其中均为负数），可能会产生溢出，因此我们必须将判断改为是否成立。由于任意两个负数的差一定在范围内，这样就不会产生溢出。

代码实现

public int divide(int dividend, int divisor) {
    // 考虑被除数为最小值的情况
    if (dividend == Integer.MIN_VALUE) {
        if (divisor == 1) {
            return Integer.MIN_VALUE;
        }
        if (divisor == -1) {
            return Integer.MAX_VALUE;
        }
    }
    // 考虑除数为最小值的情况
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }
    // 考虑被除数为 0 的情况
    if (dividend == 0) {
        return 0;
    }
    // 将所有的正数取相反数，这样就只需要考虑一种情况
    boolean rev = false;
    if (dividend > 0) {
        dividend = -dividend;
        rev = true;
    }
    if (divisor > 0) {
        divisor = -divisor;
        rev = !rev;
    }
    // 二分查找
    int left = 1, right = Integer.MAX_VALUE, ans = 0;
    while (left <= right) {
        // 注意溢出，并且不能使用除法
        int mid = left + ((right - left) >> 1);
        if (quickAdd(divisor, mid, dividend)) {
            ans = mid;
            if (mid == Integer.MAX_VALUE) {
                break;
            }
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return rev ? -ans : ans;
}
// x 和 y 是负数，z 是正数，需要判断 z * y >= x 是否成立，即 z 个 y 相加
public boolean quickAdd(int y, int z, int x) {
    int result = 0;
    while (z != 0) {
        if ((z & 1) == 1) {
            // 需要保证 result + y >= x
            if (result + y < x) {
                return false;
            }
            result += y;
        }
        if (z != 1) {
            // 需要保证 y + y >= x
            if (y + y < x) {
                return false;
            }
            y += y;
        }
        z >>= 1;
    }
    return true;
}

复杂度分析

• 时间复杂度：，其中表示位整数的范围。二分查找的次数为，其中的每一步我们都需要使用「快速乘」算法判断是否成立。
• 空间复杂度：。