In school you learned long division: look at the first few digits of the dividend, ask "how many times does the divisor fit?", write that digit of the quotient, subtract, bring down the next digit, and repeat. A computer divides in exactly the same way. The good news is that in binary the question "how many times does it fit?" has only two possible answers: 0 or 1. So every step is just one comparison and maybe one subtraction.
In the previous chapter, Booth's Multiplication Algorithm, we saw how the ALU multiplies using repeated add and shift. Division is the mirror image: repeated subtract and shift. The two classic hardware methods are restoring and non-restoring division, and both are favourite topics in university exams and GATE.
Binary division finds a quotient Q and a remainder R such that Dividend = Divisor × Q + R and 0 ≤ R < Divisor. Restoring and non-restoring division compute Q one bit per step, using a shift followed by a subtraction or an addition.
In this chapter we will do binary long division by hand, turn it into hardware with three registers, trace both algorithms step by step on the same example, understand why non-restoring division is correct, and see how signed numbers are handled. Every trace in this chapter was produced by a small simulator that was checked against ordinary integer division for all dividend/divisor pairs of up to 8 bits.
Binary Long Division by Hand
Let's divide 11 by 3. In binary, 11 = 1011 and 3 = 11.
0 0 1 1 <- quotient
_________
11 ) 1 0 1 1
1 1 < 11 -> quotient bit 0
1 0 10 < 11 -> quotient bit 0
1 0 1 101 >= 11 -> quotient bit 1
- 1 1 subtract
------
1 0
1 0 1 bring down next bit: 101 >= 11 -> quotient bit 1
- 1 1 subtract
------
1 0 remainder = 10 (binary) = 2Quotient = 0011 = 3, remainder = 10 = 2. Check: 3 × 3 + 2 = 11. Correct.
Notice the pattern in each step:
Bring down the next dividend bit (that is, shift the partial remainder left and append one bit).
Compare the partial remainder with the divisor.
If it is greater than or equal, write quotient bit 1 and subtract. Otherwise write 0 and leave it alone.
A human decides "greater or equal" by looking. Hardware has no eyes, so it decides by trying the subtraction and checking the sign of the result. That single idea is the whole of restoring division.
The Hardware: Registers A, Q and M
For dividing two n-bit unsigned numbers, the divider uses three registers:
| Register | Size | Holds |
|---|---|---|
| M | n bits (used as n + 1 with a 0 sign bit) | The divisor. It never changes. |
| Q | n bits | The dividend at the start. Quotient bits are shifted into it from the right, so at the end it holds the quotient. |
| A | n + 1 bits | The partial remainder. Starts at 0. At the end it holds the remainder. |
+---------------+
| M (divisor) |
+-------+-------+
|
v
+---------------+
| n+1 bit | add / subtract
| adder |<--- control
+-------+-------+
|
v
+--------------------+ +------------------+
| A (n+1 bits) |<--| Q (n bits) |<-- q0 (new quotient bit)
+--------------------+ +------------------+
<----------- shift left together -----------
sign bit of A tells the control unit whether the subtraction "fitted"Why does A need n + 1 bits? After a left shift, A can be as large as 2 × (divisor − 1) + 1, which may need n + 1 bits, and after a trial subtraction A may become negative, so we need a sign bit to see that. The extra bit does both jobs.
A and Q are shifted left together, as one 2n + 1 bit register: the leftmost bit of Q moves into the rightmost bit of A. This is the hardware version of "bring down the next bit". The bit position freed at the right end of Q (we write it as _ in the traces) is where the new quotient bit goes.
Restoring Division
Algorithm
Load A = 0, Q = dividend, M = divisor. Set count = n.
Shift A and Q left by one bit.
Subtract: A = A − M (done as A + 2's complement of M).
Look at the sign bit of A:
If it is 1 (A became negative, so M did not fit): set q0 = 0 and restore A by adding M back: A = A + M.
If it is 0 (M fitted): set q0 = 1 and keep the new A.
count = count − 1. If count > 0, go to step 2.
Done: Q = quotient, A = remainder.
The name comes from step 4: when the subtraction "overshoots", the old value of A is restored.
Worked Example: 11 ÷ 3 (n = 4)
Dividend Q = 1011, divisor M = 00011 (5 bits, because A is 5 bits). We will need −M in 5-bit 2's complement:
M = 00011
-M = 11100 + 1 = 11101So "A = A − M" is really "A = A + 11101", ignoring any carry out of the 5th bit.
| Step | Operation | A | Q |
|---|---|---|---|
| Init | 00000 | 1011 | |
| Step 1 | Shift A,Q left | 00001 | 011_ |
| A = A - M | 11110 | 011_ | |
| Sign of A is 1: q0 = 0, restore A = A + M | 00001 | 0110 | |
| Step 2 | Shift A,Q left | 00010 | 110_ |
| A = A - M | 11111 | 110_ | |
| Sign of A is 1: q0 = 0, restore A = A + M | 00010 | 1100 | |
| Step 3 | Shift A,Q left | 00101 | 100_ |
| A = A - M | 00010 | 100_ | |
| Sign of A is 0: q0 = 1 | 00010 | 1001 | |
| Step 4 | Shift A,Q left | 00101 | 001_ |
| A = A - M | 00010 | 001_ | |
| Sign of A is 0: q0 = 1 | 00010 | 0011 |
Result: Q = 0011 = 3 and A = 00010 = 2. That matches 11 = 3 × 3 + 2.
Look at step 1 in detail so the arithmetic is clear:
A,Q before shift : 00000 1011
shift left : 00001 011_ (leftmost bit of Q, a 1, moved into A)
A - M : 00001 + 11101 = 11110 (sign bit 1, so 1 < 3)
restore : 11110 + 00011 = 1 00001 -> keep 5 bits -> 00001
q0 = 0 : Q = 0110Compare the trace with the hand calculation: the quotient bits came out as 0, 0, 1, 1, in exactly the same order as in long division.
Cost of Restoring Division
Each of the n steps always has one subtraction. A step that gives q0 = 0 also needs a restoring addition. So:
Best case: n operations (every quotient bit is 1).
Worst case: 2n operations (every quotient bit is 0).
If 0s and 1s are equally likely, about 1.5n operations on average.
In our example the quotient 0011 has two 0s, so there were 4 subtractions + 2 additions = 6 operations. The restoring addition is the wasted work that the next method removes.
Non-Restoring Division
The Key Idea
Suppose that in some step the subtraction made A negative. Call that negative value A. Restoring division then does three things:
restore : A + M
next shift : 2(A + M) = 2A + 2M
next subtract : 2A + 2M - M = 2A + MThe net effect is simply 2A + M: shift the negative A, then add M. We do not need to restore at all. We can leave A negative and fix it in the next step by adding instead of subtracting.
If A was not negative, the next step is the usual 2A − M. So the rule becomes:
Non-restoring division: if A is ≥ 0, shift and subtract M; if A is negative, shift and add M. The quotient bit is 1 if the new A is ≥ 0, and 0 if it is negative. Only one addition or subtraction is done per step.
Algorithm
Load A = 0, Q = dividend, M = divisor. Set count = n.
If the sign of A is 0: shift A,Q left, then A = A − M.
If the sign of A is 1: shift A,Q left, then A = A + M.If the sign of the new A is 0, set q0 = 1; otherwise set q0 = 0.
count = count − 1. If count > 0, go to step 2.
Final correction: if A is negative, do A = A + M once. (Q is already correct; only the remainder needs fixing.)
Note the order in step 2: the decision add/subtract is taken from the sign of A before the shift (the shift itself can change the top bit, so look first).
Worked Example: 11 ÷ 3 Again
| Step | Operation | A | Q |
|---|---|---|---|
| Init | 00000 | 1011 | |
| Step 1 | Shift A,Q left | 00001 | 011_ |
| A = A - M (A was ≥ 0) | 11110 | 011_ | |
| Sign of A is 1: q0 = 0 | 11110 | 0110 | |
| Step 2 | Shift A,Q left | 11100 | 110_ |
| A = A + M (A was negative) | 11111 | 110_ | |
| Sign of A is 1: q0 = 0 | 11111 | 1100 | |
| Step 3 | Shift A,Q left | 11111 | 100_ |
| A = A + M (A was negative) | 00010 | 100_ | |
| Sign of A is 0: q0 = 1 | 00010 | 1001 | |
| Step 4 | Shift A,Q left | 00101 | 001_ |
| A = A - M (A was ≥ 0) | 00010 | 001_ | |
| Sign of A is 0: q0 = 1 | 00010 | 0011 |
Result: Q = 0011 = 3, A = 00010 = 2, the same as before. A ended non-negative, so no final correction was needed. The work was exactly 4 additions/subtractions instead of 6.
Compare the two traces row by row. After step 1, restoring division has A = 00001 (restored) while non-restoring keeps A = 11110 (= −2). After step 3, both arrive at the same A = 00010. The intermediate A values differ, but the quotient bits are identical in every step, because in both methods q0 = 1 exactly when the true partial remainder is ≥ M.
Worked Example with Final Correction: 8 ÷ 3
Dividend 1000, divisor M = 00011. This time the last step leaves A negative.
| Step | Operation | A | Q |
|---|---|---|---|
| Init | 00000 | 1000 | |
| Step 1 | Shift A,Q left | 00001 | 000_ |
| A = A - M (A was ≥ 0) | 11110 | 000_ | |
| Sign of A is 1: q0 = 0 | 11110 | 0000 | |
| Step 2 | Shift A,Q left | 11100 | 000_ |
| A = A + M (A was negative) | 11111 | 000_ | |
| Sign of A is 1: q0 = 0 | 11111 | 0000 | |
| Step 3 | Shift A,Q left | 11110 | 000_ |
| A = A + M (A was negative) | 00001 | 000_ | |
| Sign of A is 0: q0 = 1 | 00001 | 0001 | |
| Step 4 | Shift A,Q left | 00010 | 001_ |
| A = A - M (A was ≥ 0) | 11111 | 001_ | |
| Sign of A is 1: q0 = 0 | 11111 | 0010 | |
| Final | Sign of A is 1: correct A = A + M | 00010 | 0010 |
After the loop, A = 11111 = −1, which is not a valid remainder. Adding M once gives 00010 = 2. Final answer: Q = 0010 = 2, R = 2. Check: 3 × 2 + 2 = 8.
Why does the correction work? A negative final A means the last trial subtraction overshot, just like a step where restoring division would have restored. The quotient bit for that step is already 0, so only the remainder needs A + M.
Restoring vs Non-Restoring
| Feature | Restoring division | Non-restoring division |
|---|---|---|
| Operation per step | Always subtract; add back if result is negative | Subtract if A ≥ 0, add if A < 0; never add back inside the loop |
| Add/subtract operations for n-bit quotient | n to 2n (about 1.5n on average) | Exactly n, plus at most 1 final correction |
| Partial remainder A during the loop | Always ≥ 0 at the end of a step | Can stay negative between steps |
| Quotient bit rule | 1 if A − M ≥ 0 | 1 if new A ≥ 0 |
| Final step | None | If A < 0, A = A + M (fixes remainder only) |
| Control logic | Simple | Slightly more (choose add or subtract) |
| Speed | Slower, data-dependent time | Faster and more uniform |
8 ÷ 3 shows the difference clearly. Its quotient 0010 has three 0 bits, so restoring division needs 4 subtractions + 3 restoring additions = 7 operations. Non-restoring needs 4 + 1 final correction = 5.
Checking It in C
Here is restoring division written in C. It uses a signed variable for A so that the sign test is just A < 0, and it is compared with C's own / and % operators.
#include <stdio.h>
#include <stdint.h>
/* Restoring division of two n-bit unsigned numbers (n <= 16). */
static void restoring_div(uint32_t dividend, uint32_t divisor, int n,
uint32_t *quot, uint32_t *rem)
{
int32_t A = 0; /* partial remainder, needs a sign */
uint32_t Q = dividend; /* becomes the quotient */
uint32_t M = divisor;
for (int i = 0; i < n; i++) {
/* shift A:Q left by one bit */
A = (A << 1) | ((Q >> (n - 1)) & 1);
Q = (Q << 1) & ((1u << n) - 1);
A = A - (int32_t)M; /* trial subtraction */
if (A < 0)
A = A + (int32_t)M; /* restore, q0 = 0 */
else
Q = Q | 1; /* keep it, q0 = 1 */
}
*quot = Q;
*rem = (uint32_t)A;
}
int main(void)
{
uint32_t q, r;
int tests[][2] = { {11, 3}, {13, 4}, {8, 3}, {255, 16}, {200, 7} };
for (int t = 0; t < 5; t++) {
int n = (tests[t][0] < 16) ? 4 : 8;
restoring_div(tests[t][0], tests[t][1], n, &q, &r);
printf("%3d / %2d : quotient %2u, remainder %2u (C says %2d, %2d)\n",
tests[t][0], tests[t][1], q, r,
tests[t][0] / tests[t][1], tests[t][0] % tests[t][1]);
}
/* Signed division in C truncates toward zero */
printf("\n 7 / 2 = %2d, 7 %% 2 = %2d\n", 7 / 2, 7 % 2);
printf("-7 / 2 = %2d, -7 %% 2 = %2d\n", -7 / 2, -7 % 2);
printf(" 7 / -2 = %2d, 7 %% -2 = %2d\n", 7 / -2, 7 % -2);
printf("-7 / -2 = %2d, -7 %% -2 = %2d\n", -7 / -2, -7 % -2);
return 0;
}Output (GCC, gcc -std=c17 -Wall):
11 / 3 : quotient 3, remainder 2 (C says 3, 2)
13 / 4 : quotient 3, remainder 1 (C says 3, 1)
8 / 3 : quotient 2, remainder 2 (C says 2, 2)
255 / 16 : quotient 15, remainder 15 (C says 15, 15)
200 / 7 : quotient 28, remainder 4 (C says 28, 4)
7 / 2 = 3, 7 % 2 = 1
-7 / 2 = -3, -7 % 2 = -1
7 / -2 = -3, 7 % -2 = 1
-7 / -2 = 3, -7 % -2 = -1The last four lines lead us to signed division.
Dividing Signed Numbers
Restoring and non-restoring division, as described above, work on unsigned magnitudes. The simplest way to divide signed (2's complement) numbers is:
Remember the signs of the dividend and divisor.
Divide the magnitudes with either algorithm.
Quotient sign = sign(dividend) XOR sign(divisor). Negate the quotient if this is 1.
Remainder sign = sign of the dividend. Negate the remainder if the dividend was negative.
This rule is exactly what C (since C99) and most processors do: the quotient is truncated toward zero, and the remainder takes the dividend's sign. The output above confirms it: −7 / 2 = −3 with remainder −1, because (−3) × 2 + (−1) = −7. Some languages (Python's // and %, for example) round toward minus infinity instead and would give −4 and 1. Both satisfy Dividend = Divisor × Q + R; they differ only in which remainder they pick.
Special Cases: Division by Zero and Overflow
Divide by zero. With M = 0, the trial subtraction never goes negative, so the loop would produce Q = all 1s and a meaningless remainder. Real hardware checks for a zero divisor first and raises an exception (on x86, the divide-error exception, which the OS turns into a "floating point exception" / SIGFPE on Linux).
Quotient overflow. When a 2n-bit dividend is divided by an n-bit divisor (the usual hardware form), the quotient may not fit in n bits. It overflows exactly when the upper n bits of the dividend are ≥ the divisor. Hardware checks this before starting and signals an error.
Signed overflow. In 2's complement, the most negative number divided by −1 gives a result one too large to represent (for 8 bits, −128 / −1 = +128, which does not fit). This case is also trapped by hardware.
Common Mistakes
Using an n-bit A. A must have n + 1 bits; otherwise you cannot see the sign after the trial subtraction, and large partial remainders overflow.
Subtracting before shifting. In both algorithms the order inside a step is shift first, then add/subtract.
In non-restoring, deciding add/subtract from the shifted A. The choice depends on the sign of A before the shift.
Forgetting the final correction in non-restoring division when A ends negative. The quotient is right, but the remainder is wrong without it.
Applying the correction to Q. The final correction changes only A.
Getting −M wrong. Take the 2's complement of M in the full n + 1 bit width (for M = 00011, −M = 11101, not 1101).
Counting operations wrongly. Restoring: one subtraction per step plus one addition per quotient 0 bit. Non-restoring: one operation per step plus one correction if needed.
GATE / Interview Questions
Why does restoring division need an (n + 1)-bit A register for n-bit operands?
The extra bit acts as the sign bit, so the control unit can tell whether the trial subtraction A − M went negative. It also holds the largest shifted partial remainder, 2(M − 1) + 1, which can need n + 1 bits.
Using restoring division on 4-bit numbers, find A and Q after the second step for 13 ÷ 4.
Start A = 00000, Q = 1101, M = 00100. Step 1: shift gives A = 00001, Q = 101_; A − M = 11101 (negative), restore to 00001, q0 = 0, Q = 1010. Step 2: shift gives A = 00011, Q = 010_; A − M = 11111 (negative), restore to 00011, q0 = 0. So after step 2, A = 00011, Q = 0100. Continuing gives Q = 0011 (3) and A = 00001 (1).
How many add/subtract operations do restoring and non-restoring division need for 8 ÷ 3 with 4-bit operands?
Quotient = 0010 has three 0 bits. Restoring: 4 subtractions + 3 restores = 7. Non-restoring: 4 operations in the loop; A ends at 11111 (negative), so 1 final correction, total 5.
Why is it valid to skip the restore step in non-restoring division?
If A is negative after a subtraction, restoring would compute A + M, shift to 2A + 2M, then subtract M to get 2A + M. Non-restoring gets the same 2A + M directly by shifting the negative A and adding M. So the following partial remainder and quotient bit are the same.
In non-restoring division, what is done if the remainder is negative after the last step? Does the quotient change?
Add the divisor once: A = A + M. The quotient does not change; its last bit was already set to 0 for that step.
For n-bit operands, what is the worst-case number of add/subtract operations in each method?
Restoring: 2n (a subtraction and a restoring addition in every step). Non-restoring: n + 1 (one operation per step plus a possible final correction).
What does a C program print for -7 / 2 and -7 % 2, and why?
−3 and −1. C truncates the quotient toward zero and the remainder takes the sign of the dividend, so that (−3)(2) + (−1) = −7. Hardware gets this by dividing the magnitudes and then fixing the signs.
What happens if the divisor is 0 in the restoring algorithm without any check?
A − 0 is never negative, so every quotient bit becomes 1 and Q ends as all 1s; the result is meaningless. That is why real dividers detect a zero divisor first and raise a divide-error exception.
Summary
Binary division is long division where each quotient bit is 0 or 1. Hardware decides it by trial subtraction and checking the sign.
Registers: M = divisor, Q = dividend that turns into the quotient, A = (n + 1)-bit partial remainder that ends as the remainder. A and Q shift left together.
Restoring: shift, A = A − M; if negative, q0 = 0 and add M back, else q0 = 1. Costs n to 2n operations.
Non-restoring: if A ≥ 0 shift and subtract, else shift and add; q0 = 1 when the new A ≥ 0. Exactly n operations plus at most one final correction A = A + M.
It works because restore-then-shift-then-subtract equals shift-then-add: 2(A + M) − M = 2A + M.
Worked results: 11 ÷ 3 gives Q = 0011, R = 0010 (restoring: 6 operations, non-restoring: 4); 8 ÷ 3 gives Q = 0010, R = 0010 (7 vs 5 operations).
Signed division divides magnitudes; quotient sign = XOR of signs, remainder sign = dividend's sign (truncation toward zero, as in C).
Hardware traps divide by zero and quotient overflow.
This completes the arithmetic part of the ALU. Next, in Memory Hierarchy, we move from how the CPU computes to how it gets its data fast enough.