Reversing multiplication

곱셈도 리버싱 대상이 될 수 있는건 처음알았네... -_-

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 oflogical 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*[(2^2+1)*2]
(x << 3) + (x << 1) # Here x*10 => x*[(2^3+2)]

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,^[4] 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.