LeetCode. 29. Divide Two Integers

[Link] https://leetcode.com/problems/divide-two-integers/

This problem asks us to divide two integers without using multiplication, division, or the remainder operator. The quotient is truncated toward zero. The divisor is guaranteed to be nonzero by the problem constraints.

Convert both operands to positive long magnitudes. Casting before taking the absolute value is essential: the positive magnitude of Integer.MIN_VALUE does not fit in an int, but it does fit in a long.

Then inspect quotient bits from 31 down to 0. At each bit, compare the remaining dividend with the divisor magnitude shifted left by that bit. If the shifted value fits, subtract it and set that quotient bit. This greedily takes the largest available power-of-two multiple at each step; after all 32 bits, the remainder is smaller than the divisor and the accumulated bits form the quotient magnitude.

Apply the sign after constructing the magnitude. The only mathematical quotient outside the int range is Integer.MIN_VALUE / -1, whose positive result is saturated to Integer.MAX_VALUE.

The loop always examines 32 bits, so the time complexity is O(32) (equivalently O(1) for fixed-width integers), with O(1) extra space.

class Solution {
    public int divide(int dividend, int divisor) {
        long dividendMagnitude = Math.abs((long) dividend);
        long divisorMagnitude = Math.abs((long) divisor);
        long quotientMagnitude = 0;

        for (int bit = 31; bit >= 0; bit--) {
            long shiftedDivisor = divisorMagnitude << bit;
            if (shiftedDivisor <= dividendMagnitude) {
                dividendMagnitude -= shiftedDivisor;
                quotientMagnitude |= 1L << bit;
            }
        }

        boolean negative = (dividend < 0) != (divisor < 0);
        long quotient = negative ? -quotientMagnitude : quotientMagnitude;
        if (quotient > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int) quotient;
    }
}