たまりば

  パソコン・インターネット パソコン・インターネット  三鷹市 三鷹市

符号付き乗算
2011年04月26日 00:52

2進数の乗算は簡単だ。10進数と同じ普通の筆算でできる。しかも数字が1か0のみなので各部分積は0を掛ける(すなわち0)か1を掛ける(すなわち被乗数そのまま)かの2通りしかない。
4ビットで例を示す。0111〈10進法で7〉と1010〈10〉の乗算を筆算で書くと次のようになる。
        0 1 1 1
* 1 0 1 0
0 0 0 0
0 1 1 1
0 0 0 0
0 1 1 1
1 0 0 0 1 1 0
答えの1000110〈70〉が正しく求まった。
一般的に書くと、被乗数のnビット目と乗数のmビット目のANDをpmnと書けば次のようになる。
              p03 p02 p01 p00
p13 p12 p11 p10
p23 p22 p21 p20
+ p33 p32 p31 p30
さて、これは符号なしの場合である。符号付きの乗算をどうやればいいのか、自分は今まで知らなかった。
加算では符号を気にせず足してからあふれた桁を無視すると負数も正数も関係なく扱える。乗算ではどうかというと、さっきの計算を2の補数表現の符号付きとしてみると、0111〈7〉*1010〈-6〉の積は11010110〈-42〉になって欲しいところだがそうなっていない。

ではどうするかというと、乗数被乗数の両方を答えの8ケタまで符号拡張してやればよい。
つまり、
               0 0 0 0 0 1 1 1
* 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 1 1 0 1 1 0 1 0 1 1 0
こうである。上位を無視すると11010110〈-42〉が正しく求まっていることが分かる。
一般的に書けばこうである。
                              p03 p03 p03 p03 p03 p02 p01 p00
p13 p13 p13 p13 p13 p12 p11 p10
p23 p23 p23 p23 p23 p22 p21 p20
p33 p33 p33 p33 p33 p32 p31 p30
p33 p33 p33 p33 p33 p32 p31 p30
p33 p33 p33 p33 p33 p32 p31 p30
p33 p33 p33 p33 p33 p32 p31 p30
+ p33 p33 p33 p33 p33 p32 p31 p30
と、これを踏まえて、Wikipediaの乗算器の項を見ると簡略化された式がある。4桁×4桁の式を書くと、
                1  ~p03  p02  p01  p00
~p13 p12 p11 p10
~p23 p22 p21 p20
+ 1 p33 ~p32 ~p31 ~p30
こうだ。ここで「~」はビット反転(NOT)を表す。見ると分かるように、場所を取っていた符号拡張の部分が無くなった代わりに謎の「1」やビット反転が付いて複雑になっている。最初見た時わけが分からなかったが、考えた末に分かって感動したのでこの感動を分かち合いたい。

順に説明しよう。

まず先の式から最終的に切り捨てられる上位桁を除く。
  p03 p03 p03 p03 p03 p02 p01 p00
p13 p13 p13 p13 p12 p11 p10
p23 p23 p23 p22 p21 p20
p33 p33 p32 p31 p30
p33 p32 p31 p30
p32 p31 p30
p31 p30
+ p30
次に、
p03 p03 p03 p03 p03 p02 p01 p00
この辺に注目する。
この
p03 p03 p03 p03 p03
の部分は同じ数字が並んでいる。すなわち「00000」か「11111」になっているわけだ。
これに1を足すと、
00000 + 00001 =  00001
11111 + 00001 = 100000
となり、上位桁は切り捨てられることを考慮すれば、最下位以外が0になる。そして最下位は00000ならば1、11111ならば0であり、すなわちビット反転である。
よって、
p03 p03 p03 p03 p03 p02 p01 p00
+
0 0 0 0 1
=
0 0 0 0 ~p03 p02 p01 p00
となる。
これを使って式を書き換えると、
                 ~p03 p02 p01 p00
~p13 p12 p11 p10
~p23 p22 p21 p20
~p33 p32 p31 p30
p33 p32 p31 p30
p32 p31 p30
p31 p30
+ p30
- 1 1 1 1
さらによく見ると
                 ~p03 p02 p01 p00
