UN

Division

Not on your listed exam slides, but it's the mirror image of multiplication and it appears in MIPS code (% uses it). Skim this after you're solid on the other three sections.

1. Vocabulary

Dividend=Quotient×Divisor+Remainder\text{Dividend} = \text{Quotient} \times \text{Divisor} + \text{Remainder}
…and the remainder is always smaller than the divisor.

Division is the least frequent and quirkiest operation — it's the only one that lets you attempt something mathematically invalid: dividing by 0.

2. Long division in binary

Easier than decimal: each quotient digit is only ever 0 or 1 — the divisor either fits or it doesn't.

        1101         ← Quotient (13)
    ┌────────
 10 │ 11011        ← Dividend (27), Divisor 10 (2)
     10            fits → q bit 1
     --
      10
      10           fits → q bit 1
      --
       01          doesn't fit → q bit 0
        11
        10         fits → q bit 1
        --
         1         ← Remainder (1)

27 = 13 × 2 + 1  ✔

3. The division algorithm (restoring division)

Hardware can't “see” whether the divisor fits. So it just subtracts anyway and checks the sign afterwards — if the result went negative the subtraction was a mistake, so it puts the value back. That's why it's called restoring division.

Initialise Remainder = Dividend, then repeat:

Remainder = Dividend
initialisation
start loop
1. Remainder = Remainder − Divisor
always
2. Test the Remainder
branch
2a. Rem ≥ 0 → shift Quotient LEFT, new rightmost bit = 1
or
2b. Rem < 0 → Remainder += Divisor (restore), shift Quotient LEFT, new bit = 0
always
3. Shift the Divisor register RIGHT 1 bit
(n+1)th repetition?
Done after n + 1 repetitions
Restoring division — for an n-bit divisor it takes n + 1 steps.
Complexity. Time=O(n+1)=O(n)\text{Time} = O(n+1) = O(n) · Space=O(m+n)\text{Space} = O(m+n) for an mm-bit divisor and (m+n)(m+n)-bit dividend.

4. The hardware

RegisterWidthWhat it does
Divisor64 bits (2n)Shifts right once per iteration (actual divisor is 32 bits, held in the top half)
ALU64-bitSubtracts / restores
Quotient32 bits (n)Shifts left, one new bit per iteration
Remainder64 bits (2n)Initialised to the dividend

Compare with multiply: the shifts run the opposite way (divisor right, quotient left) and the accumulator starts at the dividend rather than 0.

5. Worked trace — 0000 0111 ÷ 0010 (7 ÷ 2)

4-bit version ⇒ 5 iterations.

IterStepQuotientDivisorRemainder
0Initial values00000010 00000000 0111
11: Rem = Rem − Div00000010 00001110 0111
2b: Rem < 0 ⇒ +Div, sll Q, Q₀ = 000000010 00000000 0111
3: shift Divisor right00000001 00000000 0111
21: Rem = Rem − Div00000001 00001111 0111
2b: Rem < 0 ⇒ +Div, sll Q, Q₀ = 000000001 00000000 0111
3: shift Divisor right00000000 10000000 0111
31: Rem = Rem − Div00000000 10001111 1111
2b: Rem < 0 ⇒ +Div, sll Q, Q₀ = 000000000 10000000 0111
3: shift Divisor right00000000 01000000 0111
41: Rem = Rem − Div00000000 01000000 0011
2a: Rem ≥ 0 ⇒ sll Q, Q₀ = 100010000 01000000 0011
3: shift Divisor right00010000 00100000 0011
51: Rem = Rem − Div00010000 00100000 0001
2a: Rem ≥ 0 ⇒ sll Q, Q₀ = 100110000 00100000 0001
3: shift Divisor right00110000 00010000 0001

Quotient = 0011 = 3, Remainder = 0000 0001 = 1 ✔ 7 = 3 × 2 + 1.

6. Signed division

Same idea as signed multiply: divide the magnitudes, then fix the signs.

  • Negate the quotient if the signs of dividend and divisor disagree.
  • The remainder takes the sign of the dividend (when it's non-zero).
OperationQuotientRemainderCheck: Q × D + R
+7 ÷ +2+3+13×2 + 1 = +7 ✔
−7 ÷ +2−3−1−3×2 − 1 = −7 ✔
+7 ÷ −2−3+1−3×−2 + 1 = +7 ✔
−7 ÷ −2+3−13×−2 − 1 = −7 ✔
Why not quotient −4 remainder +1 for −7 ÷ +2? It satisfies the formula too, but then ∣Q∣|Q| would change depending on the operand signs, i.e. −(x÷y)≠(−x)÷y-(x \div y) \ne (-x) \div y — a nightmare for programmers. The “remainder matches the dividend” rule avoids that.

7. Division in MIPS

Same Hi/Lo pair as multiply, but with different contents: Lo = quotient, Hi = remainder.

InstructionMeaning
div $s2, $s3Lo = $s2 / $s3, Hi = $s2 mod $s3 (signed)
divu $s2, $s3unsigned quotient and remainder
div  $t3, $t2     # $t3 ÷ $t2
mflo $t1          # quotient  → $t1
mfhi $t0          # remainder → $t0

Slide example — j = i % 2

int i, j;               // i = $s0,  j = $s1
j = i % 2;
if (j == 0)  i = i + 2;
else         i = i + 1;
    addi $t0, $zero, 2
    div  $s0, $t0
    mfhi $s1            # j = i % 2   (remainder is in Hi)

    bne  $s1, $zero, L1
    addi $s0, $s0, 2
    j    L2
L1:
    addi $s0, $s0, 1
L2:
    ...