Booth's multiplication algorithm

Booth's multiplication algorithm multiplies two signed binary numbers written in two's complement notation. It was invented in 1950 by Andrew Donald Booth while he was doing crystallography research at Birkbeck College in London, and it remains of interest in the study of computer architecture. The algorithm examines adjacent pairs of bits of the multiplier, including an implicit zero bit below the least significant bit. Where the two bits of a pair are equal, the product accumulator is left unchanged; where the current bit is 0 and the bit below it is 1, the multiplicand times a power of two is added, and in the opposite case it is subtracted, so the final accumulator holds the signed product. It is often described as replacing each string of 1s in the multiplier by a high-order +1 and a low-order -1 at the ends of the string. A typical implementation repeatedly adds one of two precomputed values to the product and then shifts it right arithmetically, and the basic form needs an extra bit when the multiplicand is the most negative representable number, because negating that value overflows.