~p13 p12 p11 p10
~p23 p22 p21 p20
~p33 p32 p31 p30
p33 p32 p31 p30
p32 p31 p30
p31 p30
+ p30
- 1 1 1 1
この辺にも斜めに同じ形があるので、
                     ~p03  p02  p01  p00
~p13 p12 p11 p10
~p23 p22 p21 p20
~p33 ~p32 ~p31 ~p30
+ p33
- 1 1 1 1
- 1 1 1
こうなって、さらに
   p33 ~p33

~p33 ~p33
- 1

~~p33 ~~p33
- 1 1
だから
                     ~p03  p02  p01  p00
~p13 p12 p11 p10
~p23 p22 p21 p20
+ p33 ~p32 ~p31 ~p30
- 1 1 1 1
- 1 1 1 1 1
こう。
あとは引き算を2の補数の加算に書き換えて
                     ~p03  p02  p01  p00
~p13 p12 p11 p10
~p23 p22 p21 p20
+ p33 ~p32 ~p31 ~p30
+ 1 0 0 0 1
+ 0 0 0 0 1
できあがり。
                1  ~p03  p02  p01  p00
~p13 p12 p11 p10
~p23 p22 p21 p20
+ 1 p33 ~p32 ~p31 ~p30
なおWikipediaに書いてある「bが符号付整数だった場合、部分積を符号拡張した上で足し合わせる必要がある。aが符号付整数だった場合、部分積のp7を足すのではなく、それ以外の合計から引かなければならない。」って辺りは上の式変形を部分的にやると導けると思うがめんどいので割愛。最初と最後だけ覚えておけばいいと思う。


  • Post time : 2011年04月26日 00:52│Comments(5)
    この記事へのコメント
    はじめまして!
    学校でマイコンを習い初めたのですが、先生に
    「C言語で、アスタリスクを使わずに積を求めなさい」
    ということを言われて調べていたところ、このページにたどり着きました。

    まさかコンピュータにとっても筆算のほうが計算しやすいだなんて。
    とても面白いですね。

    Wikiの内容を説明してくださっている部分も、とてもわかりやすいです。

    ビット反転まで使えるなんて、ますます処理が楽になります。

    今度、Cのプログラムに起こしてみます。
    ありがとうございました!
    Posted by Fujiruki at 2012年06月06日 03:34
    お役にたてたようで光栄です。
    乗算は奥が深いですよ。
    Posted by いかづちSqueakいかづちSqueak at 2012年06月09日 09:53
    質問よろしいでしょうか。

    p03 p03 p03 p03 p03 p02 p01 p00
    +
    0 0 0 0 1
    =
    0 0 0 0 ~p03 p02 p01 p00

    の後に、- 1が出るのは、どうしてでしょうか。
    Posted by ポニー at 2013年07月01日 18:13
    p03 p03 p03 p03 p03 p02 p01 p00
    +
    0 0 0 0 1
    =
    0 0 0 0 ~p03 p02 p01 p00



    p03 p03 p03 p03 p03 p02 p01 p00
    =
    0 0 0 0 ~p03 p02 p01 p00
    -
    0 0 0 0 1

    に変形しています。
    Posted by いかづちSqueakいかづちSqueak at 2013年07月07日 23:40
    p03 p02 p01 p00
    p13 p12 p11 p10
    + p23 p22 p21 p20
    - p33 p32 p31 p30

    p03 p02 p01 p00
    p13 p12 p11 p10
    p23 p22 p21 p20
    ~p33 ~p32 ~p31 ~p30
    + 1
    に補数表示してあげて
    p03,p13,p23をbit反転すると
    p03 p02 p01 p00
    p13 p12 p11 p10
    p23 p22 p21 p20
    + ~p33 ~p32 ~p31 ~p30
    - 0 0 1 1
    になるのでこれをまた補数表示すると同じ結果になります
    乗算は最後の桁の分を引いてあげることでも表せますね
    Posted by rarlo at 2015年06月08日 21:40
    URL欄を実験的に消してる間に廃止されてしまいました。まあいいか。
     
    <ご注意>
    書き込まれた内容は公開され、ブログの持ち主だけが削除できます。
    削除
    符号付き乗算
      コメント(5)