The idea: one adder, one shifting register, one cycle per bit

An adder gives its answer in one clock cycle. A simple multiplier or divider does not: it uses the same adder again and again, once per bit of the word. Each clock cycle does one small step of the long multiplication or long division you learned at school, in base 2. A 32-bit MIPS word needs 32 cycles. The page uses 4-bit words, so every run takes four cycles and every bit fits on screen.

The shared datapath: register M feeds a 5-bit adder and subtractor; the adder reads and writes the left part x and A of a double register x, A, Q; the double register shifts right for multiply and left for divide; a control unit tests one or two bits and picks add, subtract and shift; A becomes hi and Q becomes lo
All three circuits use the same parts: a register M, one adder and a double register that shifts. Only the control rule changes.

The parts, as drawn on the canvas:

PartMultiplyDivide
Mthe multiplicandthe divisor
A (hi half)upper half of the product, starts at 0the remainder, starts at 0
Q (lo half)the multiplier at first, the lower half of the product at the endthe dividend at first, the quotient at the end
xone extra bit left of A: the carry out of the adder (Booth: an extra sign bit)the sign of the subtraction
Q−1Booth only: the bit that was shifted out of Q lastnot used

Each tab is one circuit. Clock Once runs one clock cycle, Run All runs to the result. The trace panel writes one row per step, like the tables in the textbook.

Shift-and-add multiplication

Long multiplication in binary is easy, because each digit of the multiplier is 0 or 1: a row is either the multiplicand or nothing. So the hardware looks at one multiplier bit per cycle:

  1. Test the lowest bit Q0.
  2. If it is 1, add M to A.
  3. Shift x, A and Q one place right.

The shift does two jobs at once. It drops the multiplier bit that was just used, and it moves the lowest bit of A into Q, where it is a finished product bit. So the multiplier and the lower half of the product can share Q. Demo: 2 × 3 (multiplicand 2 = 0010, multiplier 3 = 0011):

CycleStepx AQ
0start0 00000011
1Q0 = 1: add M0 00100011
1shift right0 00010001
2Q0 = 1: add M0 00110001
2shift right0 00011000
3Q0 = 0: no add, shift right0 00001100
4Q0 = 0: no add, shift right0 00000110

The product is A:Q = 0000 0110 = 6, after two adds. Two N-bit numbers give a product of up to 2N bits: Demo: 15 × 15 ends with 1110 0001 = 225. In that run the sum in cycle 2 is 0111 + 1111 = 1 0110, which needs five bits. The fifth bit is the carry out of the adder. It is kept in x and the shift moves it back into A.

The first circuit in Patterson and Hennessy has three registers: a 2N-bit multiplicand that shifts left, an N-bit multiplier that shifts right, and a 2N-bit product, with a 2N-bit adder. The page shows the refined circuit. It keeps the multiplicand still, shifts the product right instead, and stores the multiplier in the unused right half of the product. Half the bits and half the adder are saved; the steps are the same.

Signed numbers: Booth's algorithm

Shift-and-add reads its inputs as unsigned numbers. Give it −3 = 1101 and it multiplies by 13. Booth's algorithm works on two's complement numbers directly. It rests on one fact: a run of ones is a difference of two powers of two. For example 0111 = 7 = 8 − 1. So instead of adding M once for every 1 in the run, subtract M where the run starts and add M one place after it ends.

Multiplying by 0111: shift-and-add adds M three times, for the weights 1, 2 and 4; Booth looks at pairs of bits, subtracts M at the pair 10 that starts the run and adds 8 M at the pair 01 that ends it, giving the same 7 M with two uses of the adder
A run of ones costs shift-and-add one add per 1; Booth pays one subtract at the start of the run and one add at its end.

The control looks at two bits each cycle: Q0 and Q−1, the bit that left Q in the cycle before (0 at the start).

Q0 Q−1MeaningAction before the shift
1 0a run of ones startsA = A − M
1 1middle of a run of onesnothing
0 1the run has endedA = A + M
0 0a run of zerosnothing

The shift is an arithmetic right shift: the top bit keeps its value, so a negative A stays negative. A negative multiplier needs no special case. Its top bit is 1, so its last run of ones never "ends": the final add is skipped, and that is exactly the weight −2N−1 of the sign bit.

  • Demo: 2 × −3: Q = 1101. The pairs are 10, 01, 10, 11: subtract, add, subtract, nothing. The result is 1111 1010 = −6.
  • Demo: 5 × 7: Q = 0111. The pairs are 10, 11, 11, 01: one subtract and one add give 0010 0011 = 35. Shift-and-add would add three times.
  • Demo: −8 × −8: the only use of the adder is 0 − (−8) = +8 = 0 1000. In four bits 1000 would read as −8. This is why A has the extra bit x. The result is 0100 0000 = 64.

