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

Question

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

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

Answer 1

要用加法和平移来乘，您需要将其中一个数分解为2的幂，如下所示：21&nbsp;*&nbsp;5&nbsp;=&nbsp;10101_2&nbsp;*&nbsp;101_2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Initial&nbsp;step) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;10101_2&nbsp;*&nbsp;(1&nbsp;*&nbsp;2^2&nbsp;&nbsp;+&nbsp;&nbsp;0&nbsp;*&nbsp;2^1&nbsp;&nbsp;+&nbsp;&nbsp;1&nbsp;*&nbsp;2^0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;10101_2&nbsp;*&nbsp;2^2&nbsp;+&nbsp;10101_2&nbsp;*&nbsp;2^0&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;10101_2&nbsp;<<&nbsp;2&nbsp;+&nbsp;10101_2&nbsp;<<&nbsp;0&nbsp;(Decomposed) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;10101_2&nbsp;*&nbsp;4&nbsp;+&nbsp;10101_2&nbsp;*&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;10101_2&nbsp;*&nbsp;5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;21&nbsp;*&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Same&nbsp;as&nbsp;initial&nbsp;expression)(_2平均基数2)正如你所看到的，乘法可以被分解成加、移和返回。这也是为什么乘法比位移位或加法更长的原因-在位数中它是O(n^2)而不是O(N)。真正的计算机系统(相对于理论计算机系统)有限的位数，因此乘法比加法和移位要花费恒定的时间倍数。如果我没记错的话，现代处理器，如果流水线正确的话，就可以通过干扰处理器中ALU(算术单位)的使用来实现与加法一样快的乘法。

Answer 2

x << k == x multiplied by 2 to the power of kx >> 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)要将一个数字除以非二次方，我不知道任何简单的方法，除非您想要实现一些低级逻辑，使用其他二进制操作并使用某种形式的迭代。