Question

from lintcode

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

If it is overflow, return 2147483647

Idea

Something I recapped due to solving this problem.

• Bit manipulation: x << y = x * 2 ^ y in non-overflow cases

The division is basically a loop of reducing the divisors. To accelerate the speed, we can let it grow by 2's exponents with the help of << operator. Say to find z / x, we keep calculating x * 2 ^ {i} by incrementing i. When we grow too large, i.e. when x * 2 ^ i > z, we know that x * 2 ^ (i - 1) is somewhere close to the answer. Let diff = z - x * 2 ^ (i - 1) and we start another ROUND of binary-growth division on diff / x. The correct answer would be the sum of the 1 * 2 ^ (i - 1) at each ROUND.

public class Solution {
    /**
     * @param dividend: the dividend
     * @param divisor: the divisor
     * @return: the result
     */
    public int divide(int dividend, int divisor) {

        // question requirement: If it is overflow, return `2147483647`
        if(divisor == 0)
            return Integer.MAX_VALUE;

        /**
         * Integer.MIN_VALUE is -2147483648
         * Integer.MAX_VALUE +2147483647.
         * answer +2147483648 is considered out of range.
         * So we just return the maximum as requested by question.
         */
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;

        if (dividend == 0)
            return 0;

        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;
            // x << y == x * 2 ^ y
            while(a >= (b << shift))
                shift++;

            // b * 2 ^ (shift - 1) <= b * ans == a < b * 2 ^ shift
            // want to find the ans
            a -= b << (shift - 1);
            result += 1 << (shift - 1);
        }

        return isNegative? -result:result;
    }
}