On a 4-bit word the saving is small, and for a multiplier like 0101 Booth even uses the adder more often (four times instead of two). Its real value is that signed numbers work with no extra steps. Fast multipliers use a variant that looks at three bits at a time and so halves the number of rows to add.

Restoring division

Long division asks one question per digit: does the divisor fit into what is left? In base 2 the answer is yes (quotient bit 1) or no (quotient bit 0). The hardware finds out by trying. It subtracts the divisor and looks at the sign of the result.

One cycle of restoring division: shift x, A and Q left; subtract M from A; if the result is negative add M back and set Q0 to 0, otherwise keep the result and set Q0 to 1; after four cycles A is the remainder and Q is the quotient
One divide cycle: shift left, subtract, test the sign; a negative result is undone and gives a quotient bit 0.
  1. Shift x, A and Q one place left. The next dividend bit moves into A, and Q0 is left open.
  2. Subtract: A = A − M.
  3. Test the sign bit x. If it is 1, the result is negative: the divisor did not fit. Restore A by adding M back, and put 0 into Q0. If x is 0, keep the difference and put 1 into Q0.

After the last cycle Q holds the quotient and A the remainder. Demo: 7 ÷ 2 (dividend 0111, divisor 0010):

CycleStepx AQ
0start0 00000111
1shift left0 0000111_
1subtract M: negative1 1110111_
1restore, Q0 = 00 00001110
2shift, subtract (negative), restore, Q0 = 00 00011100
3shift, subtract: 3 − 2 = 1, Q0 = 10 00011001
4shift, subtract: 3 − 2 = 1, Q0 = 10 00010011

Quotient 3, remainder 1, with two restores. Demo: 13 ÷ 5 gives 2 remainder 3 with three restores. In Demo: 3 ÷ 5 the divisor never fits: all four cycles restore, the quotient is 0 and the remainder is the dividend, 3.

A restore costs a second use of the adder in the same cycle. Non-restoring division avoids it: it leaves the negative value in A and adds M in the next cycle instead of subtracting. The page shows the restoring kind because each step matches long division by hand.

Where the results go in MIPS: hi and lo

A 32-bit multiply gives a 64-bit product, and a divide gives two results. Neither fits in one 32-bit register. So MIPS has two special registers, hi and lo. Together they are the double register of the page: hi is A and lo is Q.

InstructionWhat it does
mult $s0, $s1signed product: hi = upper 32 bits, lo = lower 32 bits
multu $s0, $s1the same for unsigned numbers
div $s0, $s1signed divide: lo = quotient, hi = remainder
divu $s0, $s1the same for unsigned numbers
mfhi $t0, mflo $t0copy hi or lo into an ordinary register

To compute c = a * b for C ints a compiler emits mult and then mflo; the upper half in hi is ignored. For a / b it reads lo, for a % b it reads hi. MIPS raises no exception when a product does not fit in 32 bits or when the divisor is 0. Software must check for that itself.

See also Arithmetic Circuits for the adder inside this datapath (ripple carry, carry-lookahead, prefix) and for the array multiplier, which does all the adds in one cycle with N rows of adders.

See also Number Bases and Two's Complement and Number Systems for how negative numbers are stored, and The Single-Cycle MIPS Processor for the datapath that runs every other instruction in one cycle.

What the page leaves out

  • Signed division. The usual way is to divide the absolute values and then fix the signs: the quotient is negative when the signs differ, and the remainder takes the sign of the dividend.
  • Division by zero. The menus do not offer it. Real hardware runs its cycles anyway and leaves a meaningless result.
  • Faster circuits: non-restoring and SRT division, radix-4 Booth recoding, and Wallace trees of carry-save adders that multiply in one or a few cycles.
  • 32-bit words. The steps are the same; there are just 32 cycles instead of 4.
  • The MIPS32 mul instruction, which writes the lower half of the product straight to a general register, and floating-point multiply and divide.

On the mind map

This page on the Computer Architecture mind map · 38 pages in 7 branches · open it to see the whole map and test yourself in recall mode.