Divide Two Integers 414

Question

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

If it is overflow, return 2147483647

Example

Given dividend = 100 and divisor = 9, return 11.

Solution

这道题要求不用乘，除和模操作完成除法操作。

1. 基本思想是不断地减掉除数，直到为0为止。但是这样会太慢。

2. 我们可以使用2分法来加速这个过程。不断对除数 * 2，直到它恰好比被除数小（即再乘2就会比被除数大）为止。加倍的同时，也记录下cnt，将被除数减掉加倍后的值，并且结果+cnt。因为是2倍地加大，所以速度会很快，指数级的速度。

但是因为不能用乘除操作，因此只能用位运算的方法，即左移1位 ＝ * 2。

首先讨论一些边界情况：

1. 如果除数为0，则被除数为正时，结果为正无穷，否则为负无穷

2. 如果被除数为0，则返回0

3. 如果被除数为正无穷除数为1或者被除数为负无穷除数为－1，则返回正无穷

4. 如果被除数为正无穷除数为－1或者被除数为负无穷除数为1，则返回负无穷

记录一下结果的符号（即除数和被除数同号为＋，异号为负），然后对除数和被除数取绝对值。注意：因为int最大2147483647,最小-2147483648，最小值直接abs后会溢出，所以要先讲被除数与除数转换为long之后再取绝对值，以防出现溢出的情况。

每次将b左移一定的位数，比如i位，使得b恰好小于a（即b< a），此时相当于b 2^i，然后再对剩下的数（即a-b 2^i）做刚才的操作，直到剩下的数小于b为止。看b总共乘以了多少power of 2，将其加和即可。

代码如下：

public class Solution {
    /**
     * @param dividend the dividend
     * @param divisor the divisor
     * @return the result
     */
    public int divide(int dividend, int divisor) {
        // Write your code here
        if(divisor == 0){
            return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }

        if(dividend == 0){
            return 0;
        }

        if((dividend == Integer.MAX_VALUE && divisor == 1) || (dividend == Integer.MIN_VALUE && divisor == -1)){
            return Integer.MAX_VALUE;
        }

        if((dividend == Integer.MIN_VALUE && divisor == 1) || (dividend == Integer.MAX_VALUE && divisor == -1)){
            return Integer.MIN_VALUE;
        }

        boolean signal = ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))? true : false;

        //在这里必须先取long再abs，否则int的最小值abs后也是原值(因为int最大2147483647,最小-2147483648，最小值abs后会溢出)
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        int result = 0;
        while(a >= b){
            int shift = 0;
            while(a >= (b << shift)){
                shift++;
            }
            shift--;
            a -= b << shift;
            result += 1 << shift;
        }

        return signal? result : -result;
    }
}