Restoring division calculator (and non-restoring)

Restoring division divides two binary numbers one quotient bit at a time: shift the remainder left, subtract the divisor, and if the result goes negative, write a 0 and add the divisor back; otherwise write a 1. Enter two numbers to see every step, or switch to the non-restoring version.

How restoring division works

It uses three registers: the divisor M, the dividend in Q, and the partial remainder A, which starts at 0 and has one extra bit so its sign shows. For an n-bit dividend it repeats n times:

• Shift A Q left by one place, so the next dividend bit moves into A.
• Subtract: A = A - M.
• If A is negative, the divisor did not fit: set Q0 = 0 and restore A = A + M.
• Otherwise it fitted: set Q0 = 1.

After n cycles, Q holds the quotient and A the remainder. It is long division in base 2, where each quotient digit can only be 0 or 1, so the only question at each step is whether the divisor fits.

Worked example: 11 ÷ 3 in 4 bits

Q = 11 = 1011, M = 3 = 0011, and A has 5 bits.

The quotient is Q = 0011 = 3 and the remainder is A = 2, and indeed 11 = 3 × 3 + 2. The calculator above checks every result it shows against ordinary division, and both algorithms are tested on every dividend and divisor from 2 to 8 bits.

Non-restoring division

Non-restoring division avoids the extra add after each failed subtraction. When A is negative it simply adds M in the next step instead of subtracting it, which has the same effect as restoring and then subtracting. Every step is one add or one subtract, and if the final A is negative, one correction A = A + M fixes the remainder. Switch the calculator to non-restoring to compare the two traces for the same numbers.

In hardware

A divider is the multiplier's mirror image: an adder-subtractor to subtract (or add back) M, A and Q joined into one shift register that shifts left, the sign bit of A to decide each quotient bit, and a counter to stop after n steps. Read the divider lesson, and compare multiplication with the Booth multiplier and the shift-and-add walkthrough.

Frequently asked

What is the restoring division algorithm?

A method for dividing unsigned binary numbers one quotient bit at a time. Each step shifts the remainder A and the dividend Q left by one place, subtracts the divisor M from A, and checks the sign: if A went negative, the quotient bit is 0 and M is added back (restored); otherwise the quotient bit is 1. After n steps Q holds the quotient and A the remainder.

What is the difference between restoring and non-restoring division?

Restoring division adds M back right away whenever a subtraction goes negative, so some steps cost two operations. Non-restoring division skips the restore: when A is negative, the next step adds M instead of subtracting it. Every step is a single add or subtract, plus at most one correction at the end.

Why does A need an extra bit?

A partial remainder can briefly go negative after a subtraction, and the algorithm decides each quotient bit from that sign. Giving A one bit more than the operands keeps the sign visible without overflow.

How many steps does restoring division take?

One step per bit of the dividend: an n-bit division takes n shift-and-subtract steps, each followed by a restore when the subtraction went negative.

How does a computer divide?

With shift and subtract, the mirror image of shift-and-add multiplication: the divider tries subtracting the divisor at each bit position, writes a 1 into the quotient when it fits and a 0 when it does not, and the leftover is the remainder.