Booth’s Algorithm MCQs: 10 Solved Recoding and Multiplication Questions

Booth questions are usually lost on pair direction, the appended q_-1 = 0, signed two’s-complement width, or the difference between radix-2 and radix-4 recoding, not on multiplication itself. The relevant Booth’s algorithm skills are recognition, signed decoding, recoding, operation counts and partial products. Attempt each before opening the answer. Keep a full paper trace for Questions 3, 8 and 9. If pair direction or shifts are unclear, revisit the Booth’s Algorithm lesson.

Booth’s algorithm rules to use in every question

For radix-2 Booth recoding, use this table:

The first bit is the current multiplier bit, the second is the previous lower bit, and the initially appended bit is q_-1 = 0. Every cycle ends with an arithmetic right shift. However, an additions/subtractions question counts only 01 and 10 transitions.

For Q = 1101, the LSB-first pairs are q0q-1 = 10, q1q0 = 01, q2q1 = 10, q3q2 = 11. They mean subtract, add, subtract, no arithmetic, so the count is one addition plus two subtractions. Always retain the stated width: 11101 is -3 at 5 bits, while 1100 is -4 at 4 bits.

Booth’s algorithm basics and signed-register interpretation

Question 1: identify what Booth’s algorithm does

BPSC 2024, PGT Tier-3

What is Booth’s algorithm used for?

A. Binary to decimal conversion
B. Decimal to binary conversion
C. Binary multiplication
D. More than one of the above
E. None of the above

Answer: C. Binary multiplication. Booth’s algorithm multiplies signed binary numbers represented in two’s complement. It recodes runs in the multiplier into additions, subtractions and arithmetic shifts; it is not a base-conversion procedure.

Question 2: decode two signed registers before multiplying

Coal India 2020

The multiplicand register and multiplier register of a hardware circuit implementing Booth's algorithm hold (11101) and (1100) respectively. The result shall be:

A. 812₁₀
B. -812₁₀
C. -12₁₀
D. 12₁₀

Answer: D. 12₁₀. At 5-bit width, invert 11101 and add one: 00010 + 1 = 00011, so it represents -3. At 4-bit width, 1100 represents -4. Therefore (-3) x (-4) = +12. Reading either pattern as unsigned gives the wrong operands.

For a register trace, use 4-bit working registers: M = 1101 (-3), -M = 0011 (+3), A = 0000, Q = 1100 (-4), Q_-1 = 0.

The final AQ = 00001100, which is 12.

Recoding negative multipliers and spotting efficient bit patterns

Question 3: recode -57 with signed Booth digits

GATE 2005, Information Technology. Open the source question.

Using Booth's Algorithm for multiplication, the multiplier -57 will be recoded as

A. 0 -1 0 0 1 0 0 -1
B. 1 1 0 0 0 1 1 1
C. 0 -1 0 0 1 0 0 0
D. 0 1 0 0 -1 0 0 1

Answer: A. 0 -1 0 0 1 0 0 -1. The 8-bit two’s-complement form of -57 is 11000111. After appending q_-1 = 0, the LSB-first pairs are 10, 11, 11, 01, 00, 00, 10, 11. Their digits are -1, 0, 0, +1, 0, 0, -1, 0. Reverse that list for the option’s MSB-to-LSB display. Audit it numerically: -2^6 + 2^3 - 2^0 = -64 + 8 - 1 = -57.

Question 4: choose the multiplier with the fewest transitions

Consider the following pattern of multiplier:
(a) 010101010101 (b) 111111111111 (c) 1111100111000
Which of the above string will give best performance for Booth's multiplication algorithm?

A. Only (a)
B. Only (b)
C. Only (c)
D. Both (b) & (c)

Answer: B. Only (b). With the appended zero, pattern (a) alternates and causes 12 arithmetic actions. Pattern (b) is one uninterrupted run of ones and causes only the first LSB-side action. Pattern (c) causes three actions. Booth recoding rewards long runs, not a multiplier’s unsigned size.

Count additions and subtractions from multiplier transitions

Question 5: count operations for Q = 1101

UPLT 2026

If the multiplier Q is 1101 (-3 in decimal) and 4 bit registers are in use, then in Booth's technique for multiplication the number of addition and subtractions required are:

A. 1 addition and 2 subtractions
B. 2 additions and 1 subtraction
C. 1 addition and 1 subtraction
D. 0 addition and 2 subtractions

