The GATE Grind

GATE 2025 CS (CS2) – Question 32

Digital Logic · Number Representation and Floating Point Arithmetic · 1 mark · Numerical answer

The following two signed 2's complement numbers (multiplicand M and multiplier Q) are being multiplied using Booth's algorithm:

M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010

The total number of addition and subtraction operations to be performed is ___________. (Answer in integer)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 13

Explanation

In Booth's algorithm, scan the multiplier $Q$ from the least significant bit, with an extra bit $Q_{-1}=0$ on the right. At each position look at the pair $(Q_i,Q_{i-1})$:
- $(0,1)$: **add** the multiplicand.
- $(1,0)$: **subtract** the multiplicand.
- $(0,0)$ or $(1,1)$: no operation, only a shift.

So the number of add/subtract operations equals the number of places where adjacent bits (including the appended $Q_{-1}=0$) **differ**.

Write $Q$ followed by the appended bit: $1010010010101010\,\mathbf{0}$.

The 16 adjacent pairs, read left to right, are
$10,\ 01,\ 10,\ 00,\ 01,\ 10,\ 00,\ 01,\ 10,\ 01,\ 10,\ 01,\ 10,\ 01,\ 10,\ 00.$
Exactly three of them are $00$ (no operation). The other $16-3=13$ pairs differ, each causing one addition or subtraction.

Total add/subtract operations $=\mathbf{13}$.

More Number Representation and Floating Point Arithmetic questions

All Number Representation and Floating Point Arithmetic questions →