Chapter 20 of 39

Booth's Multiplication Algorithm

Suppose a shopkeeper asks you to multiply 4,321 by 999. You could add 4,321 nine times, then nine times again shifted, and so on. Or you could notice that 999 = 1000 − 1, so the answer is 4,321,000 − 4,321 = 4,316,679. One subtraction instead of 27 additions.

Andrew Donald Booth used the same trick in binary in 1951. A run of 1s like 0011110 (30) equals 0100000 − 0000010 (32 − 2), so instead of adding the multiplicand four times we can add once and subtract once. Better still, the trick works directly on 2's complement signed numbers, so no separate sign handling is needed.

Booth's algorithm multiplies two signed numbers in 2's complement form. It scans the multiplier bits from right to left in pairs (Q0, Q−1); at the start of a run of 1s it subtracts the multiplicand, at the end of a run it adds it, and inside a run (or a run of 0s) it only shifts. After n steps of add/subtract and arithmetic right shift, the 2n-bit product is in A:Q.

In this chapter we first recall plain shift-and-add multiplication, then derive Booth's rule, trace it step by step on several examples (every trace below was produced and checked by a simulator that tested all pairs of 4-, 5- and 6-bit operands), learn Booth recoding and the faster bit-pair (radix-4) version, and solve exam-style questions.


Starting Point: Shift-and-Add Multiplication

Binary multiplication by hand is just like decimal: for every 1 in the multiplier, write the multiplicand shifted to that position, and add all the rows. Hardware does the same thing sequentially using three registers:

  • M: the multiplicand.

  • Q: the multiplier; the product's low half gradually shifts into it.

  • A: the accumulator, initially 0; holds the high half of the product. A carry bit C catches the carry out of A.

For n steps: if Q0 = 1, add M to A; then shift C, A, Q right by one bit.

Example: 13 × 11 (Unsigned, 4 Bits)

M = 1101, Q = 1011.

Step

Action

C

A

Q

0

initial

0

0000

1011

1

Q0 = 1: A ← A + M

0

1101

1011

shift right

0

0110

1101

2

Q0 = 1: A ← A + M

1

0011

1101

shift right

0

1001

1110

3

Q0 = 0: shift only

0

0100

1111

4

Q0 = 1: A ← A + M

1

0001

1111

shift right

0

1000

1111

Product A:Q = 1000 1111 = 143 = 13 × 11. Correct.

Two problems with this method:

  1. It works for unsigned numbers only. For signed numbers you would have to take absolute values, multiply, and fix the sign.

  2. It does one addition for every 1 in the multiplier. A multiplier like 0111 1110 needs six additions.

Booth's algorithm fixes both.


The Idea Behind Booth's Algorithm

A block of consecutive 1s from bit position j up to bit position k (k ≥ j) has the value

2^k + 2^(k-1) + ... + 2^j  =  2^(k+1) - 2^j

So "add M for every 1 in the run" can be replaced by "subtract M × 2j at the right end of the run and add M × 2k+1 just past its left end". Example: 0011110 = 25 − 21 = 32 − 2 = 30.

Scanning the multiplier from right to left, we can detect the ends of runs by looking at each bit Qi together with the bit to its right, Qi−1 (with an imaginary Q−1 = 0 to the right of bit 0):

Qi

Qi−1

Meaning

Action

Booth digit

0

0

Inside a run of 0s

Shift only

0

1

0

Start of a run of 1s (its right end)

A ← A − M, then shift

−1

1

1

Inside a run of 1s

Shift only

0

0

1

End of a run of 1s (just past its left end)

A ← A + M, then shift

+1

Memory trick: the Booth digit is simply Qi−1 − Qi.

Why It Works for Negative Multipliers

