剑指 Offer II 001. 整数除法

难度简单192收藏分享切换为英文接收动态反馈

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

注意：

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

示例 3：

输入：a = 0, b = 1
输出：0

示例 4：

输入：a = 1, b = 1
输出：1

提示:

• -231 <= a, b <= 231 - 1
• b != 0

题解

使用减法代替除法

code1

// 因为将 -2147483648 转成正数会越界，但是将 2147483647 转成负数，则不会
// 所以，我们将 a 和 b 都转成负数
// 时间复杂度：O(n)，n 是最大值 2147483647 --> 10^10 --> 超时
public int divide2(int a, int b) {
    // 32 位最大值：2^31 - 1 = 2147483647
    // 32 位最小值：-2^31 = -2147483648
    // -2147483648 / (-1) = 2147483648 > 2147483647 越界了
    if (a == Integer.MIN_VALUE && b == -1)
        return Integer.MAX_VALUE;
    int sign = (a > 0) ^ (b > 0) ? -1 : 1;
    // 环境只支持存储 32 位整数
    if (a > 0) a = -a;
    if (b > 0) b = -b;
    int res = 0;
    while (a <= b) {
        a -= b;
        res++;
    }
    // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
    return sign == 1 ? res : -res;
}

首先考虑特殊情况，当-2147483648 / (-1) = 2147483648 > 2147483647 就会越界，因此做特殊判断；

全部转换为负数运算，置res为0，每减一次就++；

其中^ 为异或运算，用于判断a、b的符号；