Signed division and non-restoring division

Signed binary division

Division of signed integers is done on the magnitudes (sign-magnitude method), and the signs are handled separately:

1. Store the sign of the dividend (Sd) and of the divisor (Sv), and take the absolute values.
2. Divide the magnitudes with the restoring or non-restoring algorithm to get the quotient Q and remainder R.
3. Quotient sign = Sd XOR Sv (negative if the signs differ).
4. Remainder sign = sign of the dividend, so that dividend = divisor × quotient + remainder.
5. If the dividend and divisor are in 2's complement, convert negative values to positive before step 2 and convert the results back at the end.
6. Check for divide overflow: the divisor must not be 0, and the quotient must fit in the register.

Non-restoring algorithm

1. Load A = 0, Q = dividend, M = divisor, SC = n.
2. If the sign of A is 0 (A ≥ 0): shift A,Q left, then A = A − M. If the sign of A is 1 (A < 0): shift A,Q left, then A = A + M.
3. If the new A is non-negative, set Q0 = 1; otherwise set Q0 = 0.
4. SC = SC − 1. Repeat from step 2 until SC = 0.
5. If A < 0 at the end, correct the remainder: A = A + M.
6. Q is the quotient and A is the remainder.

15 ÷ 4

Both numbers are positive, so no sign handling is needed. Q = 15 = 1111, M = 4 = 00100 (A and M have n + 1 = 5 bits), n = 4.

Step  Action                              A      Q
-     Initial                             00000  1111
1     Shift left A,Q                      00001  1110
      A>=0 before shift: A = A - M (=-3)  11101  1110 (Q0=0)
2     Shift left A,Q                      11011  1100
      A<0 before shift: A = A + M (=-1)   11111  1100 (Q0=0)
3     Shift left A,Q                      11111  1000
      A<0 before shift: A = A + M (=3)    00011  1001 (Q0=1)
4     Shift left A,Q                      00111  0010
      A>=0 before shift: A = A - M (=3)   00011  0011 (Q0=1)

The final A is positive, so no remainder correction is needed.

Answer: 15 ÷ 4: quotient = 3 (0011), remainder = 3 (00011)