Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 67 ยท Data Representation

Binary Multiplication and Division Algorithms

Learn how hardware multiplies and divides binary numbers: shift-and-add, Booth's algorithm for signed values, restoring and non-restoring division, with Python traces.

Addition is easy to wire up, but multiplication and division need a procedure: a loop of simple steps that a small circuit can repeat. A processor with no multiply instruction can still multiply by running these loops in software, and a processor that has one runs the same loops in hardware, usually with extra parallel adders to make it fast.

In this lesson you will follow the schoolbook method in binary, extend it to signed numbers with Booth's algorithm, and then do division with the restoring and non-restoring methods. Every algorithm is simulated in Python so you can watch the registers change. It builds on binary arithmetic and integer representation.

Shift-and-add multiplication

Multiplying by hand, you write one shifted copy of the top number for each digit of the bottom number and add the copies. In binary every digit is 0 or 1, so each copy is either the multiplicand or zero. That gives a very simple loop:

  1. Look at the lowest bit of the multiplier.
  2. If it is 1, add the multiplicand to the product register.
  3. Shift the multiplicand left by one and the multiplier right by one.
  4. Repeat for every bit of the multiplier.

For an n-bit multiplier this takes n steps, and the product needs up to 2n bits.

Python Shift-and-add multiplier

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that steps where the multiplier bit is 0 do nothing but shift. A long run of zeros wastes time, which is the first hint for the next algorithm.

The problem with negative numbers

The loop above works for unsigned values. For two's complement numbers, the sign bit of the multiplier has negative weight, and the multiplicand also needs sign extension. You could convert both to positive, multiply, and fix the sign at the end, but there is a more elegant trick.

Booth's algorithm

A run of ones in the multiplier, such as 0111100, equals a difference of two powers of two: 1000000 - 0000100. So instead of adding the multiplicand once for every 1, you can subtract at the start of the run and add just after its end. Long runs of ones then cost two operations instead of many. And because the rule works on bit pairs, the sign bit is handled correctly with no special case.

Booth's algorithm appends an extra bit Q-1 = 0 to the right of the multiplier and looks at the pair (Q0, Q-1) at every step:

Q0 Q-1 Meaning Action
0 0 middle of a run of zeros nothing
1 1 middle of a run of ones nothing
1 0 start of a run of ones subtract the multiplicand
0 1 end of a run of ones add the multiplicand

After the action, the combined registers A, Q, Q-1 are shifted right arithmetically (the top bit is copied). After n steps, A and Q together hold the 2n-bit signed product.

flowchart TD
  S["A = 0, Q = multiplier, Q-1 = 0"] --> C{"Q0, Q-1"}
  C -->|"10"| SUB["A = A - M"]
  C -->|"01"| ADD["A = A + M"]
  C -->|"00 or 11"| SH
  SUB --> SH["Arithmetic shift right of A, Q, Q-1"]
  ADD --> SH
  SH --> D{"n steps done?"}
  D -->|"no"| C
  D -->|"yes"| E["Product = A and Q"]

One Booth iteration: inspect the bit pair, add or subtract, then shift the combined registers right.

Python Booth's algorithm, step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The final line of each trace matches Python's own multiplication. Note that -6 x -6 also works with no sign fix-up.

Booth's algorithm is not always faster: an alternating pattern like 0101 has no runs and needs an operation at every step. Modern designs use modified Booth (radix-4), which looks at three bits at a time and halves the number of partial products, then sums them in a tree of adders.

Restoring division

Division is the reverse process: repeatedly try to subtract the divisor. Long division in binary is easy, because at each step the quotient digit is either 0 or 1. The restoring algorithm keeps a remainder register A and the dividend in Q:

  1. Shift A and Q left by one as a pair (the top bit of Q moves into A).
  2. Subtract the divisor from A.
  3. If A is now negative, the divisor did not fit: set the new quotient bit to 0 and restore A by adding the divisor back.
  4. Otherwise set the quotient bit to 1.

After n steps, Q holds the quotient and A the remainder.

Python Restoring division

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The restore step costs an extra addition on every failed subtraction. On average half the steps fail, so the hardware does about 1.5 operations per bit.

Non-restoring division

The non-restoring method notices that restoring and then subtracting in the next step is wasteful: after a restore, the next step shifts (doubling A) and subtracts D, which equals 2(A + D) - D = 2A + D. So if A is negative, skip the restore and add the divisor in the next step instead:

  • If A is non-negative: shift left, then subtract D.
  • If A is negative: shift left, then add D.
  • The quotient bit is 1 if A is non-negative after the operation, otherwise 0.
  • At the end, if A is negative, add D once to correct the remainder.

That is exactly one add or subtract per bit, with a single correction at the end.

Python Non-restoring division

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A real divider checks for a zero divisor first and raises a divide-error exception: neither algorithm can produce a meaningful answer in that case.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In shift-and-add multiplication, when is the multiplicand added to the product?

    Each 1 bit of the multiplier contributes one shifted copy of the multiplicand; 0 bits contribute nothing.
  2. 2. What does Booth's algorithm do when the bit pair (Q0, Q-1) is 10?

    The pair 10 marks the start of a run of ones, where the run is treated as a power of two minus a smaller power, so the multiplicand is subtracted.
  3. 3. Why does Booth's algorithm need no special sign handling?

    In two's complement the top bit has weight minus 2^(n-1), which is exactly what the run-of-ones rule produces at the end of the multiplier.
  4. 4. What is the extra work in restoring division compared with non-restoring division?

    Non-restoring division skips the restore and adds in the next step, so it needs only one add or subtract per bit.
  5. 5. After a non-restoring division, the remainder register A is negative. What must be done?

    A negative final A means the last subtraction overshot, so one final addition produces the true remainder.

Summary

  • Shift-and-add multiplication adds a shifted multiplicand for every 1 bit of the multiplier; it takes n steps for n bits.
  • Booth's algorithm inspects bit pairs, subtracting at the start of a run of ones and adding after its end, and handles signed numbers naturally.
  • Restoring division subtracts the divisor, and puts it back when the result is negative.
  • Non-restoring division avoids the restore by adding instead of subtracting after a negative result, with one final correction.
  • Hardware multipliers and dividers use these ideas with extra parallelism (radix-4 Booth, adder trees).

Continue with Floating-Point Numbers.