Booth's Multiplication Algorithm

Multiplication with only add and shift

On paper you multiply by writing a shifted copy of the multiplicand for every 1 in the multiplier and adding them up. Hardware can do the same with an adder and a shifter. Booth’s algorithm (Andrew Booth, 1950) improves on it in two ways:

1. It works directly on signed (two’s complement) numbers — no special cases for negatives.
2. A run of 1s like 0111 1100 needs only one subtraction and one addition, not one addition per 1.

The idea: runs of 1s

0111 = 8 − 1. So M × 0111 = M × 8 − M × 1: subtract M at the start of the run of 1s and add it (shifted) just after the end. Reading Q from right to left, a pair of neighbouring bits tells you where you are:

After each round, arithmetic shift right the combined A, Q, Q₋₁ (copy the sign bit of A).

The registers

Worked example: 7 × (−3)

M = 0111, −M = 1001, Q = 1101 (−3).

Result A:Q = 1110 1011 = −21 ✓

Code

def booth(m, q, n=4):
    mask = (1 << n) - 1
    A, Q, q_1 = 0, q & mask, 0
    M = m & mask
    for _ in range(n):
        pair = (Q & 1, q_1)
        if pair == (1, 0):
            A = (A - M) & mask
        elif pair == (0, 1):
            A = (A + M) & mask
        # arithmetic shift right of A:Q:Q-1
        q_1 = Q & 1
        Q = ((Q >> 1) | ((A & 1) << (n - 1))) & mask
        A = (A >> 1) | (A & (1 << (n - 1)))      # keep the sign bit
    result = (A << n) | Q
    if result & (1 << (2 * n - 1)):              # interpret as signed 2n-bit
        result -= 1 << (2 * n)
    return result

print(booth(7, -3))    # -21
print(booth(-5, -6))   # 30

Common mistakes

• Doing a logical shift (filling with 0) instead of an arithmetic shift.
• Forgetting to shift Q₀ into Q₋₁ and A’s lowest bit into Q.
• Reading the result from A alone — the product is A:Q together.
• Using M = −2ⁿ⁻¹ (e.g. −8 with 4 bits): −M doesn’t fit in n bits, so A needs one extra bit.