利用加减法位运算实现除法器

29.题目链接-来源：力扣（LeetCode）

给定两个整数，被除数 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

思路：

题目要求不能用乘除法，也就是几乎要我们实现一个有符号整数除法器。
我们可以参考竖式计算的思路来构造这个除法器。

  • 在竖式中，我们固定被除数 dividend，依次从高到低遍历其每一位。
  • 在每一轮遍历中，我们对除数 divisor 进行左移操作，直到移位后的结果「恰好」小于等于 dividend （「恰好」的意思是，若该结果继续左移 1 位，则结果会大于 dividend）。
  • 用被除数 dividend 减去这个移位结果，得到的数字作为新的 dividend 进行下一轮循环，直到 dividend 小于 divisor 而停止。
    以上操作默认两个操作数的符号均为正数。实际运算中，我们会碰到 被除数 和 除数 符号不一致的情况，可以记录其原始符号，转换符号一致后进行运算，最后再补回符号。
    另外，本题假设环境只存储 32 位整数，为了防止结果溢出，我们可以统一把 被除数 和 除数 转换为 负数 （因为负数的表数范围比正数大 1，所以转成负数时不会溢出）， 此时，对于前述循环，其涉及到的 不等关系 全都要反向（即「小于」应变为「大于」，以此类推）。
    细节，题目要求特殊值，除法结果溢出（其实只有一种情况，就是 -2^31 / -1，没有对应的正数）要返回 2^31 - 1 ，也就是最大的正数，因此单独处理即可。
    时间复杂度：O(1)
    空间复杂度：O(1)

实现：

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
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean nagative = false;
        if (dividend > 0) {
            dividend = 0 - dividend;
            nagative = !nagative;
        }
        if (divisor > 0) {
            divisor = 0 - divisor;
            nagative = !nagative;
        }
        int quotient = 0;
        while (dividend <= divisor) {
            div d = divOneTime(dividend, divisor);
            quotient += d.quo;
            dividend -= d.prod;
        }
        
        if (nagative) {
            quotient = 0 - quotient;
        }
        return quotient;
    }
    private class div {
        int quo;
        int prod;
        public div(int q, int p) {
            quo = q;
            prod = p;
        }
    }
    
    private div divOneTime(int d, int r) {
        int dup = r << 1;
        int quo = 1;
        while (dup < 0 && d <= dup) {
            dup <<= 1;
            quo <<= 1;
            r <<= 1;
        }
        return new div(quo, r);
    }
}