我如何乘，只使用比特移位并加入分？ [英] How can I multiply and divide using only bit shifting and adding?

问题描述

我怎么可以繁殖，只使用比特移位并加入分？

解决方案

要乘以添加和你想通过两个权力分解号码中的一个，像这样的转变方面：

  21 * 5 = 10101_2 * 101_2（初始步骤）
       = 10101_2 *（1 * 2 ^ 2 + 0 * 2 ^ 1 + 1 * 2 ^ 0）
       = 10101_2 * 2 ^ 2 + 10101_2 * 2 ^ 0
       = 10101_2＆LT;＆LT; 2 + 10101_2＆LT;＆LT; 0（分解）
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5（同前初始pression）
 

（ _2 指基2）<​​/ P>

正如你所看到的，乘法可以分解成增加和移动情况，然后再返回。这也是为什么乘法比移位需要更长的时间或增加 - 这是在比特数为O（n ^ 2），而不是为O（n）。真实计算机系统（相对于理论计算机系统）有位的数量有限，所以比起加法和移位乘法需要的时间的常数倍。如果我没有记错，现代的处理器，如果流水线得当，可以做乘法差不多一样快，此外，通过在处理器的算术逻辑单元（算术单元）的利用率搞乱。

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 means base 2)

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