Chapter 21 of 39

Division: Restoring & Non-Restoring

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) = 2

Quotient = 0011 = 3, remainder = 10 = 2. Check: 3 × 3 + 2 = 11. Correct.

Notice the pattern in each step:

  1. Bring down the next dividend bit (that is, shift the partial remainder left and append one bit).

  2. Compare the partial remainder with the divisor.

  3. 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:

RegisterSizeHolds
Mn bits (used as n + 1 with a 0 sign bit)The divisor. It never changes.
Qn bitsThe dividend at the start. Quotient bits are shifted into it from the right, so at the end it holds the quotient.
An + 1 bitsThe 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

  1. Load A = 0, Q = dividend, M = divisor. Set count = n.

  2. Shift A and Q left by one bit.

  3. Subtract: A = A − M (done as A + 2's complement of M).

  4. 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.

  5. count = count − 1. If count > 0, go to step 2.

  6. 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 = 11101

So "A = A − M" is really "A = A + 11101", ignoring any carry out of the 5th bit.

StepOperationAQ
Init000001011
Step 1Shift A,Q left00001011_
A = A - M11110011_
Sign of A is 1: q0 = 0, restore A = A + M000010110
Step 2Shift A,Q left00010110_
A = A - M11111110_
Sign of A is 1: q0 = 0, restore A = A + M000101100
Step 3Shift A,Q left00101100_
A = A - M00010100_
Sign of A is 0: q0 = 1000101001
Step 4Shift A,Q left00101001_
A = A - M00010001_
Sign of A is 0: q0 = 1000100011

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 = 0110

Compare 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 + M

The 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

  1. Load A = 0, Q = dividend, M = divisor. Set count = n.

  2. 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.

  3. If the sign of the new A is 0, set q0 = 1; otherwise set q0 = 0.

  4. count = count − 1. If count > 0, go to step 2.

  5. 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

StepOperationAQ
Init000001011
Step 1Shift A,Q left00001011_
A = A - M (A was ≥ 0)11110011_
Sign of A is 1: q0 = 0111100110
Step 2Shift A,Q left11100110_
A = A + M (A was negative)11111110_
Sign of A is 1: q0 = 0111111100
Step 3Shift A,Q left11111100_
A = A + M (A was negative)00010100_
Sign of A is 0: q0 = 1000101001
Step 4Shift A,Q left00101001_
A = A - M (A was ≥ 0)00010001_
Sign of A is 0: q0 = 1000100011

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.

StepOperationAQ
Init000001000
Step 1Shift A,Q left00001000_
A = A - M (A was ≥ 0)11110000_
Sign of A is 1: q0 = 0111100000
Step 2Shift A,Q left11100000_
A = A + M (A was negative)11111000_
Sign of A is 1: q0 = 0111110000
Step 3Shift A,Q left11110000_
A = A + M (A was negative)00001000_
Sign of A is 0: q0 = 1000010001
Step 4Shift A,Q left00010001_
A = A - M (A was ≥ 0)11111001_
Sign of A is 1: q0 = 0111110010
FinalSign of A is 1: correct A = A + M000100010

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

FeatureRestoring divisionNon-restoring division
Operation per stepAlways subtract; add back if result is negativeSubtract if A ≥ 0, add if A < 0; never add back inside the loop
Add/subtract operations for n-bit quotientn to 2n (about 1.5n on average)Exactly n, plus at most 1 final correction
Partial remainder A during the loopAlways ≥ 0 at the end of a stepCan stay negative between steps
Quotient bit rule1 if A − M ≥ 01 if new A ≥ 0
Final stepNoneIf A < 0, A = A + M (fixes remainder only)
Control logicSimpleSlightly more (choose add or subtract)
SpeedSlower, data-dependent timeFaster 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 = -1

The 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:

  1. Remember the signs of the dividend and divisor.

  2. Divide the magnitudes with either algorithm.

  3. Quotient sign = sign(dividend) XOR sign(divisor). Negate the quotient if this is 1.

  4. 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.