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。

解：

public class Test {
    public static void main(String[] args) {
        System.out.println(divide(2147483647, 2));
    }

    // 二分查找：x/y的结果必然在[0,x]区间中
    public static int divide(int dividend, int divisor) {
        long res = 0;// 用long存储
        long x = dividend;// 转成用long存储
        long y = divisor;// 转成用long存储

        boolean negative = false;
        if ((x > 0 && y < 0) || (x < 0 && y > 0))
            negative = true;

        if (x < 0)
            x = -x;// 都搞成正数
        if (y < 0)
            y = -y;

        long left = 0;
        long right = x;// left 和 right分别指向[0,x]区间的两端
        while (left < right) {// 经典二分法
            long mid = (left + right + 1) >> 1;
            if (quickMulti(mid, y) <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        res = negative ? -left : left;
        if (res < Integer.MIN_VALUE || res > Integer.MAX_VALUE)
            return Integer.MAX_VALUE;
        return (int) res;
    }

    // 快乘法
    public static long quickMulti(long a, long b) {
        long res = 0;// 用long存
        while (b > 0) {
            if ((b & 1) == 1) {
                res += a;
            }
            b >>= 1;// 除以2
            a += a;// 乘以2，(b/2)*(a*2)结果不变
        }
        return res;
    }
}
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
44
45
46
47
48
49