23
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

なぜ「2の補数」を使うのか

Last updated at Posted at 2018-03-13

概要

  • なぜ2の補数を使うのか.何のために使うのか.
    -> 減算器を不要にして,加算器だけで済むようにするため
  • なぜ2の補数による加算が減算の代わりになるのか
    -> 有限の桁数しか保存できないメモリでは,
    「AからBを引く」のと「AからBの2の補数を足す」のは同じ結果になるから.

2の補数が使われるのはなぜ?

ハードウェアが簡単に

2の補数を用いることで,減算を加算器を用いて行えるようになるので減算器が不要になり,
ハードウェア(回路)を簡単にできます.

(より詳細な説明は「コンピュータの構成と設計 下」の「付録B 論理設計の基礎」中の「B.6 加算の高速化:桁上げの先見」に書いてありました.これが結構面白いです.)

減算を加算器を用いて行うとはどういうことか

10進数で考えてみましょう.
8-5 という減算を加算で行おうとすると,負の数という定義を導入し,
8 + (-5)
とすることで加算に変えることができます.
言い換えると,一桁同士の引き算の表が無くても,
負の数を含めた一桁同士の足し算の表があれば済むということです.
よって,減算器が無くても減算をすることができます(超簡単化しています).

2進数に話を戻しますと,「負の数という定義を導入し,」の部分を「2の補数という定義を導入し,」とすることで減算を加算器を用いて行うことを可能にしているのです.

この,「負の数 $\approx$ 2の補数」という感覚は重要なので念頭に置いて以下を読んでもらえると,理解の助けになると思います.

「反転」して「1を足す」のはなぜ?

2の補数(反転して1を足した数)が負の数の代わりになる理由についてです.

2の補数の計算方法

ビットを反転させ,反転した2進数に1を足せば,2の補数は求まります.
例えば,0110の2の補数は

\begin{align*}
0110&→1001 \qquad (反転) \\
&→1010 \qquad (1を足す)
\end{align*}

という流れで,1010と求まります.
なぜでこのように2の補数を定義するのでしょうか?

2の補数の定義の背景

まず,ある二進数で表された値A(N桁)を考えます.当然ですが

A + (Aを反転した値)= 111...11

がどのようなAでも成り立ちます.先ほどの例で試すと,0110+1001=1111です.
そして,両辺に1を足すと,

A + (Aを反転した値)+1 = 1000...00 \\
\Leftrightarrow A + (Aの2の補数)= 1000...00

となります.これを$\pmod {2^N}$で考えると,右辺の先頭の1はN+1桁目なので消えて

A + (Aの2の補数) \equiv 0  \pmod {2^N}

となります.
$\pmod {2^N}$の意味が分からなければ,ここでは「1~N桁目だけを見てそれ以上の桁は無視する事」であると考えてください.
これを変形すると,

(Aの2の補数) \equiv -A \pmod {2^N}

になります.この式から「Aの2の補数と**-Aは法$2^N$に関して合同である」とわかります!
言い換えると,「1~N桁目だけを見る限りでは,Aの2の補数と
-A**が同じである」ということです.
このことから,なんとなくAの2の補数 と -Aの関係が見えてきましたね!

「1~N桁目だけを見る」とは

「1~N桁目だけを見る限りでは同じ」という説明をしましたが,これは現実的にはどういうことに相当するのでしょうか.

今,4つだけ,0または1を保存できるメモリがあるとします.
このメモリで保存できる数の範囲は,0000 ~ 1111です.
11011のような5桁以上の数字は保存できず,先頭の1を無視して1011と保存するしかありません.
これはつまり「1~4桁目だけを見る」ということです.

以上のことから,「Aの2の補数と**-Aは法$2^N$に関して合同である」というのは,
「N桁しか保存できないメモリからすれば,Aの2の補数と
-A**は同じ」を意味しているとわかります.
始めに示した「負の数 $\approx$ 2の補数」ということが理解できたのではないでしょうか?

もし分かりにくい点があれば,コメントいただけるとありがたいです.

まとめ

  • 「2の補数」を使うのは,加算器だけを用意すればいいようにするため
  • 減算を加算器で計算できるのは,負の数を導入して$ A - B = A + (-B) $となることからなんとなくわかる
  • N桁しか保存できないメモリからすれば,2の補数と負の数は同じ
  • 2の補数の「反転して1を足す」という計算は,$A + (Aを反転した値)+1 = 1000...00 \equiv 0 \pmod {2^N}$から

最後に

私は専門家ではないので,間違ってそうな部分があればお気軽にコメントいただけると嬉しいです.

23
8
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
23
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?