---
title: "Booth multiplication algorithm and hardware"
subject: "Computer Organization and Architecture"
chapter: 5
key: "semester_5/computer_organization_and_architecture:booth-algorithm"
source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/booth-algorithm
site: BCT Engineering
---

# Booth multiplication algorithm and hardware

Computer Organization and Architecture · Chapter 5: Computer Arithmetic

- Asked in: 2078 Kartik, 4 marks; 2076 Chaitra, 5 marks; 2075 Asoj, 10 marks; 2072 Chaitra, 5 marks; 2072 Kartik, 4 marks; 2071 Chaitra, 4 marks; 2071 Shrawan, 5 marks; 2067 Asar (old course), 4 marks (asked 8 times)
- Video: [The Concept of Booth’s Algorithm](https://www.youtube.com/watch?v=meSn0UXmgac) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/booth-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-5

## Question

Explain Booth's multiplication algorithm for signed 2's complement numbers in detail, with hardware diagram and a suitable example.

## Short answer

Booth’s algorithm scans multiplier bits Q0 and Q-1: 10 subtracts M, 01 adds M, others do nothing; then arithmetic shift right A,Q,Q-1. For 7 (0111) × -3 (1101), n=4, final A:Q = 1110 1011 = -21. Product has 2n bits.

## Answer

Booth's algorithm multiplies two signed numbers in 2's complement form. It treats a run of 1s in the multiplier as (2^(j+1) - 2^i), so a run of 1s needs only one subtraction at the beginning and one addition at the end. This makes the multiplication of negative and positive numbers uniform, and it is faster when the multiplier has long runs of 1s.

#### Hardware
```text
              +-----------------+
              |  M (multiplicand)|
              +--------+--------+
                       v
        +-------[ n-bit Adder / Subtractor ]
        |                |
        v                v
   +---------+      +---------+    +----+
   |  A (acc)|----->|    Q    |----| Q-1|
   +---------+  ASR +---------+    +----+
     <-- Shift right (A, Q, Q-1) together -->
   Control logic looks at Q0 and Q-1, with a counter n
```
- **M:** multiplicand register. **Q:** multiplier register (Q0 is the least significant bit).
- **A:** accumulator, initially 0; A and Q together hold the 2n-bit product at the end.
- **Q-1:** one extra flip-flop to the right of Q0, initially 0.
- **Counter:** set to n, the number of bits.

#### Algorithm
1. Initialise A = 0, Q-1 = 0, M = multiplicand, Q = multiplier, count = n.
2. Look at the pair (Q0, Q-1):
   - 00 or 11: no arithmetic.
   - 10: A = A - M (start of a run of 1s).
   - 01: A = A + M (end of a run of 1s).
3. Arithmetic shift right the combined A, Q, Q-1 (the sign bit of A is kept).
4. Decrement the count. If the count is not 0, go to step 2; else stop. The product is in A:Q.

#### Example: 7 × (-3), n = 4 bits
M = 7 = 0111, -M = 1001, Q = -3 = 1101 (2's complement of 0011).

| Step | A | Q | Q-1 | Q0 Q-1 | Operation |
|---|---|---|---|---|---|
| init | 0000 | 1101 | 0 | | A = 0, M = 0111 |
| 1 | 1100 | 1110 | 1 | 10 | A = A - M = 1001, then ASR |
| 2 | 0001 | 1111 | 0 | 01 | A = A + M = 0011, then ASR |
| 3 | 1101 | 0111 | 1 | 10 | A = A - M = 1010, then ASR |
| 4 | 1110 | 1011 | 1 | 11 | ASR only |

Product (A:Q) = 1110 1011 = **-21** (in 8-bit 2's complement). Check: 7 × (-3) = -21. 

ASR = arithmetic shift right of A, Q and Q-1 together.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does Booth's algorithm treat a run of 1s in the multiplier?
   A. Adds the multiplicand for every 1
   B. As a single subtraction at the start and an addition at the end of the run
   C. Ignores the run
   D. Shifts left for each 1
   Answer: B. A run of 1s equals 2^(j+1) - 2^i, so one subtract and one add replace many additions. (Key point: Idea of Booth's algorithm)

2. For (Q0, Q-1) = 10 and 01 what does Booth's algorithm do?
   A. 10: A = A + M; 01: A = A - M
   B. 10: A = A - M; 01: A = A + M
   C. Both do no operation
   D. Both shift left
   Answer: B. 10 marks the start of a run (subtract), 01 its end (add); 00 and 11 do nothing. (Key point: Action table)

3. Which shift is used after each step?
   A. Logical shift left
   B. Arithmetic shift right of A, Q, Q-1 keeping the sign bit
   C. Rotate left
   D. Logical shift right filling zero
   Answer: B. The sign must be preserved for signed numbers. (Key point: Shift type)

4. What is the result of 7 x (-3) in the example and where is it stored?
   A. +21 in A
   B. -21 as 1110 1011 in A:Q
   C. -3 in Q
   D. -21 in M
   Answer: B. After 4 steps A:Q = 1110 1011 = -21 in 8-bit 2's complement. (Key point: Example 7 x (-3))

## Related in Computer Organization and Architecture

- [Booth multiplication with hardware](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-hardware) — Computer Organization and Architecture, chapter 5
- [Booth multiplication of 9 × -3](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-9x-3) — Computer Organization and Architecture, chapter 5
- [Booth multiplication of -5 × -9](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-5x-9) — Computer Organization and Architecture, chapter 5, asked 5×
- [Booth multiplication of 5 × -6](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-5x-6) — Computer Organization and Architecture, chapter 5, asked 5×
- [Booth multiplication of -7 × -10](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-7x-10) — Computer Organization and Architecture, chapter 5, asked 5×
- [Booth multiplication of 10 × (-5)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-10x-5) — Computer Organization and Architecture, chapter 5, asked 5×

## Related in other subjects

- [Signed 1's complement addition of (-65)+(+15)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Aones-complement-addition-8bit) — Digital Logic, chapter 5
- [Algorithm for numbers divisible by 9 not 6](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-divisible-9-not-6) — Computer Programming, chapter 2