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)
Answer
13
Explanation
Booth's algorithm looks at each multiplier bit \(Q_i\) together with the bit to its right, \(Q_{i-1}\), taking \(Q_{-1} = 0\). The pair 10 subtracts M, the pair 01 adds M, and 00 or 11 only shifts. So the number of operations is the number of adjacent bit pairs that differ once a 0 is appended to Q; the multiplicand M plays no part.
Q with the extra bit is 1010 0100 1010 1010 0. Of its 16 adjacent pairs, only 3 are equal (the three 00 pairs). The other 13 each cost one operation: 7 subtractions (pair 10) and 6 additions (pair 01).
Answer: 13