请问如何仅使用位移位和加法来进行乘法和除法？

Question

如何仅使用位移位和加法来进行乘法和除法？如何仅使用位移位和加法来进行乘法和除法？

Answer 1

要用加法和平移来乘，您需要将其中一个数分解为2的幂，如下所示：

21 * 5 = 10101_2 * 101_2             (Initial step)
       = 10101_2 * (1 * 2^2  +  0 * 2^1  +  1 * 2^0)
       = 10101_2 * 2^2 + 10101_2 * 2^0 
       = 10101_2 << 2 + 10101_2 << 0 (Decomposed)
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5                      (Same as initial expression)

(_2平均基数2)

正如你所看到的，乘法可以被分解成加、移和返回。这也是为什么乘法比位移位或加法更长的原因-在位数中它是O(n^2)而不是O(N)。真正的计算机系统(相对于理论计算机系统)有限的位数，因此乘法比加法和移位要花费恒定的时间倍数。如果我没记错的话，现代处理器，如果流水线正确的话，就可以通过干扰处理器中ALU(算术单位)的使用来实现与加法一样快的乘法。

Answer 2

x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k

您可以使用这些移位来执行任何乘法操作。例如：

x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)

要将一个数字除以非二次方，我不知道任何简单的方法，除非您想要实现一些低级逻辑，使用其他二进制操作并使用某种形式的迭代。