29. Divide Two Integers

Bit Operation

class Solution {
    public int divide(int dividend, int divisor) {
        // overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        
        // convert to long to avoid overflow
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int result = 0;

        // move from highest to lowest
        for (int i = 31; i >= 0; i--) {
            if ((a >> i) >= b) {
                a -= b << i;
                result += 1 << i;
            }
        }

        // check symbol
        if ((dividend > 0) ^ (divisor > 0)) {
            result = -result;
        }

        return result;
    }
}

Remarks:

1. TC: $O(\log N)$
2. a >> i >= b equals to a >= b << i but avoids long overflow
3. $x << i = x \times 2 ^i$

BF (timeout)

class Solution {
    public int divide(int dividend, int divisor) {
        // overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // sign
        boolean negative = (dividend < 0) ^ (divisor < 0);

        // convert to long to avoid overflow
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);

        int quotient = 0;
        while (a >= b) {
            a -= b;
            quotient++;
        }

        return negative ? -quotient : quotient;
    }
}

Remarks:

1. TC: $O(dividend / divisor)$