Restoring Division

Steps

  1. Write Down Initialize line (A is All 0s, Dividend in Q)
  2. Shift A_Q Left one bit. (Dropping leftmost A, and Appending a zero to Q)
  3. If A > D, calculate A-D and store it in A. Then replace right most bit of Q with a 1.
  4. Repeat Steps 2 and 3 until you have ienumorated through the same amount of times as there are bits of Q
  5. A is the Remainder, Q is the quotient.
  6. Your can check your answer by converting your two starting numbers to decimal and using this equation,
    [(Divident-Remainder)/Divisor] = Quotient.

Example 1:

Solve 100010010 / 1101

Step A Q Divisor Details
0 0000 0000 1 0001 0010 0000 1101 Initialize
1 0000 0001 0 0010 0100 0000 1101 A < D
2 0000 0010 0 0100 1000 0000 1101 A < D
3 0000 0100 0 1001 0000 0000 1101 A < D
4 0000 1000 1 0010 0000 0000 1101 A < D
5 0001 0001 0 0100 0000 0000 1101 A > D (A-D = 100)
5.5 0000 0100 0 0100 0001 0000 1101 Move A-D to A. Replace right bit in Q with 1.
6 0000 1000 0 1000 0010 0000 1101 A < D
7 0001 0000 1 0000 0100 0000 1101 A > D (A-D = 0011)
7.5 0000 0011 1 0000 0101 0000 1101 Move A-D to A. Replace right bit in Q with 1.
8 0000 0111 0 0000 1010 0000 1101 A < D
9 0000 1110 0 0001 0100 0000 1101 A > D (A-D = 0001)
9.5 0000 0001 0 0001 0101 0000 1101 Move A-D to A. Replace right bit in Q with 1.

Your Answer is Q which is 00010101b=21, with a remainder of 00000001b = 1

Answer Check: 1101b=13, 100010010b=274, (274-1)/13 = 21.