问题描述
如何仅使用位移和加法进行乘法和除法?
How can I multiply and divide using only bit shifting and adding?
推荐答案
要在加法和移位方面进行乘法，您需要将其中一个数字分解为 2 的幂，如下所示:
To multiply in terms of adding and shifting you want to decompose one of the numbers by powers of two, like so:
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(算术单元)的利用率来进行乘法，其速度与加法一样快.
As you can see, multiplication can be decomposed into adding and shifting and back again. This is also why multiplication takes longer than bit shifts or adding - it's O(n^2) rather than O(n) in the number of bits. Real computer systems (as opposed to theoretical computer systems) have a finite number of bits, so multiplication takes a constant multiple of time compared to addition and shifting. If I recall correctly, modern processors, if pipelined properly, can do multiplication just about as fast as addition, by messing with the utilization of the ALUs (arithmetic units) in the processor.
这篇关于如何仅使用位移和加法进行乘法和除法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！