如何仅使用位移和加法进行乘法和除法? [英] How can I multiply and divide using only bit shifting and adding?

问题描述

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

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.

这篇关于如何仅使用位移和加法进行乘法和除法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！