Answer: A. 1 addition and 2 subtractions. Scanning from the LSB gives 10, 01, 10, 11, meaning subtract, add, subtract, no arithmetic. That is one 01 pair and two 10 pairs.

Question 6: count operations in a 16-bit multiplier

Indian Space Research Organization 2009

The two numbers given below are multiplied using the Booth's algorithm Multiplicand: 0101 1010 1110 1110 Multiplier: 0111 0111 1011 1101 How many additions/subtractions are required for the multiplication of the above two numbers?

A. 6
B. 8
C. 10
D. 12

Answer: B. 8. The multiplicand bits do not affect this count. In multiplier 0111 0111 1011 1101, additions (01) occur at i = 1, 6, 11, 15; subtractions (10) occur at i = 0, 2, 7, 12. That is 4 + 4 = 8 arithmetic operations.

Question 7: audit a 12-bit transition count

Consider the following Booth’s multiplication: Multiplicand: 1011 0111 1111 Multiplier: 0101 1100 1001 Which of the following represents the number of arithmetic operations are required in the multiplication?

A. 5
B. 6
C. 7
D. 8

Answer: D. 8. For multiplier 0101 1100 1001, additions (01) occur at i = 1, 4, 9, 11, while subtractions (10) occur at i = 0, 3, 6, 10. The other four pairs are 00 or 11, so four additions plus four subtractions gives eight. Counting ones instead of transitions does not solve this question.

GATE NAT: audit all 16 Booth pairs without skipping a boundary

Question 8: count 13 operations in the GATE 2025 multiplier

GATE 2025, Set 2. Open the source 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)

None. This is a NAT question.

Answer: 13. Append q_-1 = 0 to Q = 1010 0100 1010 1010. The six 01 pairs are at i = 2, 4, 6, 8, 11, 14; the seven 10 pairs are at i = 1, 3, 5, 7, 10, 13, 15. Hence 6 additions + 7 subtractions = 13 operations. At i = 0, q0 = 0 beside the appended zero gives 00, so there is no operation. The sign-side transition at i = 15 still counts.

Bit-pair partial products and the final two's-complement product

Question 9: complete a radix-4 bit-pair recoding table

GATE 2006, Information Technology. Open the source question.

When multiplicand Y is multiplied by multiplier X = xₙ₋₁xₙ₋₂ ....x₀ using bit-pair recoding in Booth's algorithm, partial products are generated according to the following table.

The partial products for rows 5 and 8 are

A. 2Y and Y
B. -2Y and 2Y
C. -2Y and 0
D. 0 and Y

Answer: C. -2Y and 0. This is modified radix-4 Booth recoding, whose triplet rule is d = -2x_(i+1) + x_i + x_(i-1). For row 5, triplet 100 gives d = -2, so the partial product is -2Y. For row 8, triplet 111 gives d = -2 + 1 + 1 = 0, so its partial product is 0. Do not apply the radix-2 pair table from Questions 3 to 8 to this radix-4 triplet table.

Question 10: convert the signed product back to eight bits

UPLT 2026

Let A = 1111 1010 and B = 0000 1010 be two 8-bit 2's complement numbers. What will their product in 2's complement be?

A. 1101 0101
B. 1010 0101
C. 1100 0100
D. 1001 1100

Answer: C. 1100 0100. Decode A = 1111 1010 as -6 and B = 0000 1010 as +10, giving -60. In the 8-bit width used by the options, +60 = 0011 1100. Invert it to 1100 0011, then add one to get 1100 0100. Decoding that result independently gives 196 - 256 = -60, confirming both sign and magnitude.

Diagnose the miss and choose the next practice step

The key skills are signed representation, recoding and runs, pair direction, transition counting, radix-2 and radix-4 recoding, and requested-width conversion.

Use this correction checklist:

1. Write the multiplier width.

2. Append q_-1 = 0.

3. Scan every bit in order and record its pair.

4. Count only 01 and 10. For a final product, verify sign and decimal magnitude separately.

Redo Questions 2, 3, 8 and 9 without the answers. Use Booth’s Algorithm Explained: Signed Binary Multiplication, Full Trace and Exam Traps when the four-cycle register trace is unclear; return here to test recoding, transition counts, radix-4 partial products and width checks. Repair signed representation with Number Systems and Base Conversions Explained.

Continue with GATE Guidance by Sanchit Sir for a structured GATE sequence, or CS Fundamentals for Exams & Placements for broader computer-organisation revision.