11.13. Booth recoding

Booth recoding is an ingenious way to make multiplication more efficient. The whole thing is based on the observation that constant coefficient multipliers are most efficient when the constant operand contains long strings of nulls. Booth recoding also makes multiplication extremely efficient when there are long strings of 1’s.