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

问题描述

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

How can I multiply and divide using only bit shifting and adding?

推荐答案

要在相乘和移位方面相乘，您需要将两个数字之一分解为一个数字，如下所示:

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屋！