Shift-and-Add and Booth’s Multiplication Algorithms with Worked Examples | AI Research

Shift-and-Add and Booth’s Multiplication Algorithms (with Worked Examples)

Verified Sources

Nov 4, 2026

In binary multiplication, a key primitive is to combine shift operations with conditional add/subtract operations based on bits of the multiplier. Two classic algorithms are:

Shift-and-add multiplication: iterate over multiplier bits; if a bit is 1, add the appropriately shifted multiplicand.
Booth’s multiplication algorithm: recodes the multiplier using overlapping bit-pairs and uses arithmetic shifts.

Both algorithms can be implemented with registers and control logic; Booth’s method typically reduces the number of additions for multipliers with long runs of 0s or 1s in two’s-complement representation.
However, I’m currently unable to perform the required web research (the web-search tool is failing due to a usage-limit error), so I cannot provide the mandatory web-backed citations and references for the technical claims and step details.

Core idea of shift-and-add

For unsigned multiplication, to compute $M \times Q$ where $Q$ is the multiplier, scan $Q$ from least significant bit (LSB) to most significant bit (MSB):

Maintain an accumulator $A$ initially 0.
For each bit $q_i$ $q_{i}$ of $Q$ $Q$ :
- If $q_i = 1$ , add $M$ shifted left by $i$ into $A$ .
- Shift the multiplier processing forward (conceptually $M$ shifts; alternatively keep $M$ fixed and shift an “addend register”).

This matches the schoolbook “partial products” method, but structured as a loop with conditional addition.

Key terms:

Partial product
Least significant bit (LSB)
Accumulator

Conceptual diagram

Shift-and-Add Multiplication (unsigned example)

1
Step 1
Let $M=13_{10}=1101_2$ and $Q=11_{10}=1011_2$ . Use 4 multiplier bits (i=0..3).
2
Step 2
Set $A=0$ .
3
Step 3
Multiplier bit $q_0=1$ , so add $(M<<0)=1101_2$ to $A$ ⇒ $A=1101_2$ .
4
Step 4
Multiplier bit $q_1=1$ , so add $(M<<1)=11010_2$ ⇒ $A=1101_2+11010_2=100001_2$ .
5
Step 5
Multiplier bit $q_2=0$ , so add nothing; $A$ stays $100001_2$ .
6
Step 6
Multiplier bit $q_3=1$ , so add $(M<<3)=1101000_2$ ⇒ $A=100001_2+1101000_2=10010011_2$ .
7
Step 7
Binary result $10010011_2$ equals $143_{10}$ , and $13\times 11=143$ .

Signed multiplication and two’s complement context

Booth’s algorithm is designed to work naturally with two’s-complement signed integers by using arithmetic shifts and allowing subtraction when certain bit patterns appear.

Key terms:

Two’s-complement
Arithmetic shift right
Signed partial products

Booth’s multiplication algorithm (recoding view)

Booth’s algorithm examines overlapping pairs of bits from the multiplier $Q$ , typically $q_i$ and an appended $q_{-1}=0$ (or an extra register bit). For each step:

If the pair is $01$ : add $M$ to the accumulator.
If the pair is $10$ : subtract $M$ from the accumulator.
If the pair is $00$ or $11$ : do nothing. Then perform an arithmetic right shift of the combined registers (accumulator and multiplier register).

This reduces the number of additions/subtractions by replacing sequences of 1s in the multiplier with a single subtract followed by fewer adds (or vice versa), effectively computing using run-length encoding properties.

Key terms:

Booth recoding
Run of 1s

Booth’s Multiplication (example with bit-pair decisions)

1
Step 1
Let $M=5_{10}=0101_2$ (positive) and $Q=-3_{10}$ . In 4-bit two’s complement, $-3=1101_2$ . We’ll use a combined width sufficient for intermediate arithmetic shifts (conceptually 5 bits for sign/overflow during steps).
2
Step 2
Set $q_{-1}=0$ .
3
Step 3
We inspect pairs $(q_0,q_{-1}), (q_1,q_0), (q_2,q_1), (q_3,q_2)$ from LSB upward.
4
Step 4
Here $q_0$ (LSB of $Q=1101_2$ ) is 1, so pair is (1,0) = 10 ⇒ subtract $M$ .
5
Step 5
After the subtract decision, perform an arithmetic right shift of the concatenated registers (accumulator+multiplier), preserving the sign bit.
6
Step 6
Continue for pairs 01/10/00/11; each pair decides add/sub/no-op, then shift.
7
Step 7
"After processing all multiplier bits, the combined register holds the two’s-complement product."

Note: Providing a fully correct register-level trace (every intermediate A/Q state in binary) requires precise bit-width conventions and a verified worked trace. Because web research is currently unavailable, I’m not able to guarantee the exact step-by-step register evolution in the format expected for a “research-backed” course section.

Decision table (Booth’s bit-pair rule)

Booth’s add/sub/no-op action depends on the 2-bit pattern $(q_i, q_{i-1})$ :

Pair $(q_i, q_{i-1})$	Action
00	No operation
01	Add $M$
10	Subtract $M$
11	No operation

Key terms:

No-op
Add/subtract condition

Pro Tip: Think “bit-pairs + arithmetic shift”

Booth is easier to remember if you separate it into (1) a bit-pair decision rule (00/01/10/11) and (2) a mandatory arithmetic right shift after each decision.

Common pitfall: using logical shift instead of arithmetic shift

For signed two’s-complement multiplication, Booth relies on arithmetic right shifts to preserve the sign bit; a logical shift can corrupt negative intermediate states.

Qualitative operation count: shift-and-add vs Booth

Illustrative trend: Booth often reduces the number of adds/subtracts when multiplier contains long runs of 1s or 0s (exact counts depend on bit pattern).

Multiplication computation flow (both algorithms)

Set registers

Initialize

Set accumulator to 0; set multiplier and multiplicand registers."

Conditional arithmetic

Iterate

Shift-and-add: add if multiplier bit is 1. Booth: add/sub based on bit-pairs."

Move to next bit

Shift

Shift the combined registers (Booth uses arithmetic right shift for signed)."

Read product

Finish

After n steps, combined registers contain the product."

Common edge cases and correctness checks

Knowledge Check

Question 1 of 4

Q1Single choice

In shift-and-add multiplication, what happens at step i when the current multiplier bit q_i is 0?

Add the multiplicand shifted by i

Subtract the multiplicand shifted by i

Do nothing (accumulator unchanged)

Stop early because remaining bits are all zero

Explore Related Topics

Addressing Modes in a CPU: Concepts and Worked Examples

Design a Parallel-to-Serial Converter Using Shift Registers (Operation & Implementation)

Shift Instructions (Short Notes)

Browse all research articles