In 2's complement, the sign bit Qn−1 has weight −2n−1. Booth's digits sum to exactly this value: summing (Qi−1 − Qi) × 2i over all i telescopes to −Qn−1 × 2n−1 + Qn−2 × 2n−2 + ... + Q0, which is the 2's complement value of Q. A negative multiplier always ends with a run of 1s reaching the sign bit, and that run gets a −1 at its right end but no +1 at the left (there is no bit beyond the sign), which is precisely what makes the result negative. No sign correction is ever needed.


The Algorithm

Registers for n-bit operands: A (n bits, initially 0), Q (n bits, the multiplier), a single extra bit Q−1 (initially 0) to the right of Q, M (n bits, the multiplicand) and a step counter.

A ← 0;  Q ← multiplier;  Q-1 ← 0;  M ← multiplicand;  count ← n
repeat n times:
    if   (Q0, Q-1) = (1, 0):  A ← A - M      (add the 2's complement of M)
    elif (Q0, Q-1) = (0, 1):  A ← A + M
    arithmetic shift right A, Q, Q-1 as one unit
        (A's sign bit is copied; A0 moves into Qn-1; Q0 moves into Q-1)
    count ← count - 1
result: the 2n-bit product is in A:Q
          +-----------+   +-----------+   +-----+
  sign -->|     A     |-->|     Q     |-->| Q-1 |      arithmetic shift right
  copied  +-----------+   +-----------+   +-----+
                ^                 |  Q0 and Q-1 decide the operation
                |  add / subtract |
          +-----------+           v
          |  n-bit    |<---- control logic
          |  adder    |<---- M  (multiplicand)
          +-----------+

Two details that students often get wrong:

  • The shift is arithmetic: the leftmost bit of A is copied into itself, so a negative partial product stays negative.

  • Any carry out of A during the add or subtract is ignored. Booth's algorithm works modulo 2n in A, unlike the unsigned method, which keeps the carry.


Worked Example 1: 7 × 3

n = 4. M = 7 = 0111, −M = 1001. Q = 3 = 0011.

Step

Q0 Q−1

Operation

A

Q

Q−1

0

initial

0000

0011

0

1

1 0

A ← A − M

1001

0011

0

shift

1100

1001

1

2

1 1

shift only

1110

0100

1

3

0 1

A ← A + M

0101

0100

1

shift

0010

1010

0

4

0 0

shift only

0001

0101

0

Product A:Q = 0001 0101 = 21. In step 3, 1110 + 0111 = 1 0101; the carry out is discarded.

The multiplier 0011 has Booth digits 0 +1 0 −1, i.e. 4 − 1 = 3: one subtraction (step 1) and one addition (step 3), exactly as the trace shows.


Worked Example 2: (−5) × (−6)

n = 4. M = −5 = 1011, so −M = 0101. Q = −6 = 1010.

Step

Q0 Q−1

Operation

A

Q

Q−1

0

initial

0000

1010

0

1

0 0

shift only

0000

0101

0

2

1 0

A ← A − M

0101

0101

0

shift

0010

1010

1

3

0 1

A ← A + M

1101

1010

1

shift

1110

1101

0

4

1 0

A ← A − M

0011

1101

0

shift

0001

1110

1

Product A:Q = 0001 1110 = 30. Both operands were negative and the product is positive, with no sign handling at all. Notice the shift in step 3: A = 1101 is negative, so the arithmetic shift copies the 1 and gives 1110.


Worked Example 3: 13 × (−6) with 5 Bits

13 does not fit in 4-bit signed (range −8 to 7), so we use n = 5. M = 13 = 01101, −M = 10011. Q = −6 = 11010.

Step

Q0 Q−1

Operation

A

Q

Q−1

0

initial

00000

11010

0

1

0 0

shift only

00000

01101

0

2

1 0

A ← A − M

10011

01101

0

shift

11001

10110

1

3

0 1

A ← A + M

00110

10110

1

shift

00011

01011

0

4

1 0

A ← A − M

10110

01011

0

shift

11011

00101

1

5

1 1

shift only

11101

10010

1

Product A:Q = 11101 10010. As a 10-bit 2's complement number this is −(0001001110) = −78 = 13 × (−6). Correct.


Booth Recoding

Instead of tracing registers, we can rewrite the multiplier as a string of Booth digits {−1, 0, +1}, one per bit, using digiti = Qi−1 − Qi (with Q−1 = 0). The number of +1 digits is the number of additions, and the number of −1 digits is the number of subtractions.

Worked Example: Recoding

Multiplier

Value

Booth recoded (MSB → LSB)

Additions

Subtractions

0011110

30

0 +1 0 0 0 −1 0

1

1

1101011

−21

0 −1 +1 −1 +1 0 −1

2

3

0110110111

439

+1 0 −1 +1 0 −1 +1 0 0 −1

3

3

0011111111110000

16368

0 +1 0 0 0 0 0 0 0 0 0 −1 0 0 0 0

1

1

01010101

85

+1 −1 +1 −1 +1 −1 +1 −1

4

4

Check one by hand: for 1101011, the digit values are 0×64 − 1×32 + 1×16 − 1×8 + 1×4 + 0×2 − 1×1 = −32 + 16 − 8 + 4 − 1 = −21, which is the 2's complement value of 1101011. Correct.

Best and Worst Cases

  • Best case: long runs of 1s and 0s. The multiplier 0011111111110000 needs only 2 operations instead of the 10 additions of the shift-and-add method.

  • Worst case: alternating bits. For n = 8, the only multiplier needing an operation in all 8 steps is 01010101 (4 additions, 4 subtractions). Here Booth is worse than plain shift-and-add, which needs only 4 additions.

So plain Booth (radix-2) does not reduce the worst-case number of steps; there are always n cycles and up to n add/subtract operations. It reduces the average work for multipliers with long runs, and, most importantly, it handles signed numbers uniformly. To guarantee fewer operations, we need the next idea.


Bit-Pair Recoding (Modified Booth, Radix-4)

Bit-pair recoding looks at three bits at a time, Qi+1 Qi Qi−1, for i = 0, 2, 4, ..., and produces one radix-4 digit in {−2, −1, 0, +1, +2} per pair of multiplier bits. So an n-bit multiplier needs only n/2 partial products, each of which is 0, ±M or ±2M (2M is just M shifted left, so no real multiplication is needed).

Qi+1 Qi Qi−1

Digit

Partial product

000

0

0

001

+1

+M

010

+1

+M

011

+2

+2M

100

−2

−2M

101

−1

−M

110

−1

−M

111

0

0

The digit is −2Qi+1 + Qi + Qi−1. Equivalently, it is the sum of the two radix-2 Booth digits of the pair: (Qi − Qi+1) × 2 + (Qi−1 − Qi).

Worked Example: 5 × (−10) with Bit-Pair Recoding

Use n = 6. Multiplier Q = −10 = 110110, with Q−1 = 0. Group from the right:

Q = 1 1 0 1 1 0 | 0      (Q-1 = 0 appended)

bits 1,0,-1 :  1 0 0  ->  -2
bits 3,2,1  :  0 1 1  ->  +2
bits 5,4,3  :  1 1 0  ->  -1

recoded multiplier (MSB to LSB):  -1  +2  -2
check: -1 x 16 + 2 x 4 + (-2) x 1 = -16 + 8 - 2 = -10   (correct)

Now the three partial products (weights 40, 41, 42), each sign-extended to 12 bits:

   -2M x 1   = -10  =  1111 1111 0110
   +2M x 4   = +40  =  0000 0010 1000
   -1M x 16  = -80  =  1111 1011 0000
                       --------------
   sum       = -50  =  1111 1100 1110   (carries out of bit 11 discarded)

Three partial products instead of six. This is why fast hardware multipliers (and many in real CPUs) use radix-4 Booth recoding together with a tree of carry-save adders.


A Pitfall: The Most Negative Multiplicand

With n bits, the multiplicand M = −2n−1 (for example −8 in 4 bits) has no positive counterpart: −M does not fit in n bits. Computing A − M then overflows A, and the result is wrong. Our simulator confirms that with n = 4, every product with M = −8 (and a non-zero multiplier) comes out wrong; for example (−8) × 3 gives +24 instead of −24.

The fix is to give A and M one extra bit (n + 1 bits). With 5 bits, (−8) × 3 = −24 and (−8) × (−8) = 64 come out correctly. Note that the multiplier Q = −2n−1 causes no problem; only the multiplicand does.


Reference Implementation

This short Python function follows the register-level algorithm exactly. It was used to check every table in this chapter:

def booth(multiplicand, multiplier, n):
    mask = (1 << n) - 1
    M, A, Q, q_1 = multiplicand & mask, 0, multiplier & mask, 0
    for _ in range(n):
        pair = (Q & 1, q_1)
        if pair == (1, 0):
            A = (A - M) & mask          # A = A - M
        elif pair == (0, 1):
            A = (A + M) & mask          # A = A + M
        # arithmetic shift right of A, Q, Q-1 (sign bit of A is copied)
        q_1 = Q & 1
        Q = ((Q >> 1) | ((A & 1) << (n - 1))) & mask
        A = (A >> 1) | (A & (1 << (n - 1)))
    product = (A << n) | Q              # 2n-bit two's complement result
    if product >> (2 * n - 1):
        product -= 1 << (2 * n)
    return product

print(booth(7, 3, 4), booth(-5, -6, 4), booth(13, -6, 5))
print(booth(-8, 3, 4), booth(-8, 3, 5))

# check every pair of 6-bit numbers whose multiplicand is not -32
ok = all(booth(m, q, 6) == m * q
         for m in range(-31, 32) for q in range(-32, 32))
print("all correct:", ok)

Output:

21 30 -78
24 -24
all correct: True

The second line shows the pitfall: (−8) × 3 is wrong with 4 bits and correct with 5.


Comparison

Feature

Shift-and-add

Booth (radix-2)

Bit-pair (radix-4 Booth)

Operands

Unsigned

Signed 2's complement

Signed 2's complement

Bits examined per step

Q0

Q0, Q−1

Qi+1, Qi, Qi−1

Possible operations

0, +M

0, +M, −M

0, ±M, ±2M

Steps / partial products

n

n

n/2

Worst-case add/sub operations

n (multiplier all 1s)

n (alternating 0101...)

n/2

Strength

Simplest

Uniform signed handling, skips runs of 1s

Halves the partial products; used in fast multipliers


Solved Problems

Problem 1: Counting Operations

How many additions and subtractions does Booth's algorithm perform for the multiplier 1011001110?

Solution. Append Q−1 = 0 and apply digit = Qi−1 − Qi from right to left: the recoding is −1 +1 0 −1 0 +1 0 0 −1 0. That is 2 additions and 3 subtractions. Quick check: there are 3 runs of 1s (11, 111 and the 1 at the left), each starts with a subtraction; the two inner runs also end with an addition, but the leftmost run reaches the sign bit, so it gets no addition.

Problem 2: Booth Recoding to a Value

A multiplier is recoded as +1 0 −1 +1 0 −1. What is its value and what was the original 6-bit multiplier?

Solution. Value = 32 − 8 + 4 − 1 = 27 = 011011. Check: recoding 011011 with Q−1 = 0 gives bit pairs (Qi, Qi−1) from the right: (1,0) −1, (1,1) 0, (0,1) +1, (1,0) −1, (1,1) 0, (0,1) +1. Reading MSB to LSB: +1 0 −1 +1 0 −1. Correct.

Problem 3: Worst Case

For 8-bit operands, which multiplier makes Booth's algorithm do an add or subtract in every one of the 8 steps?

Solution. We need Qi ≠ Qi−1 for all i, starting with Q−1 = 0, so Q0 = 1, Q1 = 0, Q2 = 1, ...: the multiplier is 01010101 (85). Our simulator confirms it is the only 8-bit value with 8 operations.

Problem 4: Register Contents After a Step

Multiply M = 6 by Q = −7 with n = 5 (M = 00110, Q = 11001). What are A, Q and Q−1 after step 2?

Solution. −M = 11010.

  • Step 1: (Q0, Q−1) = (1, 0) → A = 0 − M = 11010; shift → A = 11101, Q = 01100, Q−1 = 1.

  • Step 2: (0, 1) → A = 11101 + 00110 = 00011 (carry discarded); shift → A = 00001, Q = 10110, Q−1 = 0.

(Continuing to step 5 gives A:Q = 11110 10110 = −42.)

Problem 5: Bit-Pair Digits

Find the bit-pair recoding of the 6-bit multiplier 011011 (27).

Solution. Triples from the right with Q−1 = 0: (1,1,0) → −1; (1,0,1) → −1; (0,1,1) → +2. Recoded MSB → LSB: +2 −1 −1. Check: 2 × 16 − 1 × 4 − 1 = 27. Correct, with 3 partial products instead of 6.


Common Mistakes

  • Using a logical shift. The shift must copy the sign bit of A. A logical shift breaks every negative partial product.

  • Swapping the rule. 10 means subtract, 01 means add. Remember: digit = Qi−1 − Qi; for 10 that is 0 − 1 = −1.

  • Forgetting Q−1 = 0 at the start (or forgetting to shift Q0 into it).

  • Keeping the carry out of A. In Booth's algorithm it is discarded; only the unsigned method keeps it.

  • Reading only A as the answer. The product is 2n bits: A is the high half and Q the low half.

  • Using n bits for M = −2n−1. −M does not fit; use n + 1 bits.

  • Claiming Booth is always faster. Radix-2 Booth can need n operations (alternating bits); only bit-pair recoding guarantees at most n/2.


Interview Questions

Why is Booth's algorithm preferred for signed multiplication?

It works directly on 2's complement operands, treating positive and negative multipliers identically, so no separate sign computation or correction is needed. It also skips over runs of 1s.

What do the bit pairs 00, 01, 10, 11 mean in Booth's algorithm?

(Q0, Q−1) = 00 or 11: inside a run, just shift. 10: start of a run of 1s, subtract M then shift. 01: end of a run of 1s, add M then shift.

Why must the shift be arithmetic?

A holds a signed partial product. Shifting right divides it by 2; for a negative value, the sign bit must be replicated to keep it negative.

What is the worst case for Booth's algorithm?

A multiplier with alternating bits such as 0101...01, which needs an add or subtract in every one of the n steps; it can be worse than shift-and-add.

What is bit-pair (modified Booth) recoding?

A radix-4 version that examines three bits at a time and produces one digit in {−2, −1, 0, +1, +2} per pair of bits, halving the number of partial products to n/2.

Is there any input for which Booth's algorithm fails?

With n-bit registers, a multiplicand of −2n−1 fails because −M cannot be represented. Extending A and M by one bit fixes it.


Summary

  • Booth's algorithm multiplies 2's complement signed numbers with registers A, Q, Q−1 and M, in n steps.

  • Rule on (Q0, Q−1): 10 → A − M, 01 → A + M, 00 / 11 → nothing; then arithmetic shift right A, Q, Q−1. The product is in A:Q.

  • Traced examples: 7 × 3 = 0001 0101 (21), (−5) × (−6) = 0001 1110 (30), 13 × (−6) = 11101 10010 (−78).

  • Booth recoding: digit = Qi−1 − Qi; +1 digits are additions, −1 digits are subtractions. Best case: long runs; worst case: alternating bits.

  • Bit-pair recoding uses digits {0, ±1, ±2} on overlapping triples and halves the partial products.

  • Watch out for M = −2n−1: use an extra bit. The next chapter, Division: Restoring & Non-Restoring, applies the same register-and-shift approach to division.