Divide Two Integers Explained

Problem Statement

Given two integers dividend and divisor, compute the quotient of dividend divided by divisor without using multiplication, division, or modulo operators. The result should be truncated toward zero and must fit within a 32-bit signed integer range ([-2^31, 2^31 - 1]). This problem tests your ability to implement division using repeated subtraction and bit manipulation, handling edge cases like overflow.

Example

Input: dividend = 10, divisor = 3

Output: 3

Explanation: 10 / 3 = 3.333..., truncated to 3.

Code

public 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 dvd = Math.abs((long) dividend);
        long dvs = Math.abs((long) divisor);
        int quotient = 0;
        while (dvd >= dvs) {
            long temp = dvs, multiple = 1;
            while (dvd >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            dvd -= temp;
            quotient += multiple;
        }
        return sign * quotient;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.divide(10, 3)); // 3
    }
}
            

def divide(dividend, divisor):
    MAX_INT = 2**31 - 1
    MIN_INT = -2**31
    if dividend == MIN_INT and divisor == -1:
        return MAX_INT
    sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
    dvd = abs(dividend)
    dvs = abs(divisor)
    quotient = 0
    while dvd >= dvs:
        temp = dvs
        multiple = 1
        while dvd >= (temp << 1):
            temp <<= 1
            multiple <<= 1
        dvd -= temp
        quotient += multiple
    return sign * quotient

# Example usage
print(divide(10, 3))  # 3
            

function divide(dividend, divisor) {
    const MAX_INT = 2**31 - 1;
    const MIN_INT = -2**31;
    if (dividend === MIN_INT && divisor === -1) return MAX_INT;
    const sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
    let dvd = Math.abs(dividend);
    let dvs = Math.abs(divisor);
    let quotient = 0;
    while (dvd >= dvs) {
        let temp = dvs, multiple = 1;
        while (dvd >= (temp << 1)) {
            temp <<= 1;
            multiple <<= 1;
        }
        dvd -= temp;
        quotient += multiple;
    }
    return sign * quotient;
}

// Example usage
console.log(divide(10, 3)); // 3
            

Explanation

• Handle the edge case where dividend = -2^31 and divisor = -1, which overflows to return 2^31 - 1.
• Determine the sign of the result using XOR to check if exactly one input is negative.
• Convert both dividend and divisor to positive numbers to simplify calculations.
• Repeatedly subtract the largest possible multiple of divisor (using left shifts to double it) from dividend.
• Accumulate the number of subtractions in quotient and apply the sign.

Note