📃 题目描述

题目链接：

• 剑指 Offer II 001. 整数除法 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 29. 两数相除 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

🔔 解题思路

暴力

最简单的，不断循环做减法

另外，，int型整数的除法只有一种情况会导致溢出，即 （）（），而最大的正数只有

class Solution {
    public int divide(int a, int b) {
        // 边界条件
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        // 符号
        int sign = 1;
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
            sign = -1;
        }
        
        int res = 0;

        // 全都变成负数做运算，因为最小值的绝对值比最大值的绝对值要大 1
        a = (a > 0) ? -a : a;
        b = (b > 0) ? -b : b;
        

        while (a <= b) {
            a -= b;
            res ++;
        }

        return sign == 1 ? res : -res;
    }
}

时间复杂度 O(N)

优化

可以将上述解法稍做调整。当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是，则继续判断被除数是否大于除数的4倍、8倍等。如果被除数最多大于除数的 2^k 倍，那么将被除数减去除数的 2^k 倍，然后将剩余的被除数重复前面的步骤

由于每次将除数翻倍，因此优化后的时间复杂度是

下面以 15/2 为例讨论计算的过程

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

class Solution {
    public int divide(int a, int b) {
        // 边界条件
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        // 符号
        int sign = 1;
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
            sign = -1;
        }
        
        int res = 0;

        // 全都变成负数做运算，因为最小值的绝对值比最大值的绝对值要大 1
        a = (a > 0) ? -a : a;
        b = (b > 0) ? -b : b;
        
        while (a <= b) {
            // 除数每次翻倍
            int divisor = b;
            // 当前除数的倍数
            int quotient = 1;

            // 代码优化：如果 divisor 已经大于最小值的一半的话，那么退出本次 while 循环
            // 因为这个时候 divisor * 2 肯定会小于最小值，超过了题目给的范围
            while (divisor > Integer.MIN_VALUE >> 1 && a <= divisor + divisor) {
                // 除数翻倍
                quotient += quotient; 
                divisor += divisor;
            }

            res += quotient;
            a -= divisor;
        }

        return sign == 1 ? res : -res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：