python-3.x - 解释移位加法器乘法

Question

有人可以用虚拟术语向我解释二进制值乘法的 Shift Adder 方法吗？更不用说编写程序来计算答案了。

Answer 1

我假设您知道纸铅笔的标准乘法方法（又名长乘法方法）

二进制移位和加法与长乘法方法非常相似。

例如，在长乘法中，如果要将二进制数 1001 乘以 1011，则过程如下所示：

         1 0 0 0
       x 1 0 1 1
  ---------------
         1 0 0 0  ( Step 1: 1000 x LSB (bit 0) of 1011, which is 1, followed by 0 shift to the left)
+      1 0 0 0 -  ( Step 2: 1000 x bit 1 of 1011, which is again 1, followed by 1 shift to the left)
+    0 0 0 0 - -  ( Step 3: 1000 x bit 2 of 1011, which is 0, followed by 2 shifts to the left)
+  1 0 0 0 - - -  ( Step 4: 1000 x MSB (bit 3) of 1011 which is 1 again, followed by 3 shifts to the left)
 ----------------
   1 0 1 1 0 0 0  ( Step 5: Add all the above)
 ----------------

现在在 shift 和 add 方法中，最后你不做加法（步骤 5），而是我们不断地添加数字，如下所示：

Step 0: Result = 0
Step 1: Result = Result + Step 1 of Long division (1000 x LSB (bit 0) of 1011, which is 1, followed by 0 shift)
               = 0000 + 1000
               = 1000
Step 2: Result = Result + Step 2 of Long division (1000 x bit 1 of 1011, which is again 1, followed by 1 shift)
               = 1000 + 10000 (Additional zero at the end of second term is due to shifting 1000 to the left by 1 time: 1000_0)
               = 11000

Step 3: Result = Result + Step 3 of Long division (1000 x bit 2 of 1011, which is 0, followed by 2 shift)
               = 11000 + 000000
               = 11000
Step 4: Result = Result + Step 4 of Long division (1000 x MSB (bit 3) of 1011 which is 1 again, followed by 3 shift)
               = 11000 + 1000000 (Additional zeros at the end of second term is due to shifting 1000 to the left three times: 1000_000)
               = 1011000

我希望上述算法足以让您开始编码。