shift-and-add multiplication

Shift-and-add multiplication is the same long multiplication you learned for decimals, made trivial by binary having only the digits 0 and 1. To multiply by a decimal digit you must know a times table; to multiply by a binary digit you only ever multiply by 0 or by 1. So each step is just: look at one bit of the multiplier — if it is 1, add a shifted copy of the multiplicand into a running total; if it is 0, add nothing. Shift the position over by one and repeat. No multiplication table is needed at all.

Step through 0b101 (5) times 0b011 (3). Bit 0 of the multiplier (5) is 1, so add the multiplicand 3 shifted by 0: total 3. Bit 1 is 0, so add nothing; total stays 3. Bit 2 is 1, so add 3 shifted left by 2 (which is 3 times 4 = 12): total 3 + 12 = 15, correct. In hardware this becomes a loop with a register for the accumulating product, an adder, and a shifter, repeated once per bit of the operand. An n-bit multiply takes about n add-and-shift steps, so it is straightforwardly correct but slow — roughly n cycles where an add is one.

This is the baseline every faster multiplier is measured against. Its honest weakness is exactly that it is sequential: each step depends on the previous running total, so a 64-bit multiply could take dozens of cycles if done literally one bit at a time. Two big ideas attack that: Booth's algorithm reduces the number of add steps (and handles signed numbers cleanly), and array or Wallace-tree multipliers do all the partial-product additions in parallel hardware instead of in a loop, trading area for speed.