GATE CS Mastery
Cheat sheets

GATE CS 2025 Set 2 · Computer Organization and Architecture

Question 32

NAT1 markNo negative markingEasy (estimate)

Question

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)

Official answer and solution
Official answer
13
From
Official GATE 2025 answer key

Solution

Append Q−1=0Q_{-1} = 0 to the right of multiplier QQ and count the number of 0→10 \rightarrow 1 and 1→01 \rightarrow 0 bit transitions across adjacent bit pairs (Qi,Qi−1)(Q_i, Q_{i-1}).

In Booth's multiplication algorithm, an addition or subtraction is performed exclusively depending on the bit transitions in the multiplier QQ (with an initial bit Q−1=0Q_{-1} = 0 appended to the right of the LSB):

QiQi−1=1010 0100 1010 1010 0Q_i Q_{i-1} = \texttt{1010 0100 1010 1010}\,\texttt{0}

Writing out all 16 adjacent pairs (Qi,Qi−1)(Q_i, Q_{i-1}) from MSB to LSB:

  1. 10 (subtraction)
  2. 01 (addition)
  3. 10 (subtraction)
  4. 00 (no operation)
  5. 01 (addition)
  6. 10 (subtraction)
  7. 00 (no operation)
  8. 01 (addition)
  9. 10 (subtraction)
  10. 01 (addition)
  11. 10 (subtraction)
  12. 01 (addition)
  13. 10 (subtraction)
  14. 01 (addition)
  15. 10 (subtraction)
  16. 00 (no operation)

Out of 16 steps, 33 pairs are 00 (no operation) and the remaining 16−3=1316 - 3 = 13 pairs are 01 or 10. Thus, a total of 1313 addition and subtraction operations are performed.

Final answer

13

Common trap

Examining M instead of Q, or forgetting to append Q−1=0Q_{-1} = 0 at the right end of Q.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question
32 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.