Write a C program to perform signed binary multiplication of two integers using booth's algorithm

Explanation

Here is a concise explanation of the C++ program:

1. Purpose

This program implements Booth's Algorithm to perform signed binary multiplication of two 8-bit integers (in two's complement representation). It displays a detailed step-by-step table showing register states and prints the final decimal product.

2. Key Concepts

• Booth's Algorithm: An efficient algorithm that multiplies signed binary numbers by reducing the number of additions required.
• Bitwise Operations: Uses masking (&), bit-shifting (<<, >>), and bitwise OR/NOT (|, ~) to manipulate individual bits.
• Arithmetic Right Shift (ARS): Shifts bits to the right while preserving the Most Significant Bit (MSB) to maintain the correct sign (+/-).
• std::bitset: Formats integer values into clean binary strings for visual tracing.

3. Code Walkthrough

• Initialization (boothMultiplication):

  • A (Accumulator) and Q_minus_1 (extra bit) are initialized to 0.
  • BITS = 8 sets the working size to 8-bit signed integers.

• Main Loop (8 Iterations):

  • Inspect Bit Pair (Q0, Q_minus_1):
    • 1 0: Subtract $M$ from $A$ ($A = A - M$).
    • 0 1: Add $M$