Dividing Without Dividing

This is another problem from Leetcode. When I first see the problem, I tried solving it by transforming both numbers to binary equivalents. I didn’t know how to apply division on a binary number, and that fascinated me as well. However, that also included some division which was not “dividing without dividing”. Instead, I went with a subtraction approach.

The Problem

Given two integers, divide them and return the truncated quotient — without using multiplication, division, or the modulo operator.

The Naive Subtraction Approach: Full Loop

If I subtract the divisor repeatedly and count how many times it fits:

while ($dividend >= $divisor) {
    $dividend -= $divisor;
    $quotient++;
}

This works, but for something like 2147483647 / 1 (in a 32-bit system) it loops over 2 billion times. That’s O(n) — far too slow.

Faster Subtraction Approach: Exponential Doubling

Instead of subtracting one divisor at a time, I can subtract the largest possible chunk at each step. I find that chunk by doubling the divisor using left bit shifts (<<) until it no longer fits.

3 << 1 = 6    (3 × 2)
3 << 2 = 12   (3 × 4)
3 << 3 = 24   (3 × 8)

Each left shift multiplies the number by 2 because bits are binary (0 and 1).

The Code

function divide($dividend, $divisor) {
    if ($dividend == 0) {
        return 0;
    }

    // Whether the result will be negative or not
    $negative = false;
    if ($dividend < 0 && $divisor > 0) {
        $negative = true;
    }
    if ($dividend > 0 && $divisor < 0) {
        $negative = true;
    }

    $dividend = abs($dividend);
    $divisor  = abs($divisor);

    // If dividend is less than divisor, quotient will always be 0
    if ($dividend < $divisor) {
        return 0;
    }

    $quotient     = 0;
    $nextDividend = $dividend;

    while ($nextDividend >= $divisor) {
        $multiplier  = 1;
        $nextDivisor = $divisor;

        while ($nextDividend >= ($nextDivisor << 1)) {
            $multiplier  <<= 1;
            $nextDivisor <<= 1;
        }

        $quotient    += $multiplier;
        $nextDividend = $nextDividend - $nextDivisor;
    }

    if ($negative) {
        $quotient = -$quotient;
    }

    return $quotient;
}

Visual Walkthrough: 38 ÷ 3

flowchart TD
    A["Start\ndividend=38, divisor=3"] --> B["Both positive → negative=false\nquotient=0, nextDividend=38"]

    B --> D{"nextDividend 38\n≥ divisor 3?"}

    D -->|Yes - Pass 1| E["multiplier=1, nextDivisor=3"]
    E --> E1{"38 ≥ 3<<1=6?"} -->|Yes| E2["multiplier=2, nextDivisor=6"]
    E2 --> E3{"38 ≥ 6<<1=12?"} -->|Yes| E4["multiplier=4, nextDivisor=12"]
    E4 --> E5{"38 ≥ 12<<1=24?"} -->|Yes| E6["multiplier=8, nextDivisor=24"]
    E6 --> E7{"38 ≥ 24<<1=48?"} -->|No - STOP| E8["quotient = 0+8 = 8\nnextDividend = 38-24 = 14"]

    E8 --> F{"nextDividend 14\n≥ divisor 3?"}

    F -->|Yes - Pass 2| G["multiplier=1, nextDivisor=3"]
    G --> G1{"14 ≥ 3<<1=6?"} -->|Yes| G2["multiplier=2, nextDivisor=6"]
    G2 --> G3{"14 ≥ 6<<1=12?"} -->|Yes| G4["multiplier=4, nextDivisor=12"]
    G4 --> G5{"14 ≥ 12<<1=24?"} -->|No - STOP| G6["quotient = 8+4 = 12\nnextDividend = 14-12 = 2"]

    G6 --> H{"nextDividend 2\n≥ divisor 3?"}

    H -->|No - Exit| I["negative=false\nReturn 12 ✓"]

Step-by-Step State Table

Pass	nextDividend	Largest chunk found	multiplier	quotient	Remainder
1	38	24 (3 × 8)	8	8	14
2	14	12 (3 × 4)	4	12	2
3	2	2 < 3, stop	—	12	2

The remainder 2 is discarded, giving me the truncated result of 12.

Time Complexity

Instead of subtracting 3 from 38 twelve times, exponential doubling did it in 2 passes by taking the biggest possible bite each time. The number of iterations shrinks exponentially — making this O(log² n) rather than O(n).

Sign Handling

The sign is resolved upfront and applied at the end, so the core loop always works with positive numbers:

(+) ÷ (+) = +
(−) ÷ (−) = +
(+) ÷ (−) = −
(−) ÷ (+) = −

If either (but not both) inputs are negative, $negative is set to true and the quotient is flipped before returning.