两数相除

问题陈述

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

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

问题解决

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
/**
     * 我们可以以100/3为例
     *
     * 2^n是1，2，4，8...2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，
     *
     * 当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3
     *
     * 所以一共是减去了33个3，所以商就是33
     *
     * 这其中得处理一些特殊的数，比如divisor是不能为0的，Integer.MIN_VALUE和Integer.MAX_VALUE
     *
     */
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异
        //全部取正数计算，最后加上正负。
        long t = Math.abs((long) dividend);//t 被除数
        long d= Math.abs((long) divisor);//d 除数
        int result = 0;
        for (int i=31; i>=0;i--) {
            if ((t>>i)>=d) {//(t除2的i次方是否大于等于除数)
                result+=1<<i;//加上2^i
                t-=d<<i;//此处相当于t=t-(d*2^i)
            }
        }
        return negative ? -result : result;//符号相异取反
    }
//左移。<< 相当于乘2   例：a=a<<2等同于a=a*2.
//右移。>> 相当于除2