Multiplication: shift-and-add, Booth's algorithm; restoring division

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Constant-delay CLA: how many gate delays and under what assumption? from Lesson 2.1.2
• 4-bit 0011 − 0101 in two's complement? from Lesson 2.1.1
• What does an arithmetic right shift fill in on the left? from Lesson 0.2.2

1 · The Hook

🎣

Multiplying by 0111 1111 (127) the schoolbook way needs seven additions. But 127 = 128 − 1, so one subtraction and one addition will do. That is Booth's algorithm, and GATE asks you to count its additions and subtractions.

2 · Predict First

🤔

7 in binary is 0111. Write 7 as a difference of two powers of two. How many add/subtract steps would that suggest for multiplying by 7?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

7 = 8 − 1 = 2³ − 2⁰. Multiply by 7 as (M × 8) − (M × 1): one addition and one subtraction, instead of three additions.

Shift-and-add (unsigned)

Schoolbook multiplication in binary: for each multiplier bit (from the right), if it is 1, add the multiplicand shifted left by that bit's position. For n-bit operands the product needs 2n bits.

Hardware version with registers M (multiplicand), Q (multiplier) and A (accumulator, starts at 0), repeated n times:

• If Q₀ = 1: A ← A + M (carry into a flip-flop C).
• Shift C, A, Q right by one bit together.

After n steps the product is in A:Q. Number of additions = number of 1s in the multiplier.

Booth's algorithm (two's complement)

Booth works directly on signed numbers. Keep an extra bit Q₋₁ (initially 0) to the right of Q. Repeat n times:

• Look at the pair (Q₀, Q₋₁):

• 10 → A ← A − M (start of a run of 1s)

• 01 → A ← A + M (end of a run of 1s)

• 00 or 11 → do nothing (inside a run)

• Arithmetic shift right A, Q, Q₋₁ together.

After n steps, A:Q holds the 2n-bit signed product.

Booth recoding (fast counting)

Append a 0 to the right of the multiplier. Read pairs (bit, bit to its right) from right to left:

• 10 → −1 (a subtraction), 01 → +1 (an addition), 00, 11 → 0.

Example: 0111 (+0 appended: 01110) gives, from the right: 10 → −1, 11 → 0, 11 → 0, 01 → +1. Recoded: +1 0 0 −1 = 8 − 1 = 7. One addition, one subtraction.

• Best case: long runs of 1s (few transitions).
• Worst case: alternating bits 0101 0101 → every pair is a transition: n operations for n bits.
• The number of operations = the number of transitions in the multiplier with a 0 appended on the right.

Booth trace: 3 × 7 in 4 bits

M = 0011, −M = 1101, Q = 0111, Q₋₁ = 0, A = 0000.

Product A:Q = 0001 0101 = 21. ✓

Division (brief)

Restoring division of an n-bit dividend Q by divisor M, A = 0, repeated n times: shift A:Q left; A ← A − M; if A < 0, set Q₀ = 0 and restore A ← A + M; else Q₀ = 1. Quotient ends in Q, remainder in A. Non-restoring division skips the restore step by adding M in the next step instead. Division takes n steps, each with an add or subtract.

4 · Visual

Booth recoding of 0110 1110 (append 0 on the right)

 bits:     0  1  1  0  1  1  1  0 |0
 pairs:   01 11 10 01 11 11 10 00         (bit, right neighbour), left to right
 digit:   +1  0 -1 +1  0  0 -1  0
                                          2 additions (+1), 2 subtractions (-1)
check: 128 - 32 + 16 - 2 = 110 = 0110 1110

5 · Worked Examples

Example 1 Easy

Unsigned shift-and-add: how many additions to multiply by 1011 0101?

Solution

One per 1 bit: 5.

Example 2 Medium

Booth recoding of the 8-bit multiplier 0011 1100: how many additions and subtractions?

Solution

Append 0: 0011 1100 0. Transitions: a run of 1s from bit 2 to bit 5 gives −1 at bit 2 and +1 at bit 6: 1 addition, 1 subtraction (64 − 4 = 60 ✓).

Example 3 GATE

How many additions and subtractions does Booth's algorithm perform for the 8-bit multiplier 1010 1010?

Solution

Pairs from the right (with 0 appended): 00, 10, 01, 10, 01, 10, 01, 10 → 3 additions, 4 subtractions. Recoded: −1 +1 −1 +1 −1 +1 −1 0 = −128 + 64 − 32 + 16 − 8 + 4 − 2 = −86 = 1010 1010 ✓.

6 · GATE Traps

⚠️

• Pair order: (current bit, bit to its right). 10 is subtract, 01 is add.
• Booth uses arithmetic shifts (sign kept); unsigned shift-and-add shifts in the carry.
• Always append the 0 on the right before recoding.
• The product of two n-bit numbers needs 2n bits.

7 · Memory Hook

🧠

"Start of a run: subtract. End of a run: add." Reading right to left, a run of 1s begins with 10 and ends with 01.

8 · Connect the Dots

Chapter 2.1 is complete: the ALU slice, fast carries and multiplication. Chapter 2.2 connects the ALU to registers and memory through buses: the datapath, and the register transfers that execute an instruction step by step.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markBooth additions

In Booth's algorithm with the 8-bit multiplier 0110 1110, how many additions are performed?

Numerical answer: ________

Q2NAT2 marksBooth operations

Total number of additions plus subtractions in Booth's algorithm for the 8-bit multiplier 0101 0101?

Numerical answer: ________

Q3MCQ1 markBooth step

In Booth's algorithm, (Q₀, Q₋₁) = (1, 0). The step is:

• (A) only arithmetic shift right
• (B) A ← A − M, then logical shift right
• (C) A ← A + M, then arithmetic shift right
• (D) A ← A − M, then arithmetic shift right

Q4NAT1 markProduct width

Two 16-bit signed numbers are multiplied with Booth's algorithm. How many bits does the full product have?

Numerical answer: ________

Q5NAT2 marksRecoded value

Booth recoding of the 4-bit two's-complement multiplier 1101 gives which number of subtractions?

Numerical answer: ________

10 · Rule Card

• Shift-and-add (unsigned): one addition per 1 bit; product 2n bits.
• Booth: (Q₀,Q₋₁) 10 → A − M; 01 → A + M; 00/11 → nothing; then arithmetic shift right A,Q,Q₋₁; n steps.
• Recode with a 0 appended: pairs (bit, right neighbour): 10 = −1, 01 = +1.
• Booth operations = transitions; worst case alternating bits (n ops); best case long runs.
• Restoring division: shift, subtract, restore if negative; n steps.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

shift-and-add multiplicationmultiplicand M, multiplier Q, accumulator ABooth's algorithmQ₋₁ bitBooth recoding (+1, 0, −1)runs of 1srestoring divisionnon-restoring division

12 · Answer Vault