Algorithms of Math: Divide Two Integers

Problem Description

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

• -2^31 <= dividend, divisor <= 2^31 - 1
• divisor != 0

Related Topics

• Math
• Bit Manipulation

Analysis

set quotient = 0
n ∈ N
when divisor * 2 ^ n <= dividend < divisor * 2 ^ (n+1)
	quotient = quotient + (2 ^ n)
	dividend = dividend - (divisor ^ n)
when divisor <= dividend < divisor * 2
	quotient = quotient + 1
	dividend = dividend - divisor
when dividend < divisor
	return quotient

Solution

public int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; //Cornor case when -2^31 is divided by -1 will give 2^31 which doesnt exist so overflow

    boolean negative = dividend < 0 ^ divisor < 0; //Logical XOR will help in deciding if the results is negative only if any one of them is negative

    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    int quotient = 0, subQuot = 0;

    while (dividend - divisor >= 0) {
        for (subQuot = 0; dividend - (divisor << subQuot << 1) >= 0; subQuot++); 
        quotient += 1 << subQuot; //Add to the quotient
        dividend -= divisor << subQuot; //Substract from dividend to start over with the remaining
    }
    return negative ? -quotient : quotient;
}

TODO

Demonstrate dividend - (divisor ^ (subQuot + 1)) >= 0 is always right?

References

[1] Divide Two Integers - Java | 0ms | 100% faster | Obeys all conditions