Division operation and hardware

Division finds a quotient Q and remainder R with dividend = divisor × Q + R. In hardware it is done by repeated shift and subtract (restoring or non-restoring method), one quotient bit per cycle.

Hardware implementation

   +-----------+                  +---------+
   | Divisor M |                  | Control |
   +-----+-----+                  |  & SC   |
         | (n+1 bits)             +----+----+
         v                             |
   +------------------------+          |
   | (n+1)-bit adder/subtr. |<---------+
   +-----------+------------+
               | result / sign
               v
   +-----------------+   +-------------------+
   |  A (remainder)  |<->|  Q (dividend ->   |
   |  n+1 bits       |   |   quotient) n bits|
   +-----------------+   +-------------------+
        <---- shift left as one register ---->

• A (n+1 bits) starts at 0 and finally holds the remainder.
• Q (n bits) starts with the dividend and finally holds the quotient; the new quotient bit enters at Q0 as Q shifts left.
• M holds the divisor; the extra bit in A and the adder keep the sign of A − M.
• The adder/subtractor does A − M (and A + M for restoring or non-restoring correction).
• The sequence counter SC counts n steps.

Restoring algorithm

1. Load A = 0, Q = dividend, M = divisor, SC = n.
2. Shift A and Q left by one bit (the MSB of Q goes into the LSB of A).
3. A = A − M.
4. If A < 0 (sign bit 1): set Q0 = 0 and restore A by adding M back (A = A + M). If A ≥ 0: set Q0 = 1.
5. SC = SC − 1. If SC ≠ 0 repeat from step 2.
6. At the end Q holds the quotient and A holds the remainder.

Example: 7 ÷ 3

Step  Action                  A     Q
-     Initial                 0000  111
1     Shift left A,Q          0001  110
      A = A - M (1 - 3 = -2)  1110  110
      A<0: Q0=0, restore A    0001  110
2     Shift left A,Q          0011  100
      A = A - M (3 - 3 = 0)   0000  100
      A>=0: Q0=1              0000  101
3     Shift left A,Q          0001  010
      A = A - M (1 - 3 = -2)  1110  010
      A<0: Q0=0, restore A    0001  010

Answer: 7 ÷ 3: quotient = 2 (010), remainder = 1 (0001)

The non-restoring method saves the restoring addition: it uses A + M in the next cycle when A is negative, so each cycle needs only one add or subtract.