问题描述
如何仅使用移位和加法进行乘法和除法?
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.
这篇关于如何仅使用移位和加法进行乘法和除法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！