Divide Two Integers

This is the most efficient approach and mimics the process of long division in binary. We can determine the bits of the quotient one by one, from the most significant bit to the least significant bit. For each bit position i (from 31 down to 0), we check if the dividend is large enough to subtract the divisor shifted by i positions (divisor << i). If it is, then the i-th bit of the quotient is 1.

• Handle the overflow case (Integer.MIN_VALUE / -1) and determine the sign.
• Convert dividend and divisor to their absolute values using long.
• Initialize a long quotient to 0.
• Iterate a loop for i from 31 down to 0 (for each bit of the potential quotient).
• Inside the loop, check if ldividend shifted right by i is greater than or equal to ldivisor. This is equivalent to checking ldividend >= (ldivisor << i) but avoids overflow when shifting ldivisor.
• If the condition is true, it means the i-th bit of the quotient is 1. Add (1L << i) to the quotient and subtract (ldivisor << i) from ldividend.
• After the loop, apply the sign to the long quotient.
• Cast the final result to int and return.

The core idea is to build the quotient bit by bit. A 32-bit integer quotient can be represented as q = b_31*2^31 + b_30*2^30 + ... + b_0*2^0, where b_i is either 0 or 1. The division equation is dividend = quotient * divisor. Substituting the binary representation of the quotient, we get dividend = (b_31*2^31 + ... + b_0*2^0) * divisor.

We can find each bit b_i starting from the most significant one, b_31. We check if dividend >= divisor * 2^i. If this condition holds, it means the i-th bit of the quotient must be 1. We then set the i-th bit in our result (quotient |= (1 << i)) and subtract divisor * 2^i from the dividend to account for this part of the quotient. We then proceed to check the next bit, i-1, with the updated, smaller dividend.

Again, we first handle signs and edge cases, using long to manage absolute values safely.

The algorithm iterates from i = 31 down to 0. In each iteration, it checks if the current ldividend is greater than or equal to ldivisor << i. A safer way to perform this check to avoid ldivisor << i from overflowing is (ldividend >> i) >= ldivisor.

If it is, we subtract ldivisor << i from ldividend and add 1L << i to our long quotient. Using 1L is important to prevent 1 << 31 from being interpreted as a negative number.

After the loop finishes, we have the absolute value of the quotient, to which we apply the sign.

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

        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;

        long ldividend = Math.abs((long) dividend);
        long ldivisor = Math.abs((long) divisor);

        long quotient = 0;
        for (int i = 31; i >= 0; i--) {
            // Check if we can subtract (ldivisor << i) from ldividend
            // This check is safer than `ldividend >= (ldivisor << i)` to avoid overflow
            if ((ldividend >> i) >= ldivisor) {
                // Add 2^i to the quotient
                quotient += (1L << i);
                // Subtract the value from the dividend
                ldividend -= (ldivisor << i);
            }
        }

        return (int) (sign * quotient);
    }
}