Divide Two Integers(lintcode 414)

Description

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.

Interface

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
    }
}

Solution

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) {
            if (dividend >= 0) {
                return Integer.MAX_VALUE;
            } else {
                return Integer.MIN_VALUE;
            }
        }

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

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

        boolean isNegative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        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) >= 0) {
                shift++;
            }
            a -= b << shift - 1;
            result += 1 << shift - 1;
        }

        return isNegative ? -result : result;
    }
}