c - 如何仅使用移位和加法进行乘法和除法？

Question

如何仅使用移位和加法进行乘法和除法运算？

Answer 1

要根据加法和移位法进行乘法运算，您需要将其中一个数字分解为 2 的幂，如下所示:

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(算术单元)的使用来执行乘法和加法一样快。