Booth's Algorithm for GATE: Signed Multiplication Traced Step by Step

Booth's algorithm multiplies signed 2's-complement integers without a separate sign-correction phase. GATE can ask for the final product, an intermediate register, or the number of add and subtract operations. Most wrong traces come from using a logical shift or forgetting the extra Q-1 bit.

Why Booth's algorithm exists

Ordinary binary shift-and-add multiplication examines multiplier bits and adds shifted copies of the multiplicand. Signed operands make that procedure awkward if the sign is handled separately.

Booth recoding handles positive and negative 2's-complement operands with the same rule. It also compresses a run of 1 bits into transitions at its boundaries. Instead of performing arithmetic for every 1, the algorithm reacts when a run begins or ends.

A Booth trace only reads cleanly if fixed-width signed values read cleanly. If a bit pattern like 1011 still feels ambiguous, revise number systems and base conversions before starting one.

Registers and the Booth rule

For an n-bit multiplication, maintain:

• M, the n-bit multiplicand

• Q, the n-bit multiplier

• A, the n-bit accumulator, initially zero

• Q-1, one extra bit, initially zero

At each step, inspect (Q0, Q-1), where Q0 is the least-significant bit of Q.

After that possible arithmetic action, perform one arithmetic shift right on the combined register A,Q,Q-1. The old sign bit of A is copied into the new sign position. Repeat exactly n times. The final 2n-bit product is A concatenated with Q.

The shift rule is not optional. A logical right shift inserts zero and destroys a negative partial product.

Fully worked Booth trace

Multiply M = 2 by Q = -5 using four bits.

 M =  2 = 0010
-M = -2 = 1110
 Q = -5 = 1011
 n = 4

The expected decimal product is 2 * (-5) = -10. Initialise A = 0000, Q = 1011, and Q-1 = 0.

Check each shift as one combined value. For step 1, the pre-shift bits are 1110 1011 0. Replicating the leading 1 and shifting every other bit one place gives 1111 0101 1. The later rows follow the same movement.

Step 3 is where the fixed width bites. 1111 + 0010 is really 10001, but the carry out of the four-bit accumulator is discarded, so A becomes 0001 and every register stays at n bits.

After four steps:

A,Q = 1111 0110

As an unsigned 8-bit pattern, 11110110 is 246. Because its sign bit is 1, its signed value is 246 - 256 = -10. This matches the direct decimal product, so the trace closes correctly.

Counting additions and subtractions

The number of arithmetic operations equals the number of 01 and 10 pairs among adjacent multiplier bits, reading Q from the least-significant end with the initial Q-1 = 0 appended on the right. A 00 or 11 pair costs a shift only.

For Q = 1011, inspect from the least-significant end:

(1,0) -> subtract
(1,1) -> no arithmetic
(0,1) -> add
(1,0) -> subtract

That is two subtractions and one addition, for 3 arithmetic operations. The four arithmetic-shift steps still occur whether or not a row performs an add or subtract.

For an all-zero multiplier, every pair is 00, so the arithmetic-operation count is 0. For an all-one negative multiplier such as 1111, the appended zero creates one 10 pair at the start, so the count is 1, not 0. An alternating pattern such as 0101 can cause arithmetic on every one of the n steps, giving the worst-case count n.

This transition method is faster than simulating full register contents when the question asks only for the operation count.

Traps GATE plants in Booth questions

• Perform an arithmetic right shift of the whole A,Q,Q-1 register, not separate logical shifts.

• Initialise Q-1 to zero and include it when selecting the action.

• Keep every register at exactly n bits. Discard carry beyond A after an add or subtract.

• Count the sign bit inside n; do not trace a magnitude-only width.

• Interpret the final A,Q as a 2n-bit signed 2's-complement value.

• Apply the arithmetic action before the shift on each step.

About 1,700 COA questions in the KnowledgeGate question bank cover signed representation, Booth multiplication and operation-count variants. The COA number-representation and floating-point MCQs are a useful companion when sign extension or fixed-width interpretation is the weak point.

How GATE tests the trace

A stem may ask for the final product, the contents of A after a specified step, or the number of additions and subtractions. Build a row with the examined pair, action, and post-shift registers. Mixing pre-shift and post-shift values in one row is a common source of apparently random errors.

For exact year-specific wording, confirm the official GATE portal run by the organising IIT for that cycle. The GATE category collects the wider preparation route across the CS papers.

Short version and next step

Inspect (Q0,Q-1): 00 and 11 shift, 01 adds M, and 10 subtracts M. Then arithmetic-shift the combined registers and repeat n times. Count arithmetic operations by counting the corresponding bit transitions with the appended zero.

Now trace M = -3 by Q = -5 at n = 4 on paper, with both operands negative. The registers must close at A,Q = 0000 1111, which is 15; if they do not, the arithmetic shift is the first thing to check. Then use GATE Guidance by Sanchit Sir to drill signed-arithmetic sets until every register row is auditable.