GATE 2025 CS (CS2) – Question 32
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
- GATE 2025 CS (CS2) Q49
- GATE 2024 CS (CS1) Q13
- GATE 2024 CS (CS2) Q14
- GATE 2023 CS Q45
- GATE 2022 CS Q41
- GATE 2020 CS Q39
All Number Representation and Floating Point Arithmetic questions →