package miscellaneous.math.arithmetic.div.lc029_dividetwointegers;

/**
 * Divide two integers without using multiplication, division and mod operator.
 * If it is overflow, return MAX_INT.
 */
public class Solution {

    public int divide(int dividend, int divisor) {
        if (divisor == 0) { // avoid dead loop
            return 0;
        }
        if (divisor == Integer.MIN_VALUE) { // avoid Math.abs(divisor) overflow
            return (dividend == Integer.MIN_VALUE) ? 1 : 0;
        }

        int d1 = (dividend == Integer.MIN_VALUE) ? Math.abs(dividend + 1) : Math.abs(dividend); // error: -2147483648 / -1 = 2147483647
        int d2 = Math.abs(divisor);
        int r = 0;
        while (d1 >= d2) {
            int multi = 1;
            while (d1 >= d2) {
                r = r + multi;
                d1 = d1 - d2;

                if (d2 > Integer.MAX_VALUE - d2) {
                    break;
                }

                multi = multi + multi;
                d2 = d2 + d2;
            }
            d2 = Math.abs(divisor);
        }

        if (dividend == Integer.MIN_VALUE && (d1 + 1 == divisor)) { // dividend == Integer.MIN_VALUE
            r++;
        }
        return (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) ? r : -r;
    }

}

@@ -220,25 +220,1322 @@
     
-public int divide
+// Inspired from leetcode discuss%0A    // Very handful using Long to handle overflow%0A    public int divide(int dividend, int divisor) %7B%0A        boolean isNeg = (dividend %3C 0) %5E (divisor %3C 0); // Nice trick! Logical XOR!%0A        long did = Math.abs((long) dividend);%0A        long div = Math.abs((long) divisor);%0A%0A        long count = 0;%0A        while (did %3E= div) %7B%0A            for (long i = div, j = 1; i %3C= did; i %3C%3C= 1, j %3C%3C= 1) %7B // Faster than i+=i, j+=j%0A                did -= i;%0A                count += j;%0A            %7D%0A        %7D%0A%0A        count = isNeg ? -count : count;                 // Multiplication is not allowed, otherwise use sign as int for convenience%0A        count = Math.min(count, Integer.MAX_VALUE);     // Nice! Be aware of overflow. MAX_MIN / -1.%0A        count = Math.max(count, Integer.MIN_VALUE);%0A        return (int) count;%0A    %7D%0A%0A    // Doesn't work for negative%0A    public int divide_pos(int dividend, int divisor) %7B%0A        if (dividend %3C divisor) %7B%0A            return 0;%0A        %7D%0A%0A        long count = 0;%0A        for (long i = divisor, j = 1; i %3C= dividend; i += i, j += j) %7B%0A            dividend -= i;%0A            count += j;%0A        %7D%0A        return (int) count + divide(dividend, divisor);%0A    %7D%0A%0A    // My 1AC: correct thinking but too messy not using Long%0A    public int divide1
 (int

leetcode-029 divide two integers