【Leetcode】29.两数相除

29.两数相除

题目

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

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

 

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

 

提示：

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

方法

  • 首先考虑溢出的问题：在Java中，int型占4字节32位。int型的最大值为：Integer.MIN_VALUE= -2147483648 （-2的31次方）。最小值为：Integer.MAX_VALUE= 2147483647 （2的31次方-1）。因此，如果用-2147483648除以-1，得到的2147483648肯定会溢出，这种情况需要特殊处理。
  • 先根据除数和被除数的正负判断结果的正负。再把除数和被除数都转换为正数来计算。最后给结果加上正负号。
  • 真正的相除操作实现在div函数中，简单来说就是如下过程：60/8 = (60-32)/8 + 4 = (60-32-16)/8 + 2 + 4 = 1 + 2 + 4 = 7。具体看注释
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public int divide(int dividend, int divisor) {
    if(dividend == 0)
        return 0;
    //为了处理溢出的问题，需要特殊考虑除数为1和-1的情况
    if(divisor == 1)
        return dividend;
    if(divisor == -1){
        if(dividend == Integer.MIN_VALUE)
            return Integer.MAX_VALUE;
        return -dividend;
    }
    long a = dividend;
    long b = divisor;
    boolean isPoistive = true;
    //根据除数和被除数的正负判断结果的正负，并把除数和被除数都转换为正数
    if((a > 0 && b < 0) || (a < 0 && b > 0))
        isPoistive = false;
    a = Math.abs(a);
    b = Math.abs(b);
    long res = div(a, b);
    if(isPoistive)
        return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) res;
    return (int) -res;
}

//例如25：4
//1 * 4 < 25,于是让1翻倍
//2 * 4 < 25,于是让2翻倍
//4 * 4 < 25,于是让4翻倍
//8 * 4 < 35,于是让8翻倍
//16 * 4 > 35,可以判断结果肯定位于8和16之间
//结果为: 8 + (35 - 4*8) / 4
public int div(long a, long b){
    if(a < b)
        return 0;
    long count = 1;
    long sum = b;
    while(sum + sum <= a){
        count = count + count;
        sum = sum + sum;
    }
    return (int) (count + div(a - sum, b));
}

参考

leetcode题解区