leetcode--29. Divide Two Integers

問題

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

If it is overflow, return MAX_INT.

思路

因為不能用乘除法和取餘運算，是以隻能使用位運算和加減法。比較直接的方法是用被除數一直減去除數，直到為0。這種方法的疊代次數是結果的大小，即比如結果為n，算法複雜度是O(n)。但還有比較好的方法。

看一個例子，假設87 / 4，本來應該的得到21餘3，那麼如果我們把87忽略餘數後分解一下，87 = 4 * 21 = 4 * 16 + 4 * 4 + 4 * 1，也就是87 = 4 * (1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0)，也就是把商分解為21 = 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0，是以商的二進制是10101。我們可以不斷的将4乘2的一次方，二次方，等等，直到找到最大那個次方，在這裡是2的四次方。然後，我們就從四次方到零次方，按位看商的這一位該是0還是1。即不斷将除數增大一倍，循環結束的條件是除數大于被除數。結束後就可以得到商的最高次幂。然後被除數減去增大後的除數，再開始下輪循環，找出其它次方。注意邊界條件。代碼如下：

public int divide(int dividend, int divisor) {
        int sign = ;
        if ((dividend >  && divisor < ) || (dividend <  && divisor > ))
            sign = -;
        long ldividend = Math.abs((long) dividend);
        long ldivisor = Math.abs((long) divisor);


        if (ldivisor == ) return Integer.MAX_VALUE;
        if ((ldividend == ) || (ldividend < ldivisor)) return ;

        long lans = ldivide(ldividend, ldivisor);

        int ans;
        if (lans > Integer.MAX_VALUE){ 
            ans = (sign == )? Integer.MAX_VALUE : Integer.MIN_VALUE;
        } else {
            ans = (int) (sign * lans);
        }
        return ans;
    }

   private long ldivide(long ldividend, long ldivisor) {
        if (ldividend < ldivisor) return ;

        long sum = ldivisor;
        long multiple = ;
        while ((sum+sum) <= ldividend) {
            sum += sum;
            multiple += multiple;
        }

        return multiple + ldivide(ldividend - sum, ldivisor);
}