Booth's Algorithm in COA: Flowchart, Examples & Step-by-Step Guide

Binary multiplication sounds straightforward until you introduce negative numbers. The standard shift-and-add method works cleanly for positive operands, but signed binary multiplication in two's complement requires special handling - and doing it naively leads to incorrect results.

Booth's Algorithm solves this elegantly. Proposed by Andrew D. Booth in 1951, it is a hardware-efficient method for multiplying two signed binary integers in two's complement representation. Rather than treating every bit of the multiplier identically, Booth's algorithm inspects pairs of adjacent bits and decides whether to add, subtract, or do nothing - dramatically reducing the number of arithmetic operations needed, especially when the multiplier contains long strings of consecutive 0s or 1s.

This guide covers everything you need for exams and interviews: what Booth's algorithm is, the hardware register configuration, the complete flowchart, the Qn/Qn+1 decision rules, two fully worked step-by-step examples (7×3 and -5×-7), best and worst case analysis, a C++ implementation, and GATE-specific tips. Understanding ACID properties in DBMS or other COA topics becomes more coherent once you have this foundational arithmetic algorithm firmly in place.

Who This Guide Is For

What is Booth's Algorithm?

Booth's algorithm is a multiplication algorithm that multiplies two signed binary integers expressed in two's complement notation. It works by scanning the multiplier bit by bit - specifically examining the current bit (Qn) and the previous bit (Qn+1) together - and deciding whether to add the multiplicand, subtract the multiplicand, or take no action before performing an arithmetic right shift.

The core insight behind the Booth multiplication algorithm is that a string of consecutive 1s in the multiplier does not need individual additions. For example, a multiplier pattern like 0111100 can be rewritten as 2^5 - 2^2, converting four additions into one subtraction and one addition. The algorithm exploits this automatically by detecting transitions between 0s and 1s in the multiplier bit string.

The algorithm was originally designed for desk calculators where shifting was faster than adding. In modern computer architecture, it is important because it handles both positive and negative signed numbers in two's complement without any special-case logic for the sign - the same algorithm works for all combinations of positive and negative operands.

Hardware Register Configuration

Before walking through the algorithm steps, it is essential to understand the hardware registers involved. Booth's algorithm in computer architecture uses five key components that work together in each iteration.

Booth's Algorithm Flowchart

The Booth algorithm flowchart describes the decision and operation sequence for each of the n iterations. The key decision point is the (Qn, Qn+1) bit pair - the least significant bit of QR and the appended flip-flop. Each combination maps to a specific arithmetic operation before the mandatory arithmetic right shift.

The Qn/Qn+1 Decision Rules

The entire logic of Booth's algorithm rests on four possible combinations of the two bits (Qn, Qn+1). These bit pairs represent transitions in the multiplier bit string - the algorithm detects the beginning and end of runs of 1s and acts accordingly.

Booth's Algorithm Steps

Booth's Algorithm Example 1: 7 × 3 (Positive Numbers)

Let us start with a positive example to verify the algorithm works for standard cases before moving to negative numbers.

Given: Multiplicand M = 7 = 0111, Multiplier Q = 3 = 0011, n = 4 bits Setup:

