Booth's Multiplication

Multiply signed numbers with only add, subtract, and arithmetic shift by recoding runs of 1s.

Booth's algorithm multiplies two signed (two's complement) numbers using only operations the hardware already has: add, subtract, and arithmetic shift. Its trick is to treat a run of 1s in the multiplier as the *difference* of two numbers — subtracting once where the run starts and adding once where it ends — instead of adding the multiplicand for every single 1 bit. It also handles negative operands automatically, with no sign-fixing afterward.

The recoding rule

Booth's keeps the product in a register A and the multiplier in Q, plus one extra bit Q-1 (initially 0) sitting just to the right of Q. Each step it inspects the pair Q0 Q-1 — the multiplier's current low bit and the bit that fell off last time — to choose an action, then does an arithmetic right shift of the combined A : Q : Q-1 register.

1Q0 Q-1 = 00 -> no add/subtract (inside a run of 0s), just shift.
2Q0 Q-1 = 01 -> end of a run of 1s: A = A + M, then shift.
3Q0 Q-1 = 10 -> start of a run of 1s: A = A - M, then shift.
4Q0 Q-1 = 11 -> inside a run of 1s, just shift.
5After the chosen add/subtract, arithmetic-shift-right A:Q:Q-1, and repeat for n bits.

Why a run of 1s becomes subtract-then-add

A block of 1s from bit j up to bit k equals 2^(k+1) - 2^j (e.g. 0111 = 1000 - 0001). So instead of k - j + 1 separate additions, Booth's subtracts the multiplicand at the low end of the run and adds it once at the high end. Long runs of identical bits cost just two operations.

Multiply M = 2 (0010) by Q = -3 (1101).  n = 4.
Arithmetic shift right (ASR) copies the sign bit in.

  step   action          A      Q     Q-1
  init                   0000   1101   0
   1   10: A = A - M     1110   1101   0
       ASR               1111   0110   1
   2   01: A = A + M     0001   0110   1
       ASR               0000   1011   0
   3   10: A = A - M     1110   1011   0
       ASR               1111   0101   1
   4   11: shift only    1111   0101   1
       ASR               1111   1010   1

  product A:Q = 1111 1010 = -6     (2 × -3 = -6)

It must be an arithmetic shift

The shift after each step copies the sign bit back in (a logical shift, which feeds in 0, would corrupt negative partial products). Getting this right is what lets Booth's work directly on two's complement operands of either sign.

OperationTimeSpace

Booth's multiply · one add/sub at most per step; signed-safeO(n) iterationsO(n) registers

Check yourself

Examining the pair Q0 Q-1, which value triggers A = A - M (the start of a run of 1s)?