GATE CS 2025 Set 2 Q22 — Computer Arithmetic

In Booth's multiplication algorithm, the multiplier $Q$ is scanned from right to left, starting with an implicit bit $Q_{-1} = 0$. For each bit pair $Q_i Q_{i-1}$ (for $i = 0$ to $n-1$):

• If $Q_i Q_{i-1} = 01$, an addition operation ($A \leftarrow A + M$) is performed.
• If $Q_i Q_{i-1} = 10$, a subtraction operation ($A \leftarrow A - M$) is performed.
• If $Q_i Q_{i-1} = 00$ or $11$, no addition or subtraction is performed.

Given the multiplier $Q = 1010010010101010$. Appending $Q_{-1} = 0$ at the right end, we analyze the bit pairs $(Q_i, Q_{i-1})$ from right to left:

Thus, the total number of addition and subtraction operations to be performed is 13.