python-3.x - Shift Adder 乗算の説明

Question

バイナリ値の乗算の Shift Adder メソッドをダミーの用語で説明できますか?答えを計算するプログラムを書くことは言うまでもなく、それを理解していません。

Answer 1

紙の鉛筆による標準的な乗算方法 (別名ロング乗算法)を知っていることを前提としています。

Binary shift & add と long multiplication メソッドのメソッドは非常に似ています。

たとえば、長い乗算法で、2 進数 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 and 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

上記のアルゴリズムは、コーディングを開始するのに十分すぎるはずです。