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:
It works for unsigned numbers only. For signed numbers you would have to take absolute values, multiply, and fix the sign.
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^jSo "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: TrueThe 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.