Pattern visualizer
Divide Two Integers Without Operator
Division is repeated subtraction, and doing it one copy at a time is far too slow when the quotient is large. The fix is to subtract in power-of-two blocks. Doubling the divisor costs a single left shift, so build a ladder — the divisor, twice it, four times it — until the next rung would overshoot the dividend. Then walk the ladder back down: whenever a rung still fits, subtract it and set the matching bit of the quotient, because a rung that fits is always worth taking (two of it would be the rung above, which did not fit). The bits switched on during that walk ARE the quotient, written most-significant first, and both phases take one step per bit rather than one step per copy. Animated on: dividend = 100, divisor = 3 — return the truncated quotient without using multiplication, division or the modulo operator. Each cell is one rung of the doubling ladder: cell i holds the divisor shifted left i times, worth 2^i copies of it..
A doubling ladder turns division into a handful of subtractions
Dividing 100 by 3 without / is repeated subtraction, but peeling off one copy of 3 at a time would take as many rounds as the answer is large. So build a ladder instead: cell 0 holds a single copy of the divisor, 3, and each later cell will hold twice the cell before it — cell i is worth 1 shifted left i times, i.e. 2^i copies of 3 bought in one subtraction.
1FUNCTION divide(a, b)2 n <- ABS(a)3 d <- ABS(b)4 ladder <- [d]5 WHILE LAST(ladder) SHIFTED LEFT 1 <= n6 APPEND LAST(ladder) SHIFTED LEFT 1 TO ladder7 q <- 08 FOR i <- LENGTH(ladder) - 1 DOWN TO 09 IF ladder[i] <= n10 n <- n - ladder[i]11 q <- q + (1 SHIFTED LEFT i)12 RETURN q TIMES SIGN(a) TIMES SIGN(b)
← / → step · space play · Home restart