Shift and Add
Historically, computers used a "shift and add" algorithm for multiplying small integers. Both base 2 long multiplication and base 2 peasant multiplication reduce to this same algorithm. In base 2, multiplying by the single digit of the multiplier reduces to a simple series of logical AND operations. Each partial product is added to a running sum as soon as each partial product is computed. Most currently available microprocessors implement this or other similar algorithms (such as Booth encoding) for various integer and floating-point sizes in hardware multipliers or in microcode.
On currently available processors, a bit-wise shift instruction is faster than a multiply instruction and can be used to multiply (shift left) and divide (shift right) by powers of two. Multiplication by a constant and division by a constant can be implemented using a sequence of shifts and adds or subtracts. For example, there are several ways to multiply by 10 using only bit-shift and addition.
((x << 2) + x) << 1 # Here x*10 => x* (x << 3) + (x << 1) # Here x*10 => x*In some cases such sequences of shifts and adds or subtracts will outperform hardware multipliers and especially dividers. A division by a number of the form or often can be converted to such a short sequence.
These types of sequences have to always be used for computers that do not have a "multiply" instruction, and can also be used by extension to floating point numbers if one replaces the shifts with computation of 2*x as x+x, as these are logically equivalent.
Read more about this topic: Multiplication Algorithm
Famous quotes containing the word shift:
“Ghosts, we hope, may be always with us—that is, never too far out of the reach of fancy. On the whole, it would seem they adapt themselves well, perhaps better than we do, to changing world conditions—they enlarge their domain, shift their hold on our nerves, and, dispossessed of one habitat, set up house in another. The universal battiness of our century looks like providing them with a propitious climate ...”
—Elizabeth Bowen (1899–1973)