Booth’s Algorithm is easy to memorise as a 00/01/10/11 table but hard to execute correctly. One reversed pair, one logical shift, or one missed sign bit changes every later row. Start with zeroed registers, complete (+3) × (-5) in 4-bit two’s complement, and use a repeatable checking method. This is a signed-integer multiplication method in computer organisation, not a floating-point encoding method.
Booth’s Algorithm: the problem it solves and the registers it needs
Booth’s Algorithm multiplies signed two’s-complement integers. For an n-bit multiplication, it uses four working fields:
A, ann-bit accumulatorQ, then-bit multiplierM, then-bit multiplicandQ-1, a one-bit latch that remembers the previous multiplier bit
The algorithm makes exactly n decisions, each followed by an arithmetic right shift, even when A does not change.
Our running example uses n=4. The multiplicand is M=0011, which is +3, and the multiplier is Q=1011, which is -5 in 4-bit two’s complement. Initialise A=0000 and Q-1=0. The two’s complement of M is -M=1101. All additions in A remain four bits wide, so any carry beyond the register is discarded.
The bit pattern 1011 means -5 only because we are treating it as a 4-bit two’s-complement integer. An IEEE 754 word instead separates the sign, exponent, and fraction. See Floating point representation: encode and add in IEEE 754 if that representation needs a separate revision.
Booth’s Algorithm decision table and the combined arithmetic shift
Always read the decision pair in the order (Q0,Q-1). Here, Q0 is the current least-significant bit of Q.
Pair | Operation before shifting |
|---|---|
| No change to |
|
|
|
|
| No change to |
After the optional operation, arithmetic-right-shift [A,Q,Q-1] as one signed field. The old sign bit of A is copied into the new most-significant bit of A. The old A0 enters the most-significant bit of Q, and the old Q0 becomes the new Q-1. Shifting A and Q separately is not equivalent.
Check the first cycle. From [0000,1011,0], the pair is 10, so A=0000-0011=1101. Arithmetic-shifting [1101,1011,0] then gives [1110,1101,1].
Use Booth's Algorithm for GATE: Worked Trace, Op Counts as the compact reference for register setup, operation counting, and common GATE question formats. After that compact reference, audit the four-cycle (+3) × (-5) trace two ways, apply the transition rule to run recoding, and test the -8 edge case.
Booth’s Algorithm worked example: multiply +3 by -5 in four cycles
Keep each starting and post-shift state on one row to avoid confusing a shifted value with the next arithmetic result.
Cycle | Start | Start |
| Pair | Operation on | State after arithmetic right shift |
|---|---|---|---|---|---|---|
1 |
|
|
|
|
|
|
2 |
|
|
|
| No operation |
|
3 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
Cycle 1 subtracts M because the pair is 10, then shifts the combined register to [1110,1101,1]. Cycle 2 sees 11, so the accumulator stays 1110, but the shift still happens. Its post-shift state is [1111,0110,1].
Cycle 3 sees 01 and adds M. The full binary sum 1111+0011 produces a carry beyond the four-bit accumulator; after discarding that carry, A=0010. The combined shift produces [0001,0011,0]. Cycle 4 sees 10, so 0001-0011=1110, followed by the final state [1111,0001,1].
Stop after four cycles because n=4. Discard the helper bit Q-1, then join the final A and Q. The product is AQ=11110001.
Verify the result in binary and decimal
Decode 11110001 as an 8-bit two’s-complement number. Invert every bit to get 00001110, then add 1 to get 00001111, whose magnitude is 15. The original leading bit was 1, so the value is -15. Independently, (+3) × (-5) = -15.
Each input has four bits, but the complete product uses 2n=8 bits. Neither A nor Q alone is the product, and Q-1 is only a helper bit. A fast diagnostic also agrees: unlike operand signs require a negative result, and -15 is representable in eight signed bits.
Why Booth recoding compresses a run of 1 bits
The pair table detects transitions in the multiplier. When scanning from the appended Q-1=0, a 10 boundary begins a run of 1 bits and creates a subtraction at its low end. A 01 boundary ends the run and creates an addition at its high end. Pairs 00 and 11 sit inside unchanged regions.
For the 5-bit multiplier Q=01110, which represents +14, the low boundary at bit 1 contributes -2M. The high boundary at bit 4 contributes +16M. The middle of the run requires no arithmetic, so the recoded value is 16M-2M=14M.
This can reduce arithmetic operations for long runs of 1 bits, but it does not guarantee fewer operations for every pattern. Alternating bits such as 01010 create more transitions.
Booth’s Algorithm mistakes that corrupt the trace
The pair-order trap is the most common: 01 means add, while 10 means subtract. Write the mnemonic, “read current bit first, previous bit second.”
The shift creates another cluster of errors. Add or subtract before shifting, shift [A,Q,Q-1] together, and preserve the sign of A. In cycle 1, a logical shift would make A begin with 0; the correct arithmetic-shift result is A=1110.
Width and stopping rules matter too. Keep A, M, and Q at the declared width, run exactly n cycles, and return only AQ. There is also an important edge case: M=1000 means -8 in four bits, but its positive negation +8 cannot be represented in four bits. A robust implementation needs an extra working bit instead of silently reusing 1000 as -M. Do not mix Booth’s procedure with floating-point fields or sign-magnitude arithmetic.
How Booth’s Algorithm is tested in exam-style questions
Exam-style questions typically require one of five moves: choose the action for a pair, fill a missing register row, identify a logical shift error, count additions and subtractions, or decode the final AQ. Each can be checked from the pair rule, fixed-width arithmetic, and the combined shift.
Try one rapid check. If A=0101, Q=0110, Q-1=1, and M=0011, then (Q0,Q-1)=01. The next arithmetic step is A=0101+0011=1000 before any shift. Choosing subtraction means the pair has been reversed.
On rough paper, use five columns: cycle | pair | A after operation | A,Q,Q-1 after shift | cycles left. Check the expected sign and decimal product only after the final cycle; every intermediate decision should come from the current pair and fixed-width register state.
Use GATE CS Exam Preparation for the wider subject route, then use the GATE Test Series for structured test practice.
Booth’s Algorithm: the short version and next step
Initialise A=0 and Q-1=0. Inspect (Q0,Q-1), add for 01, subtract for 10, and do nothing for 00 or 11. Arithmetic-shift the combined register, repeat exactly n times, and read the final AQ.
For the anchor example, four cycles for 0011 × 1011 produce AQ=11110001, which is -15. Reproduce these post-shift states without looking back: [1110|1101|1], [1111|0110|1], [0001|0011|0], and [1111|0001|1].
That self-test is the immediate next action if Booth’s Algorithm is your only focus. For a broader, structured preparation route, use GATE Guidance by Sanchit Sir while keeping this register-checking habit.
