DSA Tracker

Visualize

Divide Two Integers

A doubling ladder turns division into a handful of subtractions

time O(log n) — one shift per rung up, one comparison per rung downspace O(log n) for the ladder

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.

Details

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.

Problem:Divide Two IntegersMedium

A doubling ladder turns division into a handful of subtractions

step 1 / 14

3
[0]

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.

  • 1x=0· arr[0] = 3
Pseudocode
1FUNCTION divide(a, b)
2  n <- ABS(a)
3  d <- ABS(b)
4  ladder <- [d]
5  WHILE LAST(ladder) SHIFTED LEFT 1 <= n
6    APPEND LAST(ladder) SHIFTED LEFT 1 TO ladder
7  q <- 0
8  FOR i <- LENGTH(ladder) - 1 DOWN TO 0
9    IF ladder[i] <= n
10      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

Every step in words

Show all 14 steps
  1. 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.
  2. 3 shifted left one place is 6, still no larger than 100, so it earns a rung: subtracting this single cell would remove 2 copies of 3 at once. Each doubling costs one shift and covers twice the ground the last one did.
  3. 6 shifted left one place is 12, still no larger than 100, so it earns a rung: subtracting this single cell would remove 4 copies of 3 at once. Each doubling costs one shift and covers twice the ground the last one did.
  4. 12 shifted left one place is 24, still no larger than 100, so it earns a rung: subtracting this single cell would remove 8 copies of 3 at once. Each doubling costs one shift and covers twice the ground the last one did.
  5. 24 shifted left one place is 48, still no larger than 100, so it earns a rung: subtracting this single cell would remove 16 copies of 3 at once. Each doubling costs one shift and covers twice the ground the last one did.
  6. 48 shifted left one place is 96, still no larger than 100, so it earns a rung: subtracting this single cell would remove 32 copies of 3 at once. Each doubling costs one shift and covers twice the ground the last one did.
  7. Doubling 96 again would give 192, which already overshoots 100, so the ladder stops with 6 rungs — top rung 96, worth 32 copies of 3. Doubling reached that size in 5 shifts, which is why this is a logarithmic walk and not 100 subtractions.
  8. Rung 96 fits inside the remaining 100, and taking the largest rung that fits can never be wrong — one more copy of it would need 192, which is already too big. One subtraction clears 32 copies of 3: the remainder falls to 4 and bit 5 of the quotient turns on, making it 32.
  9. Rung 48 is bigger than the remaining 4, so a block of 16 copies of 3 would overshoot. Bit 4 of the quotient stays 0 and the walk drops to the next smaller rung, halving the amount on offer.
  10. Rung 24 is bigger than the remaining 4, so a block of 8 copies of 3 would overshoot. Bit 3 of the quotient stays 0 and the walk drops to the next smaller rung, halving the amount on offer.
  11. Rung 12 is bigger than the remaining 4, so a block of 4 copies of 3 would overshoot. Bit 2 of the quotient stays 0 and the walk drops to the next smaller rung, halving the amount on offer.
  12. Rung 6 is bigger than the remaining 4, so a block of 2 copies of 3 would overshoot. Bit 1 of the quotient stays 0 and the walk drops to the next smaller rung, halving the amount on offer.
  13. Rung 3 fits inside the remaining 4, and taking the largest rung that fits can never be wrong — one more copy of it would need 6, which is already too big. One subtraction clears 1 copies of 3: the remainder falls to 1 and bit 0 of the quotient turns on, making it 33.
  14. Every rung has been tested and what is left, 1, is smaller than 3, so no further copy can be taken. The rungs that fitted spell the quotient in binary: 33 is 100001, with 1 left over — 100 divided by 3 truncates to 33, reached in 6 comparisons instead of 33 subtractions of 3 from 100.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Divide Two Integers in the editorAll Bit Manipulation problemsBack to roadmap