GATE 2025 CS2 Q.32: solution and answer

GATE 2025 · CS2Q.32 · 1 mark · NAT

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)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The total number of addition/subtraction operations Booth's algorithm performs while multiplying M by Q is $13$ .

Official answer: 13Source: Official answer key, GATE 2025 CS2 (IIT Roorkee)

Booth's algorithm runs for $n = 16$ cycles (Q is 16 bits). At each cycle it inspects the pair $(Q_{0}, Q_{- 1})$ , where $Q_{- 1}$ starts at $0$ : pair $01$ adds M to the partial product, pair $10$ subtracts M, and pair $00$ or $11$ does no arithmetic (only an arithmetic right shift).
Since $Q_{- 1}$ at cycle $k$ is just the original bit $Q_{k - 1}$ (shifted in from the previous cycle), the pair examined at cycle $k$ is $(Q_{k}, Q_{k - 1})$ for $k = 0, \dots, 15$ , with $Q_{- 1} = 0$ . So the number of add/subtract operations equals the number of $0 \to 1$ or $1 \to 0$ transitions scanning Q's bits from LSB to MSB with an extra leading $Q_{- 1} = 0$ — M is irrelevant to this count.
Q = 1010 0100 1010 1010 (MSB to LSB), so reading off individual bits: $Q_{15} = 1, Q_{14} = 0, Q_{13} = 1, Q_{12} = 0, Q_{11} = 0, Q_{10} = 1, Q_{9} = 0, Q_{8} = 0, Q_{7} = 1, Q_{6} = 0, Q_{5} = 1, Q_{4} = 0, Q_{3} = 1, Q_{2} = 0, Q_{1} = 1, Q_{0} = 0$ .
Prefixing $Q_{- 1} = 0$ gives the sequence $Q_{- 1}, Q_{0}, Q_{1}, \dots, Q_{15} = 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1$ .
Comparing each adjacent pair $(Q_{i}, Q_{i - 1})$ for $i = 0$ to $15$ : i=0:(0,0) same; i=1:(1,0) diff; i=2:(0,1) diff; i=3:(1,0) diff; i=4:(0,1) diff; i=5:(1,0) diff; i=6:(0,1) diff; i=7:(1,0) diff; i=8:(0,1) diff; i=9:(0,0) same; i=10:(1,0) diff; i=11:(0,1) diff; i=12:(0,0) same; i=13:(1,0) diff; i=14:(0,1) diff; i=15:(1,0) diff.
Same-pairs occur at $i = 0, 9, 12$ (3 positions, pure shifts, no arithmetic); every other position ( $i = 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 15$ ) is a diff-pair, giving $16 - 3 = 13$ transitions.
Total addition + subtraction operations $= 13$ .

KEY IDEA

In Booth's algorithm, at each of the $n$ cycles the ALU performs add M, subtract M, or nothing, based on the pair $(Q_{0}, Q_{- 1})$ (with $Q_{- 1}$ starting at 0): pair $01$ adds M, pair $10$ subtracts M, and $00$ or $11$ do nothing except an arithmetic shift. Because $Q_{- 1}$ at cycle $k$ is just the original bit $Q_{k - 1}$ (shifted in from the previous cycle), the total add/subtract count equals the number of bit-to-bit transitions ( $0 \to 1$ or $1 \to 0$ ) when scanning the multiplier Q from its LSB toward its MSB, with an extra leading $Q_{- 1} = 0$ prepended — independent of the multiplicand M.

WATCH OUT FOR

Assuming the number of add/subtract operations depends on the multiplicand M, or forgetting to prepend the initial $Q_{- 1} = 0$ bit — omitting it undercounts the transition at $i = 0$ and gives $12$ instead of $13$ .

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 5 ALU & control unit questions, with notes

GATE 2025 CS2 Q.32: solution and answer

Answer and solution

More ALU & control unit questions