☕ DSA Java Articles

Topics › Bit Manipulation › Learn Bit Manipulation

Divide two numbers without multiplication and division

Medium TUF ID 140 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given two integers dividend and divisor. Return the integer quotient dividend / divisor truncated toward zero, without using the multiplication, division or modulo operators. Truncation toward zero means 7 / -3 is -2, not -3.

Constraints: -2^31 ≤ dividend, divisor ≤ 2^31 - 1, divisor ≠ 0. The result must fit in a 32-bit signed integer; the single case that does not, -2^31 / -1 = 2^31, is clamped to 2^31 - 1.

Example 1

dividend = 10, divisor = 3
answer = 3           // 3 * 3 = 9 <= 10 < 12

Example 2

dividend = 7, divisor = -3
answer = -2          // 7 / -3 = -2.33..., truncated toward zero

Example 3

dividend = -2147483648, divisor = -1
answer = 2147483647  // the true answer 2^31 overflows, so return INT_MAX

Every approach below follows the same frame. Work with the absolute values as longs (so that |Integer.MIN_VALUE| = 2^31 exists), compute a non-negative quotient, then attach the sign (negative exactly when the inputs have different signs) and clamp into the int range:

static int toResult(long quotient, boolean negative) {
    if (negative) quotient = -quotient;
    if (quotient > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    if (quotient < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    return (int) quotient;
}

Working on magnitudes makes truncation toward zero automatic: we compute floor(|a| / |b|) and then negate if needed, which is exactly what truncation toward zero means.

Approach 1: Brute force, repeated subtraction

Intuition. Division asks “how many times does b fit into a?”, so subtract b from a until it no longer fits and count the subtractions. It is correct and it is what the problem statement literally says, but the count can be as large as 2^31 when the divisor is 1.

Algorithm.

  1. a = |dividend|, b = |divisor| as long, quotient = 0.
  2. While a ≥ b: a -= b, quotient++.
  3. Return toResult(quotient, signsDiffer).
static int bruteForce(int dividend, int divisor) {
    long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
    long quotient = 0;
    while (a >= b) {
        a -= b;
        quotient++;
    }
    return toResult(quotient, (dividend < 0) != (divisor < 0));
}

Complexity. Time O(|quotient|), up to about 2 × 10^9 iterations, which is why the Java tests only run this method on inputs with small quotients. Space O(1).

Approach 2: Better, subtract the largest doubling that fits

Intuition. Instead of taking away one copy of b at a time, take away b, 2b, 4b, 8b, … as long as the next doubling still fits. Doubling is a left shift, so no multiplication is needed. One round removes the largest b · 2^k ≤ a and adds 2^k to the quotient; then start over on the smaller remainder. Each round at least halves what is left (if more than half remained, a larger power would have fitted), so there are O(log a) rounds, each costing O(log a) doublings.

Algorithm.

  1. a = |dividend|, b = |divisor|, quotient = 0.
  2. While a ≥ b:
    • chunk = b, count = 1.
    • While a ≥ chunk << 1: double both chunk and count.
    • a -= chunk, quotient += count.
  3. Return toResult(quotient, signsDiffer).
static int better(int dividend, int divisor) {
    long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
    long quotient = 0;
    while (a >= b) {
        long chunk = b, count = 1;
        while (a >= (chunk << 1)) {
            chunk <<= 1;
            count <<= 1;
        }
        a -= chunk;
        quotient += count;
    }
    return toResult(quotient, (dividend < 0) != (divisor < 0));
}

Dry run on 100 / 7:

round chunks tried taken count a after quotient
1 7, 14, 28, 56 (112 > 100) 56 8 44 8
2 7, 14, 28 (56 > 44) 28 4 16 12
3 7, 14 (28 > 16) 14 2 2 14
4 2 < 7, stop     2 14

Complexity. Time O(log^2 n): at most 32 rounds of at most 32 doublings. Space O(1). All intermediate values are long; chunk << 1 never exceeds 2^32 because chunk ≤ a ≤ 2^31.

Approach 3: Optimal, decide each quotient bit from the top

Intuition. The quotient is at most 2^31, so it has at most 32 bits. Decide them from the most significant downward, exactly like long division in base 2: bit i of the quotient is 1 if b · 2^i still fits in what is left of a. Because we go from high to low, after subtracting b · 2^i the remainder is less than b · 2^i, so each lower bit is considered exactly once and the whole thing is a single pass of 32 steps.

The comparison is written (a >> i) >= b rather than a >= (b << i). They mean the same thing for non-negative values (a ≥ b · 2^i if and only if floor(a / 2^i) ≥ b), but shifting a down can never overflow, whereas shifting b up by 31 could in a narrower type.

Algorithm.

  1. a = |dividend|, b = |divisor|, quotient = 0.
  2. For i from 31 down to 0: if (a >> i) ≥ b, then a -= b << i and set bit i of quotient.
  3. Return toResult(quotient, signsDiffer).
static int optimal(int dividend, int divisor) {
    long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
    long quotient = 0;
    for (int i = 31; i >= 0; i--) {
        if ((a >> i) >= b) {            // same as a >= b << i, without risking a huge shift
            a -= b << i;
            quotient |= 1L << i;
        }
    }
    return toResult(quotient, (dividend < 0) != (divisor < 0));
}

Dry run on 100 / 7 (bits 31..4 all fail because 100 >> 4 = 6 < 7):

i a » i fits? a after quotient bits
3 12 yes 100 - 56 = 44 1000
2 11 yes 44 - 28 = 16 1100
1 8 yes 16 - 14 = 2 1110
0 2 no 2 1110 = 14

Complexity. Time O(32), constant. Space O(1).

Why start at i = 31 and not 30? Because |Integer.MIN_VALUE| / 1 = 2^31 needs quotient bit 31. With long arithmetic that is just another bit; toResult then decides whether the signed result fits.

Edge cases and pitfalls