No multiply, no divide, no modulo. Division is just "how many divisors fit" — and the trick is to count them in powers of two instead of one at a time.
Compute dividend / divisor truncated toward zero, using only +, −,
comparisons, and bit shifts — no *, /, or %. The inputs span the full
32-bit range [−2³¹, 2³¹−1], which is exactly where the sharp edges live. Two subproblems:
compute the magnitude fast, and survive the overflow cases.
Division asks how many times the divisor fits into the dividend. Repeated subtraction answers it one copy at a
time — for 2,000,000,000 ÷ 1 that's two billion steps. Instead, subtract exponentially larger
chunks: divisor×1, ×2, ×4, ×8…, each built with a left shift (x<<1 = 2x, no
multiplication needed).
14 = 8 + 4 + 2 = 1110₂, so 100 ÷ 7 is really
asking: which power-of-two chunks of 7 do I need? Each quotient bit answers "do I need 2ⁱ
copies of the divisor?"
To pay 43 with denominations 5, 10, 20, 40, you hand over the 40 first, then cover the rest with smaller notes. Always spend the largest chunk that fits.
Don't tangle negatives into the arithmetic. Decide the sign once (XOR of the two signs), work in positive magnitudes, and flip at the very end.
−2³¹ has no positive twin inside int. Cast to long before taking its
size, and hard-code the single overflow result.
Set a dividend and divisor. Each step tests one power i: does divisor << i (the
current chunk) fit in the remaining dividend? Fits →
subtract it and light quotient bit i teal. Too
big → skip. The remainder shrinks and the quotient builds up in binary. Sign is handled separately,
shown up top.
Try 7 ÷ -3 (sign flip → −2),
-2147483648 ÷ -1 (the overflow clamp), or 3 ÷ 5 (nothing fits → 0). The bit strip
shows only the low powers for readability.
| i | chunk = 7 << i | remainder | Fits? | Quotient bit | quotient |
|---|---|---|---|---|---|
| 3 | 56 | 100 → 44 | yes | +8 | 8 |
| 2 | 28 | 44 → 16 | yes | +4 | 12 |
| 1 | 14 | 16 → 2 | yes | +2 | 14 |
| 0 | 7 | 2 | no | — | 14 |
Quotient 8 + 4 + 2 = 14, remainder 2 discarded (truncation toward zero). Powers 31…4
all overshoot 100 and are skipped instantly. The quotient's binary form 1110 falls straight out of
which chunks fit.
int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; // the one true overflow boolean negative = (dividend < 0) ^ (divisor < 0); // sign once, via XOR long a = Math.abs((long) dividend); // cast BEFORE abs long b = Math.abs((long) divisor); long q = 0; for (int i = 31; i >= 0; i--) { if ((b << i) <= a) { // does this chunk fit? a -= (b << i); // subtract it q += 1L << i; // set quotient bit i } } return (int) (negative ? -q : q); }
Math.abs(int) on −2³¹ overflows before the widening. Go to
long first.
int.O(32) time = O(1) for fixed-width ints, O(1) space. Subtraction and shifts are the only arithmetic — all permitted.
quotient × divisor + remainder = original dividend (in magnitude). Subtracting a
chunk divisor × 2ⁱ and adding 2ⁱ to the quotient preserves the equality exactly. When
no chunk fits, the leftover remainder is smaller than the divisor — the truncated answer.
Taking the largest fitting power each time is safe because any remaining amount can still be assembled from smaller powers of two — the same reason every integer has a binary representation. Scanning high-to-low visits each bit once, so no chunk is ever double-counted, and the quotient's binary digits emerge in order.
The true answer 2³¹ is one past Integer.MAX_VALUE. It's the only overflow; clamp
it explicitly at the top.
Math.abs(Integer.MIN_VALUE) returns itself — still negative. Cast to long before
abs so the magnitude fits.
b << 31 as an int can turn negative or wrap. Do the shift and comparison in
long.
−7 ÷ 3 = −2, not −3. The
remainder is simply dropped, which truncates toward zero — matching Java's own integer division.
Correct but O(quotient) — up to ~2 billion steps. Powers-of-two chunking drops it to 32.
Four if branches for the sign combos is noise. (dividend<0) ^ (divisor<0)
is the whole rule.
Accumulate in long, handle the clamp, then cast once at the return. Safer than fighting
overflow mid-loop.
It's binary decomposition plus greedy subtraction, not search over a sorted array. Related mindset, different mechanism.
The core move generalizes far beyond division: replace a linear pile of identical operations with an
exponential ladder of doublings, then assemble the answer from binary pieces. Subtracting the divisor
a billion times becomes subtracting divisor×2ⁱ for 32 values of i.
The unifying shape: slow repeated work → group it in powers of two → construct the answer from its binary pieces. Recognizing it turns "arithmetic without operators" from a trick into a derivation.