[LeetCode]--29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

以前我记得做过乘法变加法吧，这个有点像除法变减法，用位运算，二进制嘛，左移一位相当于乘以二。

一个有趣的是 Math.abs(-2147483648) 结果还是 -2147483648. 在进行该运算前，要将其转化为long类型。

第一种方法，采取两个while循环来确定需要减多少，c简单理解其实就是商。这个方法显得有些累赘，不过AC了。

public int divide(int dividend, int divisor) {
        if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        int sign = 1;
        if (dividend < 0)
            sign = -sign;
        if (divisor < 0)
            sign = -sign;
        long temp1 = Math.abs((long) dividend);
        long temp2 = Math.abs((long) divisor);
        long c = 1;
        while (temp1 > temp2) {
            temp2 = temp2 << 1;
            c = c << 1;
        }
        int res = 0;
        while (temp1 >= Math.abs((long) divisor)) {
            while (temp1 >= temp2) {
                temp1 -= temp2;
                res += c;
            }
            temp2 = temp2 >> 1;
            c = c >> 1;
        }
        if (sign > 0)
            return res;
        else
            return -res;
    }

第二种方法，其实跟第一种方法是一样的原理，就是代码简化了一点点。

public int divide(int dividend, int divisor) {
        if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        int res = 0, sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
        long dvd = Math.abs((long) dividend), dvs = Math.abs((long) divisor);
        while (dvd >= dvs) {
            long mul = 1, temp = dvs;
            while (dvd >= temp << 1) {
                temp <<= 1;
                mul <<= 1;
            }
            dvd -= temp;
            res += mul;
        }
        return res * sign;
    }