不用乘除做整数除法

LeetCode 29. 两数相除 (opens new window)

题目描述

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

返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去其小数部分。

提示：被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数。如果除法结果溢出，则返回 2^31 − 1。

解题思路

首先处理特殊的溢出情况，即被除数是Integer.MIN_VALUE且除数是-1，这样得到的结果会超过32位整形数能表示的最大数值。所以按题目要求进行处理。

下面是核心的除法的计算，我们可能想到的直观方法是将除数和被除数都转为绝对值的相反数再不断通过被除数减去除数同时进行计数：

public int divide(int dividend, int divisor) {
    //特殊输入处理
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

    //转变操作数的符号
    boolean isDividendPositive = dividend > 0, isDivisorPositive = divisor > 0;
    if (isDividendPositive) dividend = -dividend;
    if (isDivisorPositive) divisor = -divisor;

    //计数并根据两者符号是否相同返回结果
    int times = 0;
    while (dividend <= divisor) {
        dividend -= divisor;
        times++;
    }
    return isDividendPositive ^ isDivisorPositive ? -times : times;
}

这种方法的时间复杂度为O(dividend/divisor)，LeetCode上提交运行会超时。那么我们就要考虑如何快速缩小统计的次数，可以通过将除数和倍数同时在循环中增大一倍的方式找到最接近的倍数，这样时间复杂度就降到了O(log(dividend/divisor))

public int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

    boolean dPositive = dividend > 0, rPositive = divisor > 0;
    if (dPositive) dividend = -dividend;
    if (rPositive) divisor = -divisor;

    //总计数初始为0，因为在两数都为负数之后被除数可能大于除数，只有除的结果大于等于1时才进行循环
    int times = 0;
    while (dividend <= divisor) {
        int temp = divisor;
        //内部循环计数从1开始，因为已经能确定被除数至少大于等于除数的1倍
        int count = 1;
        while (dividend - temp <= temp) {
            temp += temp;
            count += count;
        }
        //将内层计数加到外层上
        times += count;
        //同时将被除数减去小于被除数的 最大除数的倍数 作为新的被除数
        dividend -= temp;
    }

    return dPositive ^ rPositive ? -times : times;
}