Divide Two Integers

XXX. Divide Two Integers

Bit Manipulation

Mathematics

Problem Statement:

Given two integers dividend and divisor, divide the two integers without using multiplication, division, or mod operator. Return the quotient after dividing dividend by divisor. If the division result overflows, return Integer.MAX_VALUE.

Algorithm:

The algorithm avoids overflow and operates only with bitwise and arithmetic operations:

1. Handle special cases such as overflow when dividend == Integer.MIN_VALUE and divisor == -1.
2. Convert both dividend and divisor to negative numbers to avoid overflow issues when handling negative values.
3. Determine the largest bitwise doubling of the divisor that fits into the dividend. This helps compute the quotient in a bit-by-bit manner.
4. Use a loop to subtract the divisor, adjusted by bit-shifting, from the dividend until the dividend becomes smaller than the divisor.
5. Adjust the sign of the result based on the original signs of dividend and divisor.

Complexity:

Time Complexity: O(log n), where n is the value of the dividend. Each step reduces the problem size by at least half.
Space Complexity: O(1), as no extra space is used.

Java Implementation:

public class Solution {

    private static final int HALF_INT_MIN = -1073741824; // -2^30

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

        if (dividend == Integer.MIN_VALUE && divisor == 1) 
            return Integer.MIN_VALUE;

        // Convert both numbers to negatives for easier handling
        int negatives = 2;
        if (dividend > 0) {
            negatives--;
            dividend = -dividend;
        }
        if (divisor > 0) {
            negatives--;
            divisor = -divisor;
        }

        // Find the largest bit shift of divisor that fits into dividend
        int maxBit = 0;
        while (divisor >= HALF_INT_MIN && divisor + divisor >= dividend) {
            maxBit++;
            divisor += divisor;
        }

        int quotient = 0;
        // Calculate the quotient using bit manipulation
        for (int bit = maxBit; bit >= 0; bit--) {
            if (divisor >= dividend) {
                quotient -= (1 << bit);
                dividend -= divisor;
            }
            divisor = (divisor + 1) >> 1; // Adjust divisor for the next bit
        }

        // Adjust sign of the quotient
        if (negatives != 1) 
            quotient = -quotient;

        return quotient;
    }
}