Multiplication and Booth's algorithm
Booth's algorithm is a shift-and-add method for multiplying two's-complement signed integers efficiently by scanning adjacent bits of the multiplier to decide add/subtract or do-nothing, reducing the number of arithmetic operations for runs of 1s.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Booth's algorithm is used by engineers when designing integer multiply units in CPUs, DSPs and hardware multipliers to handle signed numbers efficiently. It reduces the number of add/subtract operations for multipliers with runs of 1s, saving gate area and power in hardware and making software multiply routines simpler for two's-complement values.
Key ideas
Product: the result of multiplication. For two n-bit operands the exact product needs 2n bits.
Signed (two's complement) representation: a way to code negative integers in binary where the most significant bit (MSB) has weight −2^{n−1} and other bits have positive powers of two. Value formula: value = −b_{n−1}·2^{n−1} + Σ_{i=0}^{n−2} b_i·2^i.
Arithmetic right shift: shift all bits right by one, copying the sign bit (MSB) into the high position. It preserves two's-complement sign.
Booth's algorithm (exact definition): For n-bit two's-complement operands, maintain registers A (n bits, accumulator), Q (n bits, multiplier) and a single bit Q−1 (initially 0). Initialize A ← 0. For i from 1 to n do:
- Look at the pair (Q0, Q−1), where Q0 is the least-significant bit of Q.
- If (Q0,Q−1) = (0,1) then A ← A + M.
- If (Q0,Q−1) = (1,0) then A ← A − M.
- If (Q0,Q−1) = (0,0) or (1,1) then do nothing.
- Perform arithmetic right shift of the concatenated A,Q,Q−1 by one bit (i.e., new Q−1 ← old Q0). Repeat. After n iterations the concatenation (A,Q) is the 2n-bit product. Assumptions: operands are in two's-complement, widths of A and Q are equal to operand width n, M is sign-extended when used.
Why the rules work (short derivation): Booth encodes runs of 1s in Q by examining transitions between bits. A run like 0111...110 is equivalent to adding M shifted left by the start and subtracting M shifted left by the end, which reduces many single-bit adds into two operations. Algebraically, shifting and adding/subtracting M implements the binary place-value sum of partial products while using transitions in Q to compress consecutive ones.
Implementation notes (what to draw): draw 3 registers horizontally labelled A (left, n bits), Q (middle, n bits), Q−1 (right, 1 bit). Below or above, show M (n bits) and −M (two's complement). Also draw control box showing (Q0,Q−1) → action table with four entries (00: nothing, 01: A←A+M, 10: A←A−M, 11: nothing) and arrow to arithmetic-right-shift block. Label the number of iterations n. Variants: Modified Booth (radix-4) examines overlapping (Q1,Q0,Q−1) to select {−2M, −M, 0, +M, +2M}, reducing iterations to about n/2; commonly used in modern multipliers.
Formulas
Product = Multiplicand × Multiplier — multiplicand and multiplier are dimensionless integers; applies always.
Value(two's-complement) = -b_{n-1}·2^{n-1} + Σ_{i=0}^{n-2} b_i·2^i — b_i are bits (0 or 1), value is dimensionless integer; applies for n-bit two's-complement representations.
-M = two's-complement(M) = (~M) + 1 — ~ means bitwise NOT on n bits; result is n-bit two's-complement negation; applies for signed arithmetic within n-bit width assuming overflow is handled by extending to 2n bits where needed. Note: for M = −2^{n−1}, negation in n bits overflows and yields the same bit pattern (mod 2^n); products are still exact when kept in 2n bits.
After n Booth iterations: Product(2n bits) = concat(A,Q) — A and Q are registers used in algorithm; applies when algorithm is implemented as stated with arithmetic right shifts.
Arithmetic-right-shift(AQ,Q-1): (A,Q,Q-1) ← arithmetic_shift_right(concat(A,Q,Q-1),1) with new Q-1 = old Q0 — defines the combined shift; applies each iteration.
Worked examples
Example 1 — Unsigned shift-and-add (manual partial products) Problem: Multiply 13 × 11 (unsigned). Use 8-bit binary to show steps. Representation: 13 = 00001101_2, 11 = 00001011_2. Product should be 143. Steps:
- Write multiplier bits LSB→MSB: 1,1,0,1,0,0,0,0 (eight bits).
- Add shifted multiplicand for each '1' bit:
- shift 0 (LSB): add 00001101 → partial = 00001101 (13)
- shift 1: add 00011010 → partial = 00001101 + 00011010 = 00100111 (39)
- shift 2: bit=0 skip
- shift 3: add 01101000 → partial = 00100111 + 01101000 = 10001111 (143)
- No higher contributions; final 8-bit result 10001111_2 = 143.
Example 2 — Booth's algorithm for signed operands Problem: Multiply M = −3 and Q(multiplier) = 6 using 4-bit two's-complement representation (n=4). Expect product −18 encoded in 8 bits: 11101110_2. Representations: M(4) = 1101 (−3), Q(4) = 0110 (6), initial A = 0000, Q−1 = 0, iterations n = 4. Precompute −M = 0011 (positive 3). Trace table (A, Q, Q−1): Initial: A=0000 Q=0110 Q−1=0 Iteration 1: (Q0,Q−1)=(0,0) → do nothing. Arithmetic right shift: A=0000 Q=0011 Q−1=0 Iteration 2: (Q0,Q−1)=(1,0) → A ← A − M (i.e. add two's complement of M): A = 0000 − 1101 = 0011. Shift: A=0001 Q=1001 Q−1=1 Iteration 3: (Q0,Q−1)=(1,1) → do nothing. Shift: A=0000 Q=1100 Q−1=1 Iteration 4: (Q0,Q−1)=(0,1) → A ← A + M: A = 0000 + 1101 = 1101. Shift (arithmetic): shift concatenated A,Q,Q−1: 110111001 >> 1 → 111011100. Final A=1110 Q=1110. Result concat(A,Q) = 11101110_2 = two's-complement −18. Final answer: −18 (11101110₂).
Example 3 — Trace showing reduction of operations (short theoretical) Show multiplier Q = 01111110 (a run of six 1s): ordinary bitwise method requires adding shifted M for each 1 (six adds). Booth sees transitions at 0→1 and 1→0 and does two operations: add M shifted at start and subtract M shifted at end — only two adds/subtracts total. Draw the binary and show two actions. (This is an exam-style short answer to explain efficiency.)
Common mistakes
- Neglecting sign-extension when adding/subtracting M (A must be n-bit and additions must be in n-bit two's-complement semantics).
- Applying Booth's rules but using M that is not in two's-complement or using incorrect −M calculation (~M + 1 mistakes).
- Using too-small register widths and ignoring that the exact product needs 2n bits (overflow silently ignored).
For your exam
Typical question types:
- Definitions: define Booth's algorithm, arithmetic right shift, two's-complement negation.
- Short note: explain why Booth's algorithm reduces the number of additions for runs of ones; include the (Q0,Q−1) table and a small diagram of A/Q/Q−1.
- Derivation: prove correctness for one iteration by algebra: show that A,Q update implements the intended arithmetic shift and partial product accumulation.
- Numericals: trace Booth's algorithm for given small n (n = 4 or 8) with signed operands; provide final 2n-bit product.
- Diagrams: draw registers A,Q,Q−1 and control-flow for (Q0,Q−1) rules.
What a full-marks answer includes:
- Clear definitions of terms (multiplicand, multiplier, product), exact specification of registers and widths.
- The action table for (Q0,Q−1) and an explanation why each case corresponds to add/subtract/do-nothing.
- A correct step-by-step trace for a numerical example, showing intermediate A,Q,Q−1 after each iteration and final 2n-bit product with interpretation in decimal.
- A short explanation of advantages and assumptions (two's-complement, need for arithmetic shift, 2n-bit product).
Quick check
- What pair of bits does Booth's algorithm examine each iteration?
- For n-bit two's-complement operands, how many iterations does Booth run?
- In Booth, which action corresponds to (Q0,Q−1) = (1,0)? Answers: 1) (Q0, Q−1). 2) n iterations. 3) A ← A − M (subtract multiplicand), then arithmetic right shift.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?