01 整数除法

题目

输入2个 int 型整数，它们进行除法计算并返回商，要求不得使用乘号'*'、除号'/'及求余符号'%'。当发生溢出时，返回最大的整数值。假设除数不为0。例如，输入 15 和 2，输出 15/2 的结果，即 7。

分析

这个题目限制我们不能使用乘号和除号进行运算。一个直观的解法是基于减法实现除法。例如，为了求得15/2的商，可以不断地从15里减去2，当减去7个2之后余数是1，此时不能再减去更多的2，因此15/2的商是7。我们可以用一个循环实现这个过程。

public static int method1(int dividend, int divisor){
    int a = dividend;
    int b = divisor;
    if (dividend < 0) {
        a = -dividend;
    }
    if (divisor < 0 ) {
        b = -divisor;
    }
    int result = 0;
    while (a - b >= 0) {
        result += 1;
        a -= b;
    }
    if ((dividend < 0 && divisor > 0 )
            || (divisor < 0 && dividend > 0 )) {
        result = -result;
    }

    return result;
}

但这个直观的解法存在一个问题。当被除数很大但除数很小时，减法操作执行的次数会很多。例如，求 $(2^31 - 1)/1$，减1的操作将执行$(2^32 - 1)/1$次，需要很长的时间。如果被除数是 n，那么这种解法的时间复杂度为O（n）。我们需要对这种解法进行优化。

可以将上述解法稍作调整，当被除数大于除数时，继续比较判断被除数是否大于除数的 2 倍，如果是，则继续判断被除数是否大于除数的 4 倍，8 倍等。如果被除数最多大于除数的 $2^k$ 倍，那么将被除数减去除数的 $2^k$ 倍，然后将剩余的被除数重复前面的步骤。由于每次将除数翻倍，因此优化后的时间复杂度是 O(logn)。

下面以15/2为例讨论计算的过程。15大于2，也大于2的2倍（即4），还大于2的4倍（即8），但小于2的8倍（即16）。于是先将15减去8，还剩余7。由于减去的是除数的4倍，减去这部分对应的商是4。接下来对剩余的7和除数2进行比较，7大于2，大于2的2倍（即4），但小于2的4倍（即8），于是将7减去4，还剩余3。这一次减去的是除数2的2倍，对应的商是2。然后对剩余的3和除数2进行比较，3大于2，但小于2的2倍（即4），于是将3减去2，还剩余1。这一次减去的是除数的1倍，对应的商是1。最后剩余的数字是1，比除数小，不能再减去除数了。于是15/2的商是4+2+1，即7。

上述讨论假设被除数和除数都是正整数。如果有负数则可以将它们先转换成正数，计算正数的除法之后再根据需要调整商的正负号。例如，如果计算-15/2，则可以先计算15/2，得到的商是7。由于被除数和除数中有一个负数，因此商应该是负数，于是商应该是-7。

将负数转换成正数存在一个小问题。对于32位的整数而言，最小的整数是-231，最大的整数是231-1。因此，如果将-231转换为正数则会导致溢出。由于将任意正数转换为负数都不会溢出，因此可以先将正数都转换成负数，用前面优化之后的减法计算两个负数的除法，然后根据需要调整商的正负号。

最后讨论可能的溢出。由于是整数的除法并且除数不等于0，因此商的绝对值一定小于或等于被除数的绝对值。因此，int型整数的除法只有一种情况会导致溢出，即 $(2^31/(-1)$ 。这是因为最大的正数为$(2^31-1)$，$2^31$超出了正数的范围。在全面地分析了使用减法实现除法的细节之后，我们可以开始编写代码。参考代码如下所示：

代码

/**
 * 作者: zhoujun134
 * 时间: 2023/12/2 23:33
 */
public class Test01 {
    public static void main(String[] args) {
        System.out.println(divide(12, 2));
    }

    /**
     * 0x80000000 is -2<sup>31</sup>
     */
    public static int divide(int dividend, int divisor) {
        if (dividend == 0x80000000 && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        int negative = 2;
        if (dividend > 0) {
            negative--;
            dividend = -dividend;
        }
        if (divisor > 0) {
            negative--;
            divisor = -divisor;
        }
        int result = divideCore(dividend, divisor);
        return negative == 1 ? -result : result;
    }

    /**
     * 0xc0000000 is -2<sup>30</sup>.
     */
    private static int divideCore(int dividend, int divisor) {
        int result = 0;
        while (dividend <= divisor) {
            int value = divisor;
            int quotient = 1;
            while (value >= 0xc0000000 && dividend <= value + value) {
                quotient += quotient;
                value += value;
            }
            result += quotient;
            dividend -= value;
        }
        return result;
    }
}