刷一道算法题 —— 两数相除

题目链接：29. 两数相除

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

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。本题中，如果商 严格大于 2^31 − 1 ，则返回 2^31 − 1 ；如果商 严格小于 -2^31 ，则返回 -2^31 。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

-2^31 <= dividend, divisor <= 2^31 - 1
divisor != 0

分析下这道题，难点在于：

不能够使用乘法、除法和取余运算
不能够使用 long
需要考虑溢出问题

那么我们就一个难点一个难点来解决！

1）考虑溢出问题

其实我们只需要关注一项即可，就是 dividend = -2^31, divisor = -1 的情况，在计算机中，假设环境只能够存储32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]，那么这种情况下，如果直接取反是会溢出的，特殊情况特殊处理即可。

// special case
if(dividend == Integer.MIN_VALUE && divisor == -1) {
    return Integer.MAX_VALUE;
}

2）不能够使用 long

我们可以把两个数都转换成负数来处理，原因同上，负数范围更大，处理起来更简单。

3）运算方法限制

可以考虑使用倍增算法来实现，其实就是每次将减数和记录值加倍。

来看一个例子：

dividend = 20, divisor = 3
1. 计算 3 * 2 ^ x 的最大值（ <= 20） => 3 * 2 ^ 2 = 12 => 20 - 12 = 8 => 新的被除数 8
2. 计算 3 * 2 ^ x 的最大值（ <= 8）=> 3 * 2 ^ 1 = 6 => 8 - 6 = 2 => 新的被除数 2
3. 2 < 3 结束，ans = 2 ^ 2 + 2 ^ 1 = 6

代码实现

class Solution {
    public int divide(int dividend, int divisor) {
        // special case
        if(dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        boolean neg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);

        // to a negative number
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;

        int ans = 0;
        // 每次减去除数的 2^x 倍数
        while(dividend <= divisor) {
            int tmp = divisor, count = 1;
            while(tmp >= dividend - tmp) { // tmp * 2，倍乘法
                tmp += tmp;
                count += count;
            }

            dividend -= tmp; // 更新被除数
            ans += count; // 更新答案
        }
        return neg ? -ans : ans;
    }
}

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }

        bool neg = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);

        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;

        long ans = 0;

        while (dividend <= divisor) {
            int  tmp = divisor;
            unsigned int count = 1;  
            while (tmp >= dividend - tmp) {
                tmp += tmp;
                count += count;
            }

            dividend -= tmp;
            ans += count;
        }

        return neg ? -ans : ans;
    }
};

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # special case
        if dividend == -2147483648 and divisor == -1:
            return 2147483647

        neg = (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0)

        # to a negative number
        dividend = -dividend if dividend > 0 else dividend
        divisor = -divisor if divisor > 0 else divisor

        ans = 0
        # 每次减去除数的 2^x 倍数
        while dividend <= divisor:
            tmp, count = divisor, 1
            while tmp >= dividend - tmp:  # tmp * 2，倍乘法
                tmp += tmp
                count += count

            dividend -= tmp  # 更新被除数
            ans += count  # 更新答案
        return -ans if neg else ans

由于 Python 支持大数运算，不用考虑溢出，因此可以转换成正数来计算，更加直观。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # special case
        if dividend == -2147483648 and divisor == -1:
            return 2147483647

        neg = (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0)

        # to a negative number
        dividend = -dividend if dividend < 0 else dividend
        divisor = -divisor if divisor < 0 else divisor

        ans = 0
        # 每次减去除数的 2^x 倍数
        while dividend >= divisor:
            tmp, count = divisor, 1
            while tmp <= dividend - tmp:  # tmp * 2，倍乘法
                tmp += tmp
                count += count

            dividend -= tmp  # 更新被除数
            ans += count  # 更新答案
        return -ans if neg else ans

时间复杂度：O(logn)
空间复杂度：O(1)