剑指 Offer II 001. 整数除法

Posted on | In
Words count in article: 306 | Reading time ≈ 1

题目

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

注意：

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

示例1：

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

示例2：

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

示例3：

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

示例4：

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

提示：

  • -2^31 <= a, b <= 2^31 - 1
  • b != 0

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        if (a > 0) {
            a = -a;
        }
        if (b > 0) {
            b = -b;
        }
        int res = 0;
        while (a <= b) {
            int value = b;
            int k = 1;
            while (value >= 0xc0000000 && a <= value + value) {
                value += value;
                if (k > Integer.MAX_VALUE / 2) {
                    return Integer.MIN_VALUE;
                }
                k += k;
            }
            a -= value;
            res += k;
        }
        return sign == 1 ? res : -res;
    }
0%