Skip to main content

Restoring division of 31 by 13

Short answer

In restoring division, shift A,Q left, subtract divisor, restore by adding back if A is negative, and set Q0 accordingly. Dividing 31 by 13 gives quotient 2 (00010) and remainder 5 (000101).

Explain the restoring division algorithm. Use this algorithm to divide 31 (dividend) by 13 (divisor).

Restoring division 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.

31 ÷ 13

Dividend = 31 = 11111 (Q), divisor M = 13 = 001101 (n+1 = 6 bits), A = 0, n = 5.

Step  Action                    A       Q
-     Initial                   000000  11111
1     Shift left A,Q            000001  11110
      A = A - M (1 - 13 = -12)  110100  11110
      A<0: Q0=0, restore A      000001  11110
2     Shift left A,Q            000011  11100
      A = A - M (3 - 13 = -10)  110110  11100
      A<0: Q0=0, restore A      000011  11100
3     Shift left A,Q            000111  11000
      A = A - M (7 - 13 = -6)   111010  11000
      A<0: Q0=0, restore A      000111  11000
4     Shift left A,Q            001111  10000
      A = A - M (15 - 13 = 2)   000010  10000
      A>=0: Q0=1                000010  10001
5     Shift left A,Q            000101  00010
      A = A - M (5 - 13 = -8)   111000  00010
      A<0: Q0=0, restore A      000101  00010

Answer: 31 ÷ 13: quotient = 2 (00010), remainder = 5 (000101)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 5 questions →