• BR = 0111 (multiplicand = 7)
• BR's 2's complement (BR'+1) = 1001 (used for subtraction)
• QR = 0011 (multiplier = 3)
• AC = 0000, Qn+1 = 0, SC = 4
• Expected result: 7 × 3 = 21 = 00010101 in 8-bit binary

Result: Product = [AC | QR] = 0001 0101 = 00010101

Converting 00010101 from binary to decimal: 16 + 4 + 1 = 21 ✓

The sign bit (MSB of AC) is 0 - confirming a positive result, as expected for 7 × 3 = 21.

Booth's Algorithm Example 2: -5 × -7 (Negative Numbers)

This is the classic GATE example that tests whether the algorithm correctly handles two negative operands. The result should be positive (+35).

Given: Multiplicand M = -5, Multiplier Q = -7, n = 4 bits

Converting to 4-bit two's complement:

• +5 = 0101, so -5 = 1011 (BR = 1011)
• BR's 2's complement (BR'+1) = 0101 (used when subtracting BR)
• +7 = 0111, so -7 = 1001 (QR = 1001)
• AC = 0000, Qn+1 = 0, SC = 4
• Expected result: (-5) × (-7) = +35 = 00100011 in 8-bit binary

Result: Product = [AC | QR] = 0010 0011 = 00100011

Converting 00100011 from binary to decimal: 32 + 2 + 1 = 35 ✓

The sign bit (MSB of AC) is 0 - confirming a positive result, as expected for (-5) × (-7) = +35.

Arithmetic Shift Right vs Logical Shift Right

One of the most commonly confused points in Booth's algorithm is the type of right shift used. This confusion is also a frequent source of GATE exam errors.

Best Case and Worst Case Analysis

C++ Implementation of Booth's Algorithm

Applications of Booth's Algorithm

Advantages and Limitations

Conclusion

Booth's algorithm is one of the most elegant results in computer arithmetic. By treating multiplication as a problem of detecting transitions between 0s and 1s in the multiplier, it converts a complex multi-case signed multiplication into a uniform procedure that handles all sign combinations correctly with no special cases.

The three things to take away: first, the (Qn, Qn+1) bit pair is the entire decision engine of the algorithm - 10 means subtract, 01 means add, 00 and 11 mean do nothing. Second, the arithmetic shift right is mandatory and non-negotiable - using a logical shift right corrupts the sign and produces wrong results. Third, the best case is a multiplier with long runs of identical bits (all 0s or all 1s); the worst case is strictly alternating bits.

For GATE preparation, the key questions to practice are: multiplying two negative numbers, identifying best and worst case multipliers, and explaining why overflow cannot occur. Board Infinity's complete guide on the structure of DBMS covers the broader Computer Organisation and Architecture context that Booth's algorithm sits within, including how the arithmetic unit fits into the overall CPU structure.

Frequently Asked Questions

Q1. What is Booth's algorithm? Booth's algorithm is a method for multiplying two signed binary integers in two's complement representation. It works by examining pairs of adjacent multiplier bits (Qn and Qn+1) and deciding whether to add the multiplicand, subtract it, or do nothing, followed by an arithmetic right shift. It handles all sign combinations correctly with a single uniform procedure.

Q2. What is the Booth multiplication algorithm used for? Booth's multiplication algorithm is used in hardware ALUs inside CPUs and microprocessors to perform fast, efficient signed integer multiplication. It is also used in DSP chips, GPU arithmetic units, cryptographic hardware, and embedded systems where efficient signed binary multiplication is required.

Q3. What is the Booth algorithm flowchart decision rule? The flowchart decision is based on the two-bit pair (Qn, Qn+1): if the pair is 10, subtract the multiplicand from AC; if 01, add the multiplicand to AC; if 00 or 11, take no arithmetic action. After any operation (or non-operation), perform an arithmetic right shift on [AC, QR, Qn+1] and decrement the sequence counter.

Q4. What is the difference between arithmetic shift right and logical shift right in Booth's algorithm? Arithmetic shift right (ashr) preserves the sign bit - the MSB of AC is copied into the vacated position after shifting. Logical shift right inserts a 0 into the MSB regardless of the original sign. Booth's algorithm always requires ashr. Using logical shift right corrupts the sign of the partial product and produces incorrect results for negative numbers.

Q5. What is the best case and worst case for Booth's algorithm? Best case is when the multiplier has long strings of consecutive identical bits (all 0s or all 1s) - only transitions trigger operations, so few adds/subtracts are needed. Worst case is when the multiplier alternates between 0 and 1 (e.g., 0101... or 1010...) - every bit pair is a transition, requiring an operation at every step - no improvement over naive multiplication.

Q6. Can Booth's algorithm overflow? No. Overflow cannot occur in Booth's algorithm because addition (01 case) and subtraction (10 case) always alternate - they never occur in consecutive iterations. This means the two numbers being added always have opposite signs, which mathematically prevents overflow in the partial products.

Q7. Where is the final product stored in Booth's algorithm? After all n iterations, the final 2n-bit product is stored in the combined [AC | QR] register pair. AC holds the most significant n bits (upper half) and QR holds the least significant n bits (lower half). The sign of the product is given by the MSB of AC.

Further Reading

Board Infinity Guides:

• Structure of DBMS with a Diagram
• DDL and DML Commands in SQL
• Functional Dependency in DBMS
• ACID Properties in DBMS with Examples
• Deadlock in DBMS

External Resources:

• GeeksforGeeks - Booth's Algorithm - the canonical reference for GATE preparation with register configurations and the official step table
• Booth Multiplication Algorithm Calculator - interactive step-by-step calculator to verify your manual Booth algorithm workings for any n-bit input
• MIT OpenCourseWare - Computer Architecture - foundational course materials covering binary arithmetic, ALU design, and the role of algorithms like Booth's in hardware design