補数 引き算 負の整数
ここでは補数について、いったいどのような仕組みになっているのかを、10進法、2進法、一般論で説明します。
補数を用いることによって、(0を含む)自然数の足し算だけを使って、引き算を実行できるようになります。
更に、補数の片方を負の整数だとみなすことで「(数の範囲に制限がある)整数もどき」の数の体系、つまり足し算・引き算・掛け算が矛盾なく実行できる数の体系、を構築することができます。
補数(ほすう:complement number)とは、互いに補う(おぎなう)2つの数の組のことです。
互いに補い合わせることで、とある決まった数になる2つの数の組を互いに補数といいます。
補数を扱う際には「合わせて何になる数で、補数を考えているのか?」を前提として常に念頭に置いておいてください。
合わせて $5$ になる数で、互いに補数を考えてみましょう。
\begin{alignat*}{2}
0 + 5 &\;=\; 5 &&\qquad\fbox{$0$ と $5$ は互いに補数} \\
1 + 4 &\;=\; 5 &&\qquad\fbox{$1$ と $4$ は互いに補数} \\
2 + 3 &\;=\; 5 &&\qquad\fbox{$2$ と $3$ は互いに補数} \\
\end{alignat*}
左辺の片方の数を右辺に移項して、左辺と右辺を入れ替えると、補数の相方(あいかた)を得る式になります。
この解説では、あえて冗長な表現で「補数の相方」と表記することにしました。「補数」という言葉自体に、「相手を補う」という意味が含まれていますので、通常は単に「補数」と表記しただけで、ここでの「補数の相方」の意味を含んでいます。
\begin{alignat*}{2}
5 - 0 &\;=\; 5 &&\qquad\fbox{$0$ の相方は $5$} \\
5 - 5 &\;=\; 0 &&\qquad\fbox{$5$ の相方は $0$} \\
5 - 1 &\;=\; 4 &&\qquad\fbox{$1$ の相方は $4$} \\
5 - 4 &\;=\; 1 &&\qquad\fbox{$4$ の相方は $1$} \\
5 - 2 &\;=\; 3 &&\qquad\fbox{$2$ の相方は $3$} \\
5 - 3 &\;=\; 2 &&\qquad\fbox{$3$ の相方は $2$} \\
\end{alignat*}
「補数の相方」という意味で、数字の上に「バー」を付けて表現します。
\begin{alignat*}{2}
\overline{0} &\;=\; 5 &\qquad\fbox{$0$ の相方は $5$} \\
\overline{5} &\;=\; 0 &\qquad\fbox{$5$ の相方は $0$} \\
\overline{1} &\;=\; 4 &\qquad\fbox{$1$ の相方は $4$} \\
\overline{4} &\;=\; 1 &\qquad\fbox{$4$ の相方は $1$} \\
\overline{2} &\;=\; 3 &\qquad\fbox{$2$ の相方は $3$} \\
\overline{3} &\;=\; 2 &\qquad\fbox{$3$ の相方は $2$} \\
\end{alignat*}
合わせて $10$ になる数で、互いに補数を考えてみましょう。
\begin{alignat*}{2}
0 + 10 &\;=\; 10 &&\qquad\fbox{$0$ と $10$ は互いに補数} \\
1 + 9 &\;=\; 10 &&\qquad\fbox{$1$ と $9$ は互いに補数} \\
2 + 8 &\;=\; 10 &&\qquad\fbox{$2$ と $8$ は互いに補数} \\
3 + 7 &\;=\; 10 &&\qquad\fbox{$3$ と $7$ は互いに補数} \\
4 + 6 &\;=\; 10 &&\qquad\fbox{$4$ と $6$ は互いに補数} \\
5 + 5 &\;=\; 10 &&\qquad\fbox{$5$ と $5$ は互いに補数} \\
\end{alignat*}
\begin{alignat*}{2}
10 - 0 &\;=\; 10 &&\qquad\fbox{$0$ の相方は $10$} \\
10 - 10 &\;=\; 0 &&\qquad\fbox{$10$ の相方は $0$} \\
10 - 1 &\;=\; 9 &&\qquad\fbox{$1$ の相方は $9$} \\
10 - 9 &\;=\; 1 &&\qquad\fbox{$9$ の相方は $1$} \\
10 - 2 &\;=\; 8 &&\qquad\fbox{$2$ の相方は $8$} \\
10 - 8 &\;=\; 2 &&\qquad\fbox{$8$ の相方は $2$} \\
10 - 3 &\;=\; 7 &&\qquad\fbox{$3$ の相方は $7$} \\
10 - 7 &\;=\; 3 &&\qquad\fbox{$7$ の相方は $3$} \\
10 - 4 &\;=\; 6 &&\qquad\fbox{$4$ の相方は $6$} \\
10 - 6 &\;=\; 4 &&\qquad\fbox{$6$ の相方は $4$} \\
10 - 5 &\;=\; 5 &&\qquad\fbox{$5$ の相方は $5$} \\
\end{alignat*}
\begin{alignat*}{2}
\overline{0} &\;=\; 10 &&\qquad\fbox{$0$ の相方は $10$} \\
\overline{10} &\;=\; 0 &&\qquad\fbox{$10$ の相方は $0$} \\
\overline{1} &\;=\; 9 &&\qquad\fbox{$1$ の相方は $9$} \\
\overline{9} &\;=\; 1 &&\qquad\fbox{$9$ の相方は $1$} \\
\overline{2} &\;=\; 8 &&\qquad\fbox{$2$ の相方は $8$} \\
\overline{8} &\;=\; 2 &&\qquad\fbox{$8$ の相方は $2$} \\
\overline{3} &\;=\; 7 &&\qquad\fbox{$3$ の相方は $7$} \\
\overline{7} &\;=\; 3 &&\qquad\fbox{$7$ の相方は $3$} \\
\overline{4} &\;=\; 6 &&\qquad\fbox{$4$ の相方は $6$} \\
\overline{6} &\;=\; 4 &&\qquad\fbox{$6$ の相方は $4$} \\
\overline{5} &\;=\; 5 &&\qquad\fbox{$5$ の相方は $5$} \\
\end{alignat*}
合わせて $9$ になる数で、互いに補数を考えてみましょう。
\begin{alignat*}{2}
0 + 9 &\;=\; 9 &&\qquad\fbox{$0$ と $9$ は互いに補数} \\
1 + 8 &\;=\; 9 &&\qquad\fbox{$1$ と $8$ は互いに補数} \\
2 + 7 &\;=\; 9 &&\qquad\fbox{$2$ と $7$ は互いに補数} \\
3 + 6 &\;=\; 9 &&\qquad\fbox{$3$ と $6$ は互いに補数} \\
4 + 5 &\;=\; 9 &&\qquad\fbox{$4$ と $5$ は互いに補数} \\
\end{alignat*}
\begin{alignat*}{2}
9 - 0 &\;=\; 9 &&\qquad\fbox{$0$ の相方は $9$} \\
9 - 9 &\;=\; 0 &&\qquad\fbox{$9$ の相方は $0$} \\
9 - 1 &\;=\; 8 &&\qquad\fbox{$1$ の相方は $8$} \\
9 - 8 &\;=\; 1 &&\qquad\fbox{$8$ の相方は $1$} \\
9 - 2 &\;=\; 7 &&\qquad\fbox{$2$ の相方は $7$} \\
9 - 7 &\;=\; 2 &&\qquad\fbox{$7$ の相方は $2$} \\
9 - 3 &\;=\; 6 &&\qquad\fbox{$3$ の相方は $6$} \\
9 - 6 &\;=\; 3 &&\qquad\fbox{$6$ の相方は $3$} \\
9 - 4 &\;=\; 5 &&\qquad\fbox{$4$ の相方は $5$} \\
9 - 5 &\;=\; 4 &&\qquad\fbox{$5$ の相方は $4$} \\
\end{alignat*}
\begin{alignat*}{2}
\overline{0} &\;=\; 9 &\qquad\fbox{$0$ の相方は $9$} \\
\overline{9} &\;=\; 0 &\qquad\fbox{$9$ の相方は $0$} \\
\overline{1} &\;=\; 8 &\qquad\fbox{$1$ の相方は $8$} \\
\overline{8} &\;=\; 1 &\qquad\fbox{$8$ の相方は $1$} \\
\overline{2} &\;=\; 7 &\qquad\fbox{$2$ の相方は $7$} \\
\overline{7} &\;=\; 2 &\qquad\fbox{$7$ の相方は $2$} \\
\overline{3} &\;=\; 6 &\qquad\fbox{$3$ の相方は $6$} \\
\overline{6} &\;=\; 3 &\qquad\fbox{$6$ の相方は $3$} \\
\overline{5} &\;=\; 4 &\qquad\fbox{$5$ の相方は $4$} \\
\overline{4} &\;=\; 5 &\qquad\fbox{$4$ の相方は $5$} \\
\end{alignat*}
あまり意識している人はいないかも知れませんが、殆どの人は小学校1,2年生の学校教育で、上記の補数、特に「合わせて $10$ になる数」を叩き込まれています。
初めての計算では指折り数えて計算を実行していたかも知れませんが、計算練習をいっぱいやっているうちに「$10$ の塊」を身に付けていきます。
どの数の組が $10$ になるのか、ということを体感で覚えさせられているわけです。
そして「自分でも気付かないうちに、指を折らなくても計算ができるようになっていた」という人が多いのではないでしょうか?
「合わせて $9$ になる数」は、連続の繰り下がりのある引き算の筆算で、意識せずに使っていると思われます。
算盤(そろばん)では、「五珠(ごだま)」の扱いがありますので「合わせて $5$ になる数」も積極的に使っています。
「補数」という言葉を使っていないだけで、補数の概念自体は知らない間に身に付いているはずです。
この後で補数を使った引き算や負の数に関して説明していきます。
補数の話では2進法がでてくるのですが、補数を利用した計算原理については10進法や2進法などの数の表記法とは関係がありません。
2進法の計算はそのままディジタル回路に置き換えることができますので、2進法での応用が重要になるのです。
足し算回路のみで引き算が実行できるようになれば、足し算よりも複雑な引き算の回路を作る必要がなくなって、余計な回路を作る必要がなくなり、資源を有効活用できることになります。
2進法に慣れてないのに、いきなり2進法の補数を学ぼうとすると、分からないが重なって、何が分からないのか分からない、ということになりかねません。
普段使い慣れている10進法で、ある程度の仕組みを知って、慣れてから2進法に応用するとよいでしょう。
2進法について全く聞いたことのない「基数?」「進法?」「位取り?」という人は(こちら)のリンク先を見てください。
10進数と2進数の変換等、各基数の変換については(こちら)のリンク先を見てください。
補数を考える際には「合わせて何になる数で、補数を扱っているのか?」が重要です。
この解説では、合わせて何になるか、様々な設定で補数を扱います。
そこで、説明全体を通して 文字 $N$ で、合わせて何になるかの設定の数値を表すことにします。
この文字を用いて、補数の定義をまとめておきましょう。
合わせて $N$ になる自然数の組 $a, b$ を互いに補数といいます。
次の式で補数を定義します。
\begin{alignat*}{2}
a + b &\;=\; N &&\qquad\fbox{$a$ と $b$ は互いに補数} \\
\end{alignat*}
定義式の左辺の $a$ を右辺に移項すると次の式を得ます。
\begin{alignat*}{2}
b &\;=\; N - a &&\qquad\fbox{$a$ の相方 $b$ は $N-a$ で求められる} \\
\end{alignat*}
$a$ の相方を $\overline{a}$ で表現することにします。
\begin{alignat*}{2}
\overline{a} &\;=\; N - a &&\qquad\fbox{$a$ の相方 $\overline{a}$ は $N - a$} \\
\end{alignat*}
補数の定義式は次のように書き換えることができます。
\begin{alignat*}{2}
a + \overline{a} &\;=\; N &&\qquad\fbox{$a$ と $\overline{a}$ は互いに補数} \\
\end{alignat*}
相方の相方は元の数になります。
\begin{alignat*}{2}
\overline{\overline{a}} &\;=\; N - \overline{a} &&\qquad\fbox{$\overline{a}$ の相方である $\overline{\overline{a}}$ は $N - \overline{a}$} \\
&\;=\; N - \left(N - a\right) &&\qquad\fbox{$\overline{a}$ を $N - a$ で置き換えた} \\
&\;=\; N - N + a &&\qquad\fbox{括弧を展開した} \\
&\;=\; a &&\qquad\fbox{$N$ が相殺されて消えるので、相方の相方で元の数 $a$ に戻ることが分かった} \\
\end{alignat*}
後の説明で一般論を理解すると分かるのですが、「補数の相方を求める操作」が「整数の符号反転の操作」に対応することになります。
補数を利用することによって、足し算のみで引き算を実行することができるようになります。
まずは、10進法でその仕組みを見てみましょう。
例として、$5-2=3$ という計算を $N=10$ の補数を利用できる形に書き換えてみましょう。
($2$ と $8$ は互いに補数になっていて、$\overline{2}=8,\; \overline{8}=2$ と表記できます。)
$5-2$ の計算を次のように考えます。
\begin{alignat*}{2}
5 - 2 &\;=\; 5 - 2 + 10 - 10 &&\qquad\fbox{$N=10$ を足して引いた($N=10$ の下駄を履かせて計算してることになる)} \\
&\;=\; 5 + (10 - 2) - 10 &&\qquad\fbox{$-2+10$ の部分を括弧で括った} \\
&\;=\; 5 + 8 - 10 &&\qquad\fbox{括弧内を計算した} \\
&\;=\; 13 - 10 &&\qquad\fbox{$5+8$ の部分だけ計算した} \\
&\;=\; 1\color{red}{3} - 10 &&\qquad\fbox{第1項の$\color{red}{\mbox{一桁目だけ}}$を見れば $5-2$ の$\color{red}{\mbox{答え}}$になってる} \\
\end{alignat*}
上記の2段目と最後の段で等式を作り、整理します。
\begin{alignat*}{2}
5 + (10 - 2) - 10 &\;=\; 1\color{red}{3} - 10 &&\qquad\fbox{上枠の2段目を左辺に、最後の段を右辺にした等式} \\
5 + (10 - 2) &\;=\; 1\color{red}{3} &&\qquad\fbox{両辺に $N=10$ を足した} \\
5 + \overline{2} &\;=\; 1\color{red}{3} &&\qquad\fbox{左辺の $10-2$ は $2$ の相方} \\
\end{alignat*}
上式の最後の等式は「$5+\overline{2}$ を計算して、$N=10$ を取り除くことで、$5-2$ の結果になる」と解釈することができます。
実際の計算では機械的に次の手順の操作を実行することで、引き算の結果を得ることができます。
\begin{alignat*}{2}
5 - 2 &\;\rightarrow\; 5 + \overline{2} &&\qquad\fbox{$2$ を引く演算を $2$ の相方の足し算に置き換える} \\
&\;=\; 5 + 8 &&\qquad\fbox{$2$ の相方は $8$} \\
&\;=\; 13 &&\qquad\fbox{足し算を実行した} \\
&\;=\; 1\color{red}{3} &&\qquad\fbox{$\color{red}{\mbox{一桁目だけ}}$を見れば $N=10$ を無視していていることになり、$5-2$ の$\color{red}{\mbox{答え}}$になってる} \\
\end{alignat*}
一桁目だけを見る、という部分は $N=10$ を取り除くということです。
二桁目以降を見ないだけで取り除く操作が実行できるので、この部分は計算する必要がありません。
この操作で、正の数の足し算を用いて引き算を実行していることになります。
次の例として、$62-28=34$ という計算を $N=10^2=100$ の補数を利用できる形に書き換えてみましょう。
($28$ と $72$ は互いに補数になっていて、$\overline{28}=72,\; \overline{72}=28$ と表記できます。)
$62-28$ の計算を次のように考えます。
\begin{alignat*}{2}
62 - 28 &\;=\; 62 - 28 + 100 - 100 &&\qquad\fbox{$N=100$ を足して引いた($N=100$ の下駄を履かせて計算してることになる)} \\
&\;=\; 62 + (100 - 28) - 100 &&\qquad\fbox{$-28+100$ の部分を括弧で括った} \\
&\;=\; 62 + 72 - 100 &&\qquad\fbox{括弧内を計算した} \\
&\;=\; 134 - 100 &&\qquad\fbox{$62+72$ の部分だけ計算した} \\
&\;=\; 1\color{red}{34} - 100 &&\qquad\fbox{第1項の$\color{red}{\mbox{二桁だけ}}$を見れば $62-28$ の$\color{red}{\mbox{答え}}$になってる} \\
\end{alignat*}
上記の2段目と最後の段で等式を作り、整理します。
\begin{alignat*}{2}
62 + (100 - 28) - 100 &\;=\; 1\color{red}{34} - 100 &&\qquad\fbox{上枠の2段目を左辺に、最後の段を右辺にした等式} \\
62 + (100 - 28) &\;=\; 1\color{red}{34} &&\qquad\fbox{両辺に $N=100$ を足した} \\
62 + \overline{28} &\;=\; 1\color{red}{34} &&\qquad\fbox{左辺の $100-28$ は $28$ の相方} \\
\end{alignat*}
上式の最後の等式は「$62+\overline{28}$ を計算して、$N=100$ を取り除くことで、$62-28$ の結果になる」と解釈することができます。
実際の計算では機械的に次の手順の操作を実行することで、引き算の結果を得ることができます。
\begin{alignat*}{2}
62 - 28 &\;\rightarrow\; 62 + \overline{28} && \qquad\fbox{$28$ を引く演算を $28$ の相方の足し算に置き換える} \\
&\;=\; 62 + 72 &&\qquad\fbox{$28$ の相方は $72$} \\
&\;=\; 134 &&\qquad\fbox{足し算を実行した} \\
&\;=\; 1\color{red}{34} &&\qquad\fbox{$\color{red}{\mbox{二桁だけ}}$を見れば $N=100$ を無視していることになり、$62-28$ の$\color{red}{\mbox{答え}}$になってる} \\
\end{alignat*}
二桁だけを見る、という部分は $N=100$ を取り除くということです。
三桁目以降を見ないだけで取り除く操作が実行できるので、この部分は計算する必要がありません。
この操作で、正の数の足し算を用いて引き算を実行していることになります。
次の例として、$62-28=34$ という計算を $N=10^4=10000$ の補数を利用できる形に書き換えてみましょう。
($28$ と $9972$ は互いに補数になっていて、$\overline{28}=9972,\; \overline{9972}=28$ と表記できます。)
$62-28=34$ の計算を次のように考えます。
\begin{alignat*}{2}
62 - 28 &\;=\; 62 - 28 + 10000 - 10000 &&\qquad\fbox{$N=10000$ を足して引いた($N=10000$ の下駄を履かせて計算してることになる)} \\
&\;=\; 62 + (10000 - 28) - 10000 &&\qquad\fbox{$-28+10000$ の部分を括弧で括った} \\
&\;=\; 62 + 9972 - 10000 &&\qquad\fbox{括弧内を計算した} \\
&\;=\; 10034 - 10000 &&\qquad\fbox{$62+9972$ の部分だけ計算した} \\
&\;=\; 1\color{red}{0034} - 10000 &&\qquad\fbox{第1項の$\color{red}{\mbox{四桁だけ}}$を見れば $62-28$ の$\color{red}{\mbox{答え}}$になってる} \\
\end{alignat*}
上記の2段目と最後の段で等式を作り、整理します。
\begin{alignat*}{2}
62 + (10000 - 28) - 10000 &\;=\; 1\color{red}{0034} - 10000 &&\qquad\fbox{上枠の2段目を左辺に、最後の段を右辺にした等式} \\
62 + (10000 - 28) &\;=\; 1\color{red}{0034} &&\qquad\fbox{両辺に $N=10000$ を足した} \\
62 + \overline{28} &\;=\; 1\color{red}{0034} &&\qquad\fbox{左辺の $10000-28$ は $28$ の相方} \\
\end{alignat*}
上式の最後の等式は「$62+\overline{28}$ を計算して、$N=10000$ を取り除くことで、$62-28$ の結果になる」と解釈することができます。
実際の計算では機械的に次の手順の操作を実行することで、引き算の結果を得ることができます。
\begin{alignat*}{2}
62 - 28 &\;\rightarrow\; 62 + \overline{28} && \qquad\fbox{$28$ を引く演算を $28$ の $N=10000$ の相方の足し算に置き換える} \\
&\;=\; 62 + 9972 &&\qquad\fbox{$28$ の相方は $9972$} \\
&\;=\; 10034 &&\qquad\fbox{足し算を実行した} \\
&\;=\; 1\color{red}{0034} &&\qquad\fbox{$\color{red}{\mbox{四桁だけ}}$を見れば $N=10000$ を無視していることになり、$62-28$ の$\color{red}{\mbox{答え}}$になってる} \\
\end{alignat*}
四桁だけを見る、という部分は $N=10000$ を取り除くということです。
五桁目以降を見ないだけで取り除く操作が実行できるので、この部分は計算する必要がありません。
この操作で、正の数の足し算を用いて引き算を実行していることになります。
$10^n$ は $100\ldots 0$ のように $1$ の次に $n$ 桁連続で $0$ を並べた数になります。
合わせて $N=10^n$ になる補数を利用すると、$N$ を取り除く操作は $n$ 桁だけを見るという操作で実行できることになり、便利に使うことができます。
補数を利用することによって、足し算のみで引き算を実行することができるようになります。
10進法の例をいくつかやってみて、慣れてきたら、2進法でその仕組みを見てみるとよいでしょう。
2進法の計算は簡単なのですが、ちょっと大きな数になると桁数が多くなって、扱うのが大変です。
仕組みを理解することが重要なので、慣れないうちはあまり桁数が大きくならない数で考えてみてください。
例として、$5-2=3$ 、という計算を $N=8=2^3$ の補数を利用できる形に書き換えてみましょう。
(10進表記では、$2$ と $6$ は互いに $N=8$ の補数になっていて、$\overline{2}=6,\; \overline{6}=2$ と表記できます。)
この例題に登場する数値の、2進表記と10進表記の対応は、次のようになります。
\begin{align*}
\begin{array}{rcr}
\mbox{2進表記} &\;\leftrightarrow& \mbox{10進表記} \\
N=1000 &\;\leftrightarrow& N=8 \\
101 &\;\leftrightarrow& 5 \\
10 &\;\leftrightarrow& 2 \\
11 &\;\leftrightarrow& 3 \\
110 &\;\leftrightarrow& 6 \\
1011 &\;\leftrightarrow& 11 \\
\end{array}
\end{align*}
計算を次のように考えます。
次の枠の、左の式は2進表記での計算です。
右の式は、左の式と同じ計算を10進表記で示したものです。
\begin{alignat*}{5}
101 - 10 &\;=\; 101 - 10 + 1000 - 1000 &&\qquad\fbox{$N=1000$ を足して引いた} &&\qquad & 5 - 2 &\;=\; 5 - 2 + 8 - 8 &&\qquad\fbox{参考のため同じ計算を10進表記で表示} \\
&\;=\; 101 + (1000 - 10) - 1000 &&\qquad\fbox{$-10+1000$ の部分を括弧で括った} &&\qquad & &\;=\; 5 + (8 - 2) + 8 && \\
&\;=\; 101 + 110 - 1000 &&\qquad\fbox{括弧内を計算した} &&\qquad & &\;=\; 5 + 6 - 8 && \\
&\;=\; 1011 - 1000 &&\qquad\fbox{$101+110$ の部分だけ計算した} &&\qquad & &\;=\; 11 - 8 && \\
&\;=\; 1\color{red}{011} - 1000 &&\qquad\fbox{第1項の$\color{red}{\mbox{三桁だけ}}$を見れば $101-10$ の$\color{red}{\mbox{答え}}$になってる} &&\qquad & &\;=\; 3 && \qquad\fbox{第1項の$\color{red}{\mbox{三桁だけを見るというわけにはいかない}}$}\\
\end{alignat*}
上の2進表記の式の2段目と最後の段で等式を作り、整理します。
\begin{alignat*}{2}
101 + (1000 - 10) - 1000 &\;=\; 1\color{red}{011} - 1000 &&\qquad\fbox{上枠の2段目を左辺に、最後の段を右辺にした等式} \\
101 + (1000 - 10) &\;=\; 1\color{red}{011} &&\qquad\fbox{両辺に $N=1000$ を足した} \\
101 + \overline{10} &\;=\; 1\color{red}{011} &&\qquad\fbox{左辺の $1000-10$ は $10$ の相方} \\
\end{alignat*}
上式の最後の等式は「$101+\overline{10}$ を計算して、$N=1000$ を取り除くことで、$101-10$ の結果になる」と解釈することができます。
実際の計算では機械的に次の手順の操作を実行することで、引き算の結果を得ることができます。
\begin{alignat*}{2}
5 - 2 &\;\rightarrow\; 101 - 10 &&\qquad\fbox{2進表示に変換} \\
&\;\rightarrow\; 101 + \overline{10} &&\qquad\fbox{$10$ を引く演算を $10$ の相方の足し算に置き換える} \\
&\;=\; 101 + 110 &&\qquad\fbox{$10$ の相方は $110$} \\
&\;=\; 1011 &&\qquad\fbox{足し算を実行した} \\
&\;=\; 1\color{red}{011} &&\qquad\fbox{$\color{red}{\mbox{三桁だけ}}$を見れば $N=1000$ を無視していていることになり、$101-10$ の$\color{red}{\mbox{答え}}$になってる} \\
&\;\rightarrow\; \color{red}{3} &&\qquad\fbox{$\color{red}{\mbox{答え}}$の部分を10進表記に変換} \\
\end{alignat*}
三桁だけを見る、という部分は2進表記で $N=1000$ を取り除くということです。
四桁目以降を見ないだけで取り除く操作が実行できるので、この部分は計算する必要がありません。
(10進表記で同じ操作をしようとすると $N=8$ を取り除かなければいけないので、計算が必要になります。)
この操作で、正の数の足し算を用いて引き算を実行していることになります。
10進表記の $2^n$ は、2進表記では $100\ldots 0$ のように $1$ の次に $n$ 桁連続で $0$ を並べた数になります。
合わせて $N=2^n$ になる補数を利用すると、2進表記で $N$ を取り除く操作は $n$ 桁だけを見るという操作で実行できることになり、便利に使うことができます。
あらかじめ補数の相方を計算しておいて、対応表を作っておくことで、引き算を足し算で実行することが可能になります。
対応表がない場合は、なるべく簡単な計算で補数を求める方法があれば便利です。
10進法では $N=10^n$ の補数を使うことで、最後に $N$ を無視して取り除く操作が非常に簡単になりました。
ここでは $N=10^n$ の補数の相方を簡単に求める工夫を紹介します。
例として、 $N=10^6=1000000$ での $5678$ の補数の相方を $1000000 - 5678$ で求めてみましょう。
試しに普通に筆算でやってみると、連続の繰り下がりの処理が結構しんどいと思います。
そこで、次のように計算します。
\begin{alignat*}{2}
1000000 - 5678 &\;=\; 999999 + 1 - 5678 &&\qquad\fbox{$1000000 = 999999 + 1$ を用いた} \\
&\;=\; (999999 - 5678) + 1 &&\qquad\fbox{計算の順番を変えた} \\
&\;=\; 994321 + 1 &&\qquad\fbox{$999999 - 5678$ の計算は繰り下がりがないので暗算でできる} \\
&\;=\; 994322 &&\qquad\fbox{$1$ を足すと、$5678$ の $N=1000000$ の補数の相方 $994322$ が求まる} \\
\end{alignat*}
$N=1000000$ での $5678$ の補数の相方を求めるには、$N=999999$ での $5678$ の補数の相方を $999999 - 5678$ で求めて、得られた $994321$ に $1$ を足すことで、暗算で簡単に計算できるということです。
一般に $N=10^n$ の補数の相方を求める際には、$N=10^n-1=99\cdots 9$ の $n$ 桁連続 $9$ の補数の相方を求めて、$1$ を足せば暗算で簡単に計算できる、ということになります。
$10^n-1$ が $n$ 桁連続で $9$ を並べた数字になることは、次のことから分かります。
\begin{alignat*}{2}
S &\;=\; \phantom{x^n + \;} x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 &&\qquad\fbox{$1$ から $x^{n-1}$ までの、全部で $n$ 個の項の和を $S$ と置いた} \\
xS &\;=\; x^n + x^{n-1} + x^{n-2} + \cdots + x^2 + x &&\qquad\fbox{上式の両辺に $x$ を掛けた} \\
(x-1)S &\;=\; x^n - 1 &&\qquad\fbox{上の2式の第2式から第1式の引き算を、両辺で実行した} \\
\end{alignat*}
\begin{alignat*}{2}
(x-1)(x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1) &\;=\; x^n - 1 &&\qquad\fbox{$S$ の部分を最初の定義で書き直した(左辺の式は右辺の式を因数分解した式になる)} \\
9(10^{n-1} + 10^{n-2} + \cdots + 10^2 + 10 + 1) &\;=\; 10^n - 1 &&\qquad\fbox{$x$ に $10$ を代入} \\
9\cdot 10^{n-1} + 9\cdot 10^{n-2} + \cdots + 9\cdot 10^2 + 9\cdot 10 + 9 &\;=\; 10^n - 1 &&\qquad\fbox{左辺の $9$ を分配すると、左辺は10進法での $n$ 桁連続の $9$ になることが分かる} \\
\end{alignat*}
2進法では $N=2^n$ の補数を用いると、計算がめちゃめちゃ簡単になります。
$a$ の補数の相方 $\overline{a}$ を求めるには、$\overline{a}=N-a$ の計算をする必要があるのですが、ある工夫によって引き算の計算をする必要が全くなくなります。
ここではその工夫について説明します。
$N=2^n$ の補数の相方の計算には $2^n-1$ によって得られる2進表記での $n$ 桁連続の $1$ が便利に使えるようになります。
$2^n-1$ が、2進表記で $n$ 桁連続で $1$ を並べた数字になることは、次のことから分かります。
\begin{alignat*}{2}
(x-1)(x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1) &\;=\; x^n - 1 &&\qquad\fbox{前節の議論で得られた $x^n-1$ の因数分解の式} \\
1(2^{n-1} + 2^{n-2} + \cdots + 2^2 + 2 + 1) &\;=\; 2^n - 1 &&\qquad\fbox{$x$ に $2$ を代入} \\
1\cdot 2^{n-1} + 1\cdot 2^{n-2} + \cdots + 1\cdot 2^2 + 1\cdot 2 + 1 &\;=\; 2^n - 1 &&\qquad\fbox{左辺の $1$ を分配すると、左辺は2進法での $n$ 桁連続の $1$ になることが分かる} \\
\end{alignat*}
例として $N=16=2^4$ の補数を考えます。
$5$ の相方を求めてみましょう。
10進表記の $N=16$ は 2進表記で $N=10000$ です。
10進表記の $5$ は2進表記で $101$ です。
次の枠の左の式は、2進表記で補数を求める計算です。
右の式は、左の式と同じ計算を10進表記で表示したものです。
\begin{alignat*}{5}
10000 - 101 &\;=\; 1111 + 1 - 101 &&\qquad\fbox{$10000 = 1111 + 1$ を用いた} &&\qquad & 16 - 5 &\;=\; 15 + 1 -5 &&\qquad\fbox{参考のため同じ計算を10進表記で表示} \\
&\;=\; (1111 - 101) + 1 &&\qquad\fbox{計算の順番を変えた} &&\qquad & &\;=\; (15 - 5) + 1 && \\
&\;=\; 1010 + 1 &&\qquad\fbox{$1111 - 101$ の計算は繰り下がりがないので簡単} &&\qquad & &\;=\; 10 + 1 && \\
&\;=\; 1011 &&\qquad\fbox{$1$ を足すと $101$ の $N=10000$ の補数の相方は $1011$ が求まる} &&\qquad & &\;=\; 11 &&\qquad\fbox{$5$ の $N=16$ の補数の相方は $11$} \\
\end{alignat*}
2進表記で、$101$ の $N=10000$ の補数の相方を求めるには、$101$ の $N=1111$ の 補数の相方を $1111-101$ で求めて、得られた $1010$ に $1$ を足すことで、暗算で求めることができます。
更に良いことに $1111 - 101$ の部分は、$101=0101$ のように、引く数を引かれる数に揃えて4桁で書くことによって、次のようにもっと簡単に計算できます。
\begin{align*}
\begin{array}{rrl}
& 1111 & \\
- & 0101 & \leftarrow\mbox{この、$0$ を $1$ に、$1$ を $0$ に、置き換えて、} \\ \hline
& 1010 & \leftarrow\mbox{コインの裏表のように反転させると、} \\
& & \phantom{\leftarrow}\mbox{引き算の答えになっている}
\end{array}
\end{align*}
つまり、2進表記で連続で $1$ を並べた数字からの引き算は $0$ と $1$ の置き換えで実行できる、ということです。
色々な数値で試してみてください、超簡単で計算しているような感覚はないと思います。
ディジタル回路では $0$ と $1$ を置き換える操作をビット反転といいます。
ビット反転を実行するディジタル回路は非常に単純です。
複雑な引き算回路を作るよりも、ビット反転を使って補数の相方を求めた方が、遥かに単純なので、コンピュータでは補数を用いて計算を行います。
$N=2^n$ の補数の相方を、引き算を使わずに求める方法です。
- 2進法の $n$ ビットで自然数を表現
- ビット反転する($2^n-1$ の補数の相方が求まる)
- $1$ を足す($2^n$ の補数の相方が求まる)
例として $73$ の $N=2^8=256$ の補数の相方を求めて、相方の相方で元に戻るのか確かめてみましょう。
\begin{alignat*}{3}
\fbox{10進数の元の数} &\qquad& 73 &\qquad& 183 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{2進数8ビット表現} && 01001001 && 10110111 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{ビット反転} && 10110110 && 01001000 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{$1$ を足す} && 10110111 && 01001001 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{10進数に変換} &\qquad& 183 &\qquad& 73 \\
\end{alignat*}
次の例として $73$ の $N=2^{16}=65536$ の補数の相方を求めて、相方の相方で元に戻るのか確かめてみましょう。。
\begin{alignat*}{3}
\fbox{10進数の元の数} &\qquad& 73 &\qquad& 65463 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{2進数16ビット表現} && 0000000001001001 && 1111111110110111 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{ビット反転} && 1111111110110110 && 0000000001001000 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{$1$ を足す} && 1111111110110111 && 0000000001001001 \\
\downarrow\quad&&\downarrow&&\downarrow \\
\fbox{10進数に変換} &\qquad& 65463 &\qquad& 73 \\
\end{alignat*}
合わせて $N$ の値になる補数を利用することで、引き算を足し算で表したり、後で説明しますが自然数で負の整数を扱ったりすることができるようになります。
この $N$ の値は何でも良いのですが、位取り記数法に使ってる基数(base 又は radix)によって計算が簡単になる値があります。
便利に使える補数には特別な名前がついています。
- 基数$b$の補数(radix complement)
- 合わせて $N=b^n$ になる補数のこと
- $b^n$ を$b$進表記すると、$1$ の次に $n$ 桁連続で $0$ を並べた数になる
- $b$進表記でこの補数を利用すると、$N$ の倍数を取り除く操作を $n$ 桁で打ち切る操作によって実行できるので便利
- 10の補数(ten's complement)
- 合わせて $N=10^n$ になる補数のこと
- $10^n$ を10進表記すると、$1$ の次に $n$ 桁連続で $0$ を並べた数になる
- 10進表記でこの補数を利用すると、$N$ の倍数を取り除く操作を $n$ 桁で打ち切る操作によって実行できるので便利
- 2の補数(two's complement)
- 合わせて $N=2^n$ になる補数のこと
- $2^n$ を2進表記すると、$1$ の次に $n$ 桁連続で $0$ を並べた数になる
- 2進表記でこの補数を利用すると、$N$ の倍数を取り除く操作を $n$ 桁で打ち切る操作によって実行できるので便利
- 減基数$(b-1)$の補数(diminished radix complement)
- 合わせて $N=b^n-1$ になる補数のこと
- $b^n-1$ を$b$進表記すると $n$ 桁連続で $(b-1)$ を並べた数になる
- $b$進表記でこの補数を利用すると、補数の相方を求める計算で繰り下がりを考える必要がなくなるので便利
- 基数$b$の補数の相方は、減基数$(b-1)$の補数の相方に $1$ を足して計算できる
- 9の補数(nines' complement)
- 合わせて $N=10^n-1$ になる補数のこと
- $10^n-1$ を10進表記すると $n$ 桁連続で $9$ を並べた数になる
- 10進表記でこの補数を利用すると、補数の相方を求める計算で繰り下がりを考える必要がなくなるので便利
- 10の補数の相方は、9の補数の相方に $1$ を足して計算できる
- 1の補数(ones' complement)
- 合わせて $N=2^n-1$ になる補数のこと
- $2^n-1$ を2進表記すると $n$ 桁連続で $1$ を並べた数になる
- 2進表記でこの補数を利用すると、補数の相方を求める計算で繰り下がりを考える必要がなくなるので便利
- ディジタル回路では、ビット反転するだけで、補数の相方を求める操作ができるので超便利
- 2の補数の相方は、1の補数の相方に $1$ を足して計算できる
$n$ の値を何桁にするのか、については特に決まりはありません。
その時の都合で適当な桁数に設定します。
私見ですが、ここでの補数のネーミングが、補数を分かりにくくしている一因になっていると思います。
「10の補数」と書かれると「足して10になる補数」だ、「9の補数」と書かれると「足して9になる補数」だと勘違いしてしまいそうです。
初めて学習するときの脱落地点になりかねないと思いますので、注意してください。
英語表記での nines' は、アポストロフィの位置から 9 の複数形の所有格です。
この英語表記には 9 をたくさん並べた感じのニュアンスがあります。
補数を利用することで「引き算は補数の相方の足し算で実行できる」ということが分かりました。
ここで、中学校1年で初めて「負の整数」を習った時のことを思い出してみましょう。
「引き算は負の数の足し算」ということを習った記憶はないでしょうか?
整数の定義を思い出して、補数の定義と比較してみましょう。
自然数のイメージは、起点の $0$ から $1$ ずつ増えて、無限に数が続いていく次のようなものです。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | … 無限に続く |
自然数 $a$ に対する負の整数 $-a$ は、足して $0$ になる数で定義しました。
次の式が負の整数 $-a$ を定める定義式になります。
自然数 $a$ に対して、$a$ と足して $0$ になる数を、負の $a$ と呼び、$-a$ で表す。
\begin{align*}
a + (-a) = 0
\end{align*}
この定義を元に、数の基本法則である、結合法則、交換法則、分配法則を壊さないように足し算や掛け算の計算ルールを定めることで、矛盾のない整数の体系を構築することができます。
興味のある人は(講義スライド)を見てください。
「負の数」と「負の数」の掛け算の答えが「正の数」になる理由が分かります。
整数のイメージには $0$ を挟んで左右対称に「正の数」と「負の数」を並べた「数直線」があります。
無限に続く … | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | … 無限に続く |
補数の定義を見直してみましょう。
$0\le a\le N$ の自然数 $N, a$ において、$a$ と足して $N$ になる数を $a$ の補数の相方といい、$\overline{a}$ で表す。
\begin{align*}
a + \overline{a} = N
\end{align*}
負の整数の定義式と、補数の定義式を並べてみてください。
補数の定義式の $\overline{a}$ を $-a$ に、$N$ を $0$ に置き換えてみて、負の整数の定義式と見比べると、そっくりなことに気付きます。
実は、補数の定義式を元に、整数とそっくりな「整数もどき」の数の体系を作っていくことができるのです。
ここでは補数の相方が、ある条件の下で負の整数とみなすことができることを説明します。
一般論で説明しますので、一度での理解は難しいかも知れません。
そのような場合は、後の節の具体論を見てから、もう一度一般論を見直すことをお勧めします。
それでは、数の大きさを $0\lt b \lt a \lt N,\, 0\lt c \lt N$ のように設定し、大きな数 $a$ から 小さな数 $b$ の引き算 $a-b=c$ を考えてみましょう。
\begin{alignat*}{2}
a - b &\;=\; c && \\
N + a - b &\;=\; N + c &&\qquad\fbox{両辺に $N$ を加えた(両辺に $N$ の下駄を履かせて計算してることになる)} \\
a + (N - b) &\;=\; N + c &&\qquad\fbox{左辺の計算の順番を変えた} \\
a + \overline{b} &\:=\; N + c &&\qquad\fbox{左辺の $N-b$ は $b$ の相方} \\
a + \overline{b} &\;=\; \overline{0} + c &&\qquad\fbox{右辺の $N - 0$ は $0$ の相方} \\
\end{alignat*}
最後の等式は「$a$ に $b$ の補数の相方を足した結果は $N + c$ になる」というものです。
この等式は $N$ をゼロのようなものとみなして取り除き(もしくは無視して)、$\overline{b}$ の数値は正の値だけど負の $b$ を意味すると解釈することによって「$a$ と 負の $b$ の足し算の答えは $c$ である」という意味の式になります。
左辺の $a$ も $\overline{b}$ も、どちらも正の値なので、左辺の計算は正の数の足し算で実行できますし、右辺の計算結果も正の値になります。
余談になりますが、合同式の知識がある人は、次のように考えてみると、さらに深い理解が得られるでしょう。
\begin{alignat*}{2}
a - b &\;\equiv\; N + a - b \quad (\mathrm{mod} N) &&\qquad\fbox{$N$ を加えても $N$ で割った余りは変わらない} \\
&\;=\; a + (N - b) &&\qquad\fbox{計算の順番を変えた} \\
&\;=\; a + \overline{b} &&\qquad\fbox{$a - b$ と $a + \overline{b}$ は $N$ で割った余りは同じ} \\
\end{alignat*}
つまり、$N$ で割った余りだけに着目した自然数の世界では、$a - b$ と $a + \overline{b}$ は同じものとみなせます。
余りが同じ数をまとめて分類することを、剰余類と呼びます。
補数を使った整数もどきの数の世界の構築は、剰余類の応用の話をやっていることになります。
機会があれば、合同式について勉強してみると良いでしょう。
次に、数の大きさを $0\lt b \lt a \lt N,\, 0\lt c \lt N$ のように設定し、小さな $b$ から 大きな数 $a$ の引き算 $b-a=-c$ を考えてみましょう。
\begin{alignat*}{2}
b - a &\;=\; -c && \\
N + b - a &\;=\; N - c &&\qquad\fbox{両辺に $N$ を加えた(両辺に $N$ の下駄を履かせて計算してることになる)} \\
b + (N - a) &\;=\; N - c &&\qquad\fbox{左辺の計算の順番を変えた} \\
b + \overline{a} &\:=\; \overline{c} &&\qquad\fbox{左辺の $N-a$ は $a$ の相方、右辺の $N-c$ は $c$ の相方} \\
\end{alignat*}
最後の等式は「$b$ に $a$ の補数の相方を足した結果が $c$ の補数の相方になる」というものです。
この等式は、$\overline{a}$ は負の $a$ 、$\overline{c}$ は負の $c$ を意味すると解釈することによって「$b$ と 負の $a$ の足し算の答えは負の $c$ である」という意味の式になります。
前の方の節で見たように、具体的な数値での計算では、左辺の $b$ も $\overline{a}$ も、どちらも正の値なので、左辺の計算は正の数の足し算で実行できますし、右辺の結果も正の値になります。
数の大きさを $0\lt a,\,b,\,c \lt N$ のように設定し、負の数 $-a$ から 正の数 $b$ の引き算 $-a-b=-c$ を考えてみましょう。
\begin{alignat*}{2}
-a -b &\;=\; -c && \\
2N - a - b &\;=\; 2N - c &&\qquad\fbox{両辺に $2N$ を加えた(両辺に $2N$ の下駄を履かせて計算してることになる)} \\
(N - a) + (N - b) &\;=\; N + N - c &&\qquad\fbox{$2N$ の足し算を分割して計算の順番を変えた} \\
\overline{a} + \overline{b} &\:=\; N + \overline{c} &&\qquad\fbox{左辺の $N-a$ は $a$ の相方、$N-b$ は $b$ の相方、右辺の $N-c$ は $c$ の相方} \\
\overline{a} + \overline{b} &\:=\; \overline{0} + \overline{c} &&\qquad\fbox{右辺の $N-0$ は $0$ の相方} \\
\end{alignat*}
最後の等式は「$a$ の補数の相方に $b$ の補数の相方を足した結果は $N + \overline{c}$ になる」というものです。
この等式は $N$ をゼロのようなものとみなして取り除き(もしくは無視して)、$\overline{a}$ は負の $a$、$\overline{b}$ は負の $b$、$\overline{c}$ は負の $c$ を意味すると解釈することによって「負の $a$ と 負の $b$ の足し算の答えは負の $c$ である」というという意味の式になります。
後の例でやりますが、具体的な数値での計算では、左辺の $\overline{a}$ も $\overline{b}$ も、どちらも正の値なので、左辺の計算は正の数の足し算で実行できますし、右辺の結果も正の値になります。
数の大きさを $0\lt a,\,b,\,c \lt N$ のように設定し、正の数 $a$ と 負の数 $-b$ の掛け算 $a(-b)=-c$ を考えてみましょう。
\begin{alignat*}{2}
a(-b) &\;=\; -c && \\
a(N - N - b) &\;=\; -c &&\qquad\fbox{左辺に $0=N-N$ を挿入} \\
a((N - b) - N) &\;=\; -c &&\qquad\fbox{左辺の計算の順番を入れ替え} \\
a(N - b) -aN &\;=\; -c &&\qquad\fbox{左辺の掛け算を分配} \\
a(N - b) &\;=\; aN - c &&\qquad\fbox{左辺の $-aN$ を右辺に移項} \\
a(N - b) &\;=\; (a-1)N + N - c &&\qquad\fbox{右辺の $a\times N$ を $(a-1)N$ と $N$ に分割} \\
a\overline{b} &\;=\; (a-1)N + \overline{c} &&\qquad\fbox{左辺の $N-b$ は $b$ の相方、右辺の $N-c$ は $c$ の相方} \\
a\overline{b} &\;=\; (a-1)\overline{0} + \overline{c} &&\qquad\fbox{右辺の $N-0$ は $0$ の相方} \\
\end{alignat*}
最後の等式は「$a$ に $b$ の補数の相方を掛けた結果は $(a-1)N + \overline{c}$ になる」というものです。
この等式は $N$ をゼロのようなものとみなして取り除き(もしくは無視して)、 $\overline{b}$ は負の $b$、$\overline{c}$ は負の $c$ を意味すると解釈することによって「$a$ と 負の $b$ の掛け算の答えは負の $c$ である」というという意味の式になります。
後の例でやりますが、具体的な数値での計算では、左辺の $a$ も $\overline{b}$ も、どちらも正の値なので、左辺の計算は正の数の掛け算で実行できますし、右辺の計算結果も正の値になります。
数の大きさを $0\lt a,\,b,\,c \lt N$ のように設定し、負の数 $-a$ と 負の数 $-b$ の掛け算 $(-a)(-b)=c$ を考えてみましょう。
\begin{alignat*}{2}
(-a)(-b) &\;=\; c && \\
(N - N - a)(N - N - b) &\;=\; c &&\qquad\fbox{左辺に $0=N-N$ を挿入} \\
((N - a) - N)((N - b) - N) &\;=\; c &&\qquad\fbox{左辺の計算の順番を入れ替え} \\
(N - a)(N - b) -(N - a)N -(N - b)N + N^2 &\;=\; c &&\qquad\fbox{左辺で $(N-a)$ や $(N-b)$ を塊で見て、掛け算を展開} \\
(N - a)(N - b) - N^2 + aN - N^2 + bN + N^2 &\;=\; c &&\qquad\fbox{左辺の $(N-a)N$ と $(N-b)N$ を展開} \\
(N - a)(N - b) - N^2 + aN + bN &\;=\; c &&\qquad\fbox{$-N^2-N^2+N^2=N^2$ で左辺を整理} \\
(N - a)(N - b) - (N - a - b)N &\;=\; c &&\qquad\fbox{$-N^2+aN+bN=-(N-a-b)$ で左辺を整理} \\
(N - a)(N - b) - (N - (a + b))N &\;=\; c &&\qquad\fbox{$-a-b=-(a+b)$ で左辺を整理} \\
(N - a)(N - b) &\;=\; (N - (a + b))N + c &&\qquad\fbox{左辺の $-(N-(a+b))N$ を右辺に移項} \\
\overline{a}\overline{b} &\;=\; \overline{a+b}N + c &&\qquad\fbox{左辺の $N-a$ は $a$ の相方、$N-b$ は $b$ の相方、右辺の $N-(a+b)$ は $a+b$ の相方} \\
\overline{a}\overline{b} &\;=\; \overline{a+b}\;\overline{0} + c &&\qquad\fbox{右辺の $N-0$ は $0$ の相方} \\
\end{alignat*}
最後の等式は「$a$ の補数の相方に $b$ の補数の相方を掛けた結果は $\overline{a+b}N + c$ になる」というものです。
この等式は $N$ をゼロのようなものとみなして取り除き(もしくは無視して)、$\overline{a}$ は負の $a$、$\overline{b}$ は負の $b$ を意味すると解釈することによって「負の $a$ と 負の $b$ の掛け算の答えは正の $c$ である」という意味の式になります。
後の例でやりますが、具体的な数値での計算では、左辺の $\overline{a}$ も $\overline{b}$ も、どちらも正の値なので、左辺の計算は正の数の掛け算で実行できますし、右辺の計算結果も正の値になります。
$a$ か $b$ のどちらかが $1$ じゃなければ $a+b\lt ab = c$ なので、$0\lt a + b\lt N$ になります。
$a$ と $b$ のどちらかが $1$ の場合、例えば $a=1$ の場合は $ab=b=c$ なので、$a+b=1+b=1+c\le N$ になります。
補数を利用することで、引き算を足し算で行うだけでなく、負の整数を扱った計算も、自然数のみを使って実行できることを示しました。
各導出の最後の等式で、両辺とも正の値になっていることに注目です。
左辺を計算のスタートにして右辺の結果を得ることになるのですが、途中計算には正の数値の足し算と掛け算だけを用いるので、負の数値は一切出てくることはありません。
正の数値を上手く解釈することによって、負の数と同等なものを扱っているということになります。
補数を使った計算原理は、記数法に2進法を使うとか、10進法をつかうとか、そういうこととは関係ありません。
計算結果から $N$ の倍数を取り除く操作が、$N=10^n$ なら10進表記で $n$ 桁取り出す操作に対応し、$N=2^n$ なら2進表記で $n$ 桁取り出す操作に対応する、ということです。
実際の計算では、正である自然数の足し算と掛け算のみを使うので、計算するたびに数の大きさはどんどん膨らんでいきますが、$N$ の倍数を取り除くという操作で、ある範囲にある数値の演算を矛盾なく表現することになります。
補数の定義式が負の整数の定義式とそっくりなので、ある限られた範囲ではありますが、矛盾が起きることはありません。
余裕のある人は「群論」という分野の、商群の剰余類というもの勉強すると、より深い理解に繋がります。
計算原理は以上なのですが、数値の解釈と範囲についての補足があります。
補数を用いることによって、自然数の数値には二種類の解釈ができるようになります。
例えば、$a+b=N$ で表される $a$ という自然数は、そのまま $a$ を表しているとすることも、$b$ の補数である $\overline{b}$ のことを表しているとすることも、両方の表現(解釈)が可能です。
しかし具体的な応用では、どちらか一方に機械的に解釈しないと困ります。
一つの数値には一つの意味しか持たせないようにするわけです。
一つの物事に二種類の解釈があるとき、人間は臨機応変にその場の都合で2種類の解釈を使い分けることができますが、コンピュータ等の機械に判断させる場合には、どちらか一方に決める方法を指示しておかなければなりません。
正の整数も負の整数も同じくらいの量が必要だと考えられるため、$0\le a \lt N$ の範囲に入る自然数 $a$ を次のように分類します。
\begin{alignat*}{3}
a \mbox{と表現する数の範囲} &\quad:\quad 0 \le a \lt \frac{N}{2} &&\qquad\fbox{半分より小さい方はそのまま「バー無し」で表現して、「正の数」を表すと解釈} \\
\overline{N - a} \mbox{と表現する数の範囲} &\quad:\quad \frac{N}{2} \le a \lt N &&\qquad\fbox{半分以上の方は「バー有り」で表現して、「負の数」を表すと解釈} \\
\end{alignat*}
上記分類を、自然数 $m$ を使って、$N$ の周期 $mN$ で、次のように自然数全体に広げます。
\begin{alignat*}{3}
a \mbox{と表現する数の範囲} &\quad:\quad mN \le a + mN \lt \frac{N}{2} + mN &&\qquad\fbox{半分の自然数を「バー無し」で表現} \\
\overline{N - a} \mbox{と表現する数の範囲} &\quad:\quad \frac{N}{2} + mN\le a + mN \lt N + mN &&\qquad\fbox{もう半分の自然数は「バー有り」で表現} \\
\end{alignat*}
($0$ 以外の)「バー無し」の表現を「正の数」、「バー有り」の表現を「負の数」、に解釈しますので表現できる数の範囲は次のようになります。
\begin{alignat*}{3}
\mbox{0と正の数の範囲} &\quad:\quad \left[0, \frac{N}{2}\right) &&\qquad\fbox{$0$ 以上 $\displaystyle\frac{N}{2}$ 未満} \\
\mbox{負の数の範囲} &\quad:\quad \left[-\frac{N}{2}, 0\right) &&\qquad\fbox{$\displaystyle -\frac{N}{2}$ 以上 $0$ 未満} \\
\end{alignat*}
最終的に扱う整数の範囲は、次のようになります。
\begin{alignat*}{3}
\mbox{合わせて $N$ の補数を利用して、扱う整数の範囲} &\quad:\quad \left[-\frac{N}{2}, \frac{N}{2} \right) &&\qquad\fbox{$\displaystyle -\frac{N}{2}$ 以上 $\displaystyle\frac{N}{2}$ 未満} \\
\end{alignat*}
ここでの説明は一般論だったので、一度で理解するのは難しいかも知れません。
次節以降の具体的な数の構成をやってみて、感覚をつかんでからもう一度、ここの解説を見直してみてください。
N=10 の例
例として $N=10$ の補数を考えて、整数もどきの数の世界を作ってみましょう。
補数の世界で、$N$ をゼロとみなし、次の表のように、自然数を補数を利用して二通りに解釈して表現します。
例えば、$3$ という自然数は二通りの解釈が可能で、そのまま $3$ として解釈することもできますし、$3=N-7$ なので $\overline{7}$ と解釈することもできます。
例えば、$18$ という自然数は二通りの解釈が可能で、$18=N+8$ なので $8$ と解釈することもできますし、$18=2N-2$ なので $\overline{2}$ と解釈することもできます。
あらゆる自然数が「バー有り」と「バー無し」の二種類の表現で解釈できるようになります。
一般の自然数を考えると、数は無限に続きますが、$N=10$ より小さい2つの数の掛け算までしか考える必要がない時は $10\times 10=100$ の自然数まで、表を作っておけば十分です。
次に、青色を付けた部分をその数の代表表現として決めます。
後で、「バー無し」表現を「正の数」、「バー有り」表現を「負の数」、だとみなすので 0 をまたいで左右に均等に取るとよいでしょう。
そして、代表表現と自然数の対応を以下の表のように整理します。
(ちなみに、「群論」の分野の知識がある人は、ここでの話を「$\mathrm{mod} N$ の商群の剰余類の代表元を定めている」と考えてください。暦のカレンダーの7種類の曜日のように、自然数を10で割った余りで10種類に分類してます。)
自然数の2桁目以降の桁は、計算の最終段階で無視することになるので、次のように書いた方がすっきりします。
この後は、途中計算では自然数をそのまま使って、計算結果の最終的な表現では上の代表表現のみを用いるということにします。
そして、この表のバー有り表現を負の数だとみなすことで、$-5$ から $4$ までの範囲の整数に関しては、矛盾のない数の演算が可能になります。
様々な数の演算(足し算・引き算・掛け算)をやってみて、上手くいくのか確かめてみましょう。
\begin{alignat*}{2}
2 + 2 &\;=\; 4 &&\qquad\fbox{$2+2$ はそのまま計算すればよい} \\
\end{alignat*}
\begin{alignat*}{2}
4 - 2 &\;\rightarrow\; 4 + \overline{2} &&\qquad\fbox{$-2$ は $\overline{2}$ の足し算で表現} \\
&\;=\; 4 + 8 &&\qquad\fbox{$\overline{2}$ は $8$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{1}2 &&\qquad\fbox{計算した} \\
&\;=\; 2 &&\qquad\fbox{代表表現で表示} \\
\end{alignat*}
\begin{alignat*}{2}
2 - 4 &\;\rightarrow\; 2 + \overline{4} &&\qquad\fbox{$-4$ は $\overline{4}$ の足し算で表現} \\
&\;=\; 2 + 6 &&\qquad\fbox{$\overline{4}$ は $6$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; 8 &&\qquad\fbox{計算した} \\
&\;=\; \overline{2} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -2 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
-2 - 2 &\;\rightarrow\; \overline{2} + \overline{2} &&\qquad\fbox{$-2$ は $\overline{2}$ の足し算で表現} \\
&\;=\; 8 + 8 &&\qquad\fbox{$\overline{2}$ は $8$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{1}6 &&\qquad\fbox{計算した} \\
&\;=\; \overline{4} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -4 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
2 \times 2 &\;=\; 4 &&\qquad\fbox{$2\times 2$ はそのまま計算すればよい} \\
\end{alignat*}
\begin{alignat*}{2}
2 \times (-2) &\;\rightarrow\; 2 \times \overline{2} &&\qquad\fbox{$-2$ は $\overline{2}$ で表現} \\
&\;=\; 2 \times 8 &&\qquad\fbox{$\overline{2}$ は $8$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{1}6 &&\qquad\fbox{計算した} \\
&\;=\; \overline{4} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -4 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
(-2) \times (-2) &\;\rightarrow\; \overline{2} \times \overline{2} &&\qquad\fbox{$-2$ は $\overline{2}$ で表現} \\
&\;=\; 8 \times 8 &&\qquad\fbox{$\overline{2}$ は $8$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{6}4 &&\qquad\fbox{計算した} \\
&\;=\; 4 &&\qquad\fbox{代表表現で表示} \\
\end{alignat*}
\begin{alignat*}{2}
3 + 4 &\;=\; 7 &&\qquad\fbox{$3+4$ はそのまま計算} \\
&\;=\; \overline{3} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -3 &&\qquad\fbox{バー有り表現は負の数のこと。$\color{red}{\mbox{$4$ を上回る計算結果は上手く表現できない}}$} \\
\end{alignat*}
\begin{alignat*}{2}
-4 - 3 &\;\rightarrow\; \overline{4} + \overline{3} &&\qquad\fbox{$-4$ は $\overline{4}$ で、$-3$ は $\overline{3}$ の足し算で表現} \\
&\;=\; 6 \times 7 &&\qquad\fbox{$\overline{4}$ は $6$ で、$\overline{3}$ は $7$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{1}3 &&\qquad\fbox{計算した} \\
&\;=\; 3 &&\qquad\fbox{代表表現で表示。$\color{red}{\mbox{$-5$ を下回る計算結果は上手く表現できない}}$} \\
\end{alignat*}
上手く扱える数値の範囲は限られていますが、範囲を超えないように注意すると上手く行くことが分かります。
$N=10$ をもっと大きな数にすることで、上手く扱える数値の範囲が広がります。
N=102 の例
次の例として $N=100$ の補数を考えて、整数もどきの数の世界を作ってみましょう。
$N=10$ の時と同様な操作で次の表(長くなるので先の例と行列を逆にしてる)を作ります。
この表のバー有り表現を負の数だとみなすことで、$-50$ から $49$ に収まる数の計算がすべてできるようになります。
この表を利用して、様々な数の演算(足し算・引き算・掛け算)をやってみましょう。
途中計算では自然数をそのまま、計算結果の最終的な表現では上の代表表現のみを使います。
\begin{alignat*}{2}
27 + 19 &\;=\; 43 &&\qquad\fbox{$27+13$ はそのまま計算すればよい} \\
\end{alignat*}
\begin{alignat*}{2}
27 - 19 &\;\rightarrow\; 27 + \overline{19} &&\qquad\fbox{$-19$ は $\overline{19}$ の足し算で表現} \\
&\;=\; 27 + 81 &&\qquad\fbox{$\overline{19}$ は $81$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{1}08 &&\qquad\fbox{計算した} \\
&\;=\; 8 &&\qquad\fbox{代表表現で表示} \\
\end{alignat*}
\begin{alignat*}{2}
19 - 27 &\;\rightarrow\; 19 + \overline{27} &&\qquad\fbox{$-27$ は $\overline{27}$ の足し算で表現} \\
&\;=\; 19 + 73 &&\qquad\fbox{$\overline{27}$ は $73$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; 92 &&\qquad\fbox{計算した} \\
&\;=\; \overline{8} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -8 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
-19 - 27 &\;\rightarrow\; \overline{19} + \overline{27} &&\qquad\fbox{$-19$ は $\overline{19}$ で、$-27$ は $\overline{27}$ の足し算で表現} \\
&\;=\; 81 + 73 &&\qquad\fbox{$\overline{19}$ は $81$ 、$\overline{27}$ は $73$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{1}54 &&\qquad\fbox{計算した} \\
&\;=\; \overline{46} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -46 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
13 \times 3 &\;=\; 39 &&\qquad\fbox{$3\times 13$ はそのまま計算すればよい} \\
\end{alignat*}
\begin{alignat*}{2}
13 \times (-3) &\;\rightarrow\; 13 \times \overline{3} &&\qquad\fbox{$-3$ は $\overline{3}$ で表現} \\
&\;=\; 13 \times 97 &&\qquad\fbox{$\overline{3}$ は $97$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{12}61 &&\qquad\fbox{計算した} \\
&\;=\; \overline{39} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -39 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
(-13) \times 3 &\;\rightarrow\; \overline{13} \times 3 &&\qquad\fbox{$-13$ は $\overline{13}$ で表現} \\
&\;=\; 87 \times 3 &&\qquad\fbox{$\overline{13}$ は $87$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{2}61 &&\qquad\fbox{計算した} \\
&\;=\; \overline{39} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -39 &&\qquad\fbox{バー有り表現は負の数のこと} \\
\end{alignat*}
\begin{alignat*}{2}
(-13) \times (-3) &\;\rightarrow\; \overline{13} \times \overline{3} &&\qquad\fbox{$-13$ は $\overline{13}$ で、$-3$ は $\overline{3}$ 表現} \\
&\;=\; 87 \times 97 &&\qquad\fbox{$\overline{13}$ は $87$ 、$\overline{3}$ は $97$ のこと(計算には自然数をそのまま使う)} \\
&\;=\; \color{gray}{84}39 &&\qquad\fbox{計算した} \\
&\;=\; 39 &&\qquad\fbox{代表表現で表示} \\
\end{alignat*}
N=24 の例
次の例として $N=2^4=16$ の補数の例を考えて、整数もどきの数の世界を作ってみましょう。
数を10進法と2進法で表記して、前節の例と同様に各自然数を補数を利用して「バー有り」と「バー無し」の二通りで解釈し、以下の表を作ります。
各蘭の、上に書いた数字が10進表記で、下に書いた数字が2進表記です。
一般の自然数を考えると、数は無限に続きますが、$N=16$ より小さい2つの数の掛け算までしか考える必要がない時は $16\times 16=256$ の自然数まで、表を作っておけば十分です。
次に、青色を付けた部分をその数の代表表現として決めます。
後で、バー無し表現を正の数、バー有り表現を負の数、だと考えるので 0 をまたいで左右に均等に取るとよいでしょう。
また、8 や 24 を「バー有り」にするか「バー無し」にするか、迷うところなのですが、2進表記の4ビット目に注目して決めることにします。
「4ビット目が 0 の数」を「正の数」、「4ビット目が 1 の数」を「負の数」、に選ぶことにします。
これによって自然数の4ビット目が符号の役割を兼ねることになって便利です。
4ビット目が 0 の時はプラス符号、1 の時はマイナス符号、を表現してるようにみなせます。
この符号の役割を兼ねるようにできる性質は、$2^n$ の補数の2進表記でのみ可能で、10進法などではできません。
$n$ ビットの場合に一般化すると、$2^n$ の補数の2進表記では、$n$ ビット目を符号の役割を兼ねるようにできまして、ディジタル回路においては非常に便利に使えます。
そして、前節の例と同じように代表表現と自然数の対応を以下の表のように整理します。
上手く分けたので、バー有り表現の自然数の4ビット目は 1 に、バー無し表現の自然数の4ビット目は 0 に、なってます。
2進表記では、代表表現によって自然数の下位4ビットの数字で分類できます。
2進表記の5桁目以降の桁は、計算の最終段階で無視することになるので、次のように書いた方がすっきりします。
自然数の4ビット目が、符号の意味を兼ねてることも分かりやすくなったと思います。
更に、2進の4ビット表現では、補数の対応計算も、ビット反転プラス1、で簡単に求まります。
この後は、途中計算では自然数をそのまま使って、計算結果の最終的な表現では上の代表表現のみを用いるということにします。
そして、この表のバー有り表現を負の数だとみなすことで、$-8$(二進表記で $-1000$)から $7$(二進表記で $0111$)までの範囲の数に関しては、矛盾のない数の演算が可能になります。
様々な数の演算(足し算・引き算・掛け算)をやってみて、上手くいくのか確かめてみましょう。
\begin{alignat*}{2}
5 + 2 &\;\rightarrow\; 0101 + 0010 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;=\; 0111 &&\qquad\fbox{そのまま計算すればよい} \\
&\;\rightarrow\; 7 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{alignat*}{2}
5 - 2 &\;\rightarrow\; 0101 - 0010 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;\rightarrow\; 0101 + \overline{0010} &&\qquad\fbox{引き算を補数の相方の足し算に置き換える} \\
&\;=\; 0101 + 1110 &&\qquad\fbox{$\overline{0010}$ は $1110$ のこと(ビット反転プラス$1$)} \\
&\;=\; \color{gray}{1}0011 &&\qquad\fbox{計算した} \\
&\;=\; 0011 &&\qquad\fbox{代表表現で表示(4桁だけ見る、4桁目が0なのでそのまま)} \\
&\;\rightarrow\; 3 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{alignat*}{2}
2 - 5 &\;\rightarrow\; 0010 - 0101 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;\rightarrow\; 0010 + \overline{0101} &&\qquad\fbox{引き算を補数の相方の足し算に置き換える} \\
&\;=\; 0010 + 1011 &&\qquad\fbox{$\overline{0101}$ は $1011$ のこと(ビット反転プラス$1$)} \\
&\;=\; 1101 &&\qquad\fbox{計算した} \\
&\;=\; \overline{0011} &&\qquad\fbox{代表表現で表示} \\
&\;\rightarrow\; -0011 &&\qquad\fbox{負の数のこと} \\
&\;\rightarrow\; -3 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{alignat*}{2}
- 2 - 5 &\;\rightarrow\; - 0010 - 0101 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;\rightarrow\; \overline{0010} + \overline{0101} &&\qquad\fbox{負の数を補数の相方で置き換える} \\
&\;=\; 1110 + 1011 &&\qquad\fbox{(ビット反転プラス$1$)} \\
&\;=\; \color{gray}{1}1001 &&\qquad\fbox{計算した} \\
&\;=\; \overline{0111} &&\qquad\fbox{代表表現で表示(4桁目が1なので、ビット反転プラス1する)} \\
&\;\rightarrow\; -0111 &&\qquad\fbox{負の数のこと} \\
&\;\rightarrow\; -7 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{alignat*}{2}
2 \times 3 &\;\rightarrow\; 0010 \times 0011 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;=\; 0110 &&\qquad\fbox{計算した(下の筆算参考)} \\
&\;\rightarrow\; 6 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{align*}
\begin{array}{rr}
& \phantom{0000}0010 \\
\times & \phantom{0000}0011 \\ \hline
& \phantom{0000}0010 \\
& \phantom{000}\color{gray}{0}010\phantom{0} \\
& \phantom{00}\color{gray}{00}00\phantom{00} \\
& \phantom{0}\color{gray}{000}0\phantom{000} \\ \hline
& \color{gray}{000}0110
\end{array}
\end{align*}
\begin{alignat*}{2}
2\times(-3) &\;\rightarrow\; 0010 \times (-0011) &&\qquad\fbox{4ビット2進表示に変換} \\
&\;\rightarrow\; 0010 \times \overline{0011} &&\qquad\fbox{負の数を補数の相方に置き換える} \\
&\;=\; 0010 \times 1101 &&\qquad\fbox{(ビット反転プラス1)} \\
&\;=\; \color{gray}{1}1010 &&\qquad\fbox{計算した(下の筆算参考)} \\
&\;=\; \overline{0110} &&\qquad\fbox{代表表現で表示(4桁目が1なので、ビット反転プラス1する)} \\
&\;\rightarrow\; -0110 &&\qquad\fbox{負の数のこと} \\
&\;\rightarrow\; -6 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{align*}
\begin{array}{rr}
& \phantom{0000}0010 \\
\times & \phantom{0000}1101 \\ \hline
& \phantom{0000}0010 \\
& \phantom{000}\color{gray}{0}000\phantom{0} \\
& \phantom{00}\color{gray}{00}10\phantom{00} \\
& \phantom{0}\color{gray}{001}0\phantom{000} \\ \hline
& \color{gray}{001}1010
\end{array}
\end{align*}
\begin{alignat*}{2}
(-2)\times 3 &\;\rightarrow\; -0010 \times 0011 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;\rightarrow\; \overline{0010} \times 0011 &&\qquad\fbox{負の数を補数の相方に置き換える} \\
&\;=\; 1110 \times 0011 &&\qquad\fbox{(ビット反転プラス1)} \\
&\;=\; \color{gray}{10}1010 &&\qquad\fbox{計算した(下の筆算参考)} \\
&\;=\; \overline{0110} &&\qquad\fbox{代表表現で表示(4桁目が1なので、ビット反転プラス1する)} \\
&\;\rightarrow\; -0110 &&\qquad\fbox{負の数のこと} \\
&\;\rightarrow\; -6 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{align*}
\begin{array}{rr}
& \phantom{0000}1110 \\
\times & \phantom{0000}0011 \\ \hline
& \phantom{0000}1110 \\
& \phantom{000}\color{gray}{1}110\phantom{0} \\
& \phantom{00}\color{gray}{00}00\phantom{00} \\
& \phantom{0}\color{gray}{000}0\phantom{000} \\ \hline
& \color{gray}{010}1010
\end{array}
\end{align*}
\begin{alignat*}{2}
(-2)\times (-3) &\;\rightarrow\; -0010 \times -0011 &&\qquad\fbox{4ビット2進表示に変換} \\
&\;\rightarrow\; \overline{0010} \times \overline{0011} &&\qquad\fbox{負の数を補数の相方に置き換える} \\
&\;=\; 1110 \times 1101 &&\qquad\fbox{(ビット反転プラス1)} \\
&\;=\; \color{gray}{1011}0110 &&\qquad\fbox{計算した(下の筆算参考)} \\
&\;=\; 0110 &&\qquad\fbox{代表表現で表示(4桁目が0なので、4桁そのまま)} \\
&\;\rightarrow\; 6 &&\qquad\fbox{10進表示に変換} \\
\end{alignat*}
\begin{align*}
\begin{array}{rr}
& \phantom{00000}1110 \\
\times & \phantom{00000}1101 \\ \hline
& \phantom{00000}1110 \\
& \phantom{0000}\color{gray}{0}000\phantom{0} \\
& \phantom{000}\color{gray}{11}10\phantom{00} \\
& \phantom{00}\color{gray}{111}0\phantom{000} \\ \hline
& \color{gray}{1011}0110
\end{array}
\end{align*}
上の計算例の掛け算の筆算を見てください、2進法では掛け算は桁をずらす操作と、足し算の組み合わせで実行できます。
ディジタル回路では桁をずらす操作をビットシフトといいまして、簡単に実装することができます。
N=28 の例
次の例として $N=2^8=256$ の補数を考えて、整数もどきの数の世界を作ってみましょう。
$N=2^4$ の時と同様な操作で次の表(長くなるので先の例と行列を逆にしてる)を作ります。
この表のバー有り表現を負の数だとみなすことで、$-128$ から $127$ に収まる数の計算がすべてできるようになります。
丁度いいところで折り返したので、自然数の $8$ ビット目が、符号の表現を兼ねるようになります。
8ビット目が 0 の時はプラス符号、1 の時はマイナス符号、を表現してるようにみなせます。
2進法の場合は、ビット反転プラス1で、補数表現が簡単に計算できるので、表を作っておく必要すらありません。
(2進法と10進法との対応は表を作っておくと便利です。)
様々な数の演算(足し算・引き算・掛け算)をやってみましょう。
途中計算では自然数をそのまま、計算結果の最終的な表現では上の代表表現のみを使います。
良い頭の体操になりますので、自分で適当な数を設定して手計算してみてください。
前節の例で掛け算の例を行いました。
10進法で $10^n$ を掛ける操作は、全ての桁の数字を $n$ 桁左にずらす操作に対応します。
10進法の $2$ が、2進法では $10$ (イチ・ゼロ)と表現されます。
$2^n$ を掛ける操作は、$n$ 桁の左ビットシフトになります。
掛け算はビットシフトと足し算で実装されます。
10進法の割り算の筆算を思い出してください。
(こちら)のリンク先に解説があるので参考になります。
割り算は、掛け算と引き算の組み合わせです。
補数を利用した制限つきの整数で、負の数を表すことによって引き算を実行できるようになったので、割り算も実行できるようになります。
ここでは、8ビットの整数で、割り算をどのように実行するか、例題をやってみましょう。
例として $57\div 6$ の商 $9$ と、余り $3$ の計算を $N=2^{8}$ の補数を利用した2進表示でやってみましょう。
割る数 $6\rightarrow 00000110$、割られる数 $57\rightarrow 00111001$ で筆算をします。
\begin{align*}
\require{enclose}
\begin{array}{r}
00000110\enclose{longdiv}{00111001} \\[-3pt]
\end{array}
\end{align*}
$00000110$ に $00100000$ を掛ける演算は $00000110$ を 5ビット左にシフトする操作に対応します。
$00000110\times 00100000=\color{red}{1}1000000$ になってしまい、8ビット目が $\color{red}{1}$ の負の値を表現する数になってしまいます。
(これは、10進表記で $6$ に $2^5=32$ を掛けると $192$ になり、8ビットの最大数 $127$ を超えてしまうことに対応します。)
そうならないように、商の上位3ビット(6桁目~8桁目)は $0$ で埋めます。
\begin{align*}
\require{enclose}
\begin{array}{r}
000\phantom{00000} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\end{array}
\end{align*}
商の5桁目に $1$ を立てて、$00000110$ に $00010000$ を掛けたものを、$00111001$ から引きます。
$00100000$ の掛け算は4桁の左ビットシフトに対応します。
(これは、10進表記で $6$ に $2^4=16$ を掛けた $96$ を、$57$ から引くことに対応します。)
\begin{align*}
\require{enclose}
\begin{array}{r}
0001\phantom{0000} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{-\,01100000} \\[-3pt]
\end{array}
\end{align*}
引き算部分は補数の相方(ビット反転プラス1)の足し算で計算します。
引き算の結果の8ビット目が$\color{red}{1}$なので、負の数を表すことになりますので、「引き過ぎ」です。
商の5桁目は $\color{blue}{1 \mbox{ではなく} 0}$ だと確定します。
\begin{align*}
\require{enclose}
\begin{array}{r}
000\color{blue}{1}\phantom{0000} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,10100000} \\[-3pt]
\color{red}{1}1011001\\[-3pt]
\end{array}
\end{align*}
引き過ぎの計算をキャンセルします。
次に、商の4桁目に $1$ を立てて、$00000110$ に $000001000$ を掛けたものを、$00111001$ から引きます。
$000001000$ の掛け算は3桁の左ビットシフトに対応します。
(これは、10進表記で $6$ に $2^3=8$ を掛けた $48$ を、$57$ から引くことに対応します。)
\begin{align*}
\require{enclose}
\begin{array}{r}
000\color{blue}{0}1\phantom{000} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{-\,00110000} \\[-3pt]
\end{array}
\end{align*}
引き算部分は補数の相方(ビット反転プラス1)の足し算で計算します。
引き算の結果の8ビット目が $\color{red}{0}$ なので、正の数を表すことになり、商の3桁目は $1$ だと確定します。
\begin{align*}
\require{enclose}
\begin{array}{r}
00001\phantom{000} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
\color{gray}{1}\color{red}{0}0001001 \\[3pt]
\end{array}
\end{align*}
商の3桁目に $1$ を立てて、$00000110$ に $00000100$ を掛けたものを、残っている $00001001$ から引きます。
$00000100$ の掛け算は2桁の左ビットシフトに対応します。
(これは、10進表記で $6$ に $2^2=4$ を掛けた $24$ を、残っている $9$ から引くことに対応します。)
\begin{align*}
\require{enclose}
\begin{array}{r}
000011\phantom{00} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
00001001 \\[-3pt]
\underline{-\,00011000} \\[-3pt]
\end{array}
\end{align*}
引き算部分は補数の相方(ビット反転プラス1)の足し算で計算します。
引き算の結果の8ビット目が$\color{red}{1}$なので、負の数を表すことになりますので、「引き過ぎ」です。
商の3桁目は $\color{blue}{1 \mbox{ではなく} 0}$ だと確定します。
\begin{align*}
\require{enclose}
\begin{array}{r}
00001\color{blue}{1}\phantom{00} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
00001001 \\[-3pt]
\underline{+\,11101000} \\[-3pt]
\color{red}{1}1110001 \\[-3pt]
\end{array}
\end{align*}
引き過ぎの計算をキャンセルします。
次に、商の2桁目に $1$ を立てて、$00000110$ に $000000010$ を掛けたものを、残っている $00001100$ から引きます。
$000000010$ の掛け算は1桁の左ビットシフトに対応します。
(これは、10進表記で $6$ に $2^1=2$ を掛けた $12$ を、残っている $9$ から引くことに対応します。)
\begin{align*}
\require{enclose}
\begin{array}{r}
00001\color{blue}{0}1\phantom{0} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
00001001 \\[-3pt]
\underline{-\,00001100} \\[-3pt]
\end{array}
\end{align*}
引き算部分は補数の相方(ビット反転プラス1)の足し算で計算します。
引き算の結果の8ビット目が$\color{red}{1}$なので、負の数を表すことになりますので、「引き過ぎ」です。
商の2桁目は $\color{blue}{1 \mbox{ではなく} 0}$ だと確定します。
\begin{align*}
\require{enclose}
\begin{array}{r}
000010\color{blue}{1}\phantom{0} \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
00001001 \\[-3pt]
\underline{+\,11110100} \\[-3pt]
\color{red}{1}1111101 \\[-3pt]
\end{array}
\end{align*}
引き過ぎの計算をキャンセルします。
次に、商の1桁目に $1$ を立てて、$00000110$ に $000000001$ を掛けたものを、残っている $00001100$ から引きます。
$000000001$ の掛け算は0桁の左ビットシフトに対応します。
(これは、10進表記で $6$ に $2^0=1$ を掛けた $6$ を、残っている $9$ から引くことに対応します。)
\begin{align*}
\require{enclose}
\begin{array}{r}
000010\color{blue}{0}1 \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
00001001 \\[-3pt]
\underline{-\,00000110} \\[-3pt]
\end{array}
\end{align*}
引き算部分は補数の相方(ビット反転プラス1)の足し算で計算します。
引き算の結果の8ビット目が $\color{red}{0}$ なので、正の数を表すことになり、商の1桁目は $1$ だと確定します。
\begin{align*}
\require{enclose}
\begin{array}{r}
000010\color{blue}{0}1 \\[-3pt]
00000110\enclose{longdiv}{00111001} \\[-3pt]
\underline{+\,11010000} \\[-3pt]
00001001 \\[-3pt]
\underline{+\,11111010} \\[-3pt]
\color{gray}{1}\color{red}{0}0000011 \\[-3pt]
\end{array}
\end{align*}
商と余りが確定しましたので、10進表記に変換します。
\begin{align*}
\mbox{商} &\; 00001001 \rightarrow 9 \\
\mbox{余り} &\; 00000011 \rightarrow 3 \\
\end{align*}
長々と計算を追っていきましたが、やってることは10進法の割り算の筆算と同じことです。
「立てる」「掛ける」「引く」を、上の桁から順にやっているだけです。
10進法の場合は「立てる」数に $0\,,1\,,\ldots\,,9$ を試してみなければなりません。
(九九の暗記で、試してみる操作を素早くすることができるようになります。)
2進法の場合は、$0,\,1$ のみなので、$1$ を立ててみて、ダメなら即 $0$ に決定します。
慣れると、考えることなく機械的に計算できて簡単です。
ここでの例の割り算は、小学校で習った10進法の割り算の筆算に近いやり方です。
割り算には他にも様々なアルゴリズムが考えられていて、もっと効率の良いやり方もあります。
更に効率の良い割り算のアルゴリズムの開発は、現在でも重要な課題になっています。
足し算や掛け算に比べて手順数がたくさんあるので、割り算は時間がかかると思っていてください。
($2^n$ で割る計算に限っては「右ビットシフトを $n$ 回」で実行できますので、超速です。)
昔は「繰り返しループ中の割り算は、なるべく避けて、掛け算で代用できるなら代用する」のがプログラミングの鉄則でした。
最近はコンパイラの進歩等で自動的に最適化されることが多いので、割り算を避けろとはあまり言われなくなっています。
合わせて $N$ の補数を利用することによって、半分の自然数をゼロ又は正の数として、もう半分の自然数を負の数として、範囲付きの整数を表現することができるようになりました。
表現する整数の範囲は次のように定めました。
\begin{alignat*}{2}
\mbox{合わせて $N$ の補数を利用して、扱う整数の範囲} &\quad:\quad \left[-\frac{N}{2}, \frac{N}{2} \right) \\
\end{alignat*}
$N=2^n$ の、2進法 $n$ ビットで扱う整数の、最大数は $2^{n-1} -1$ に、最小数は $-2^{n-1}$ になります。
コンピュータでよく使う、整数データの最大数と最小数をまとめておきます。
バイト数 | ビット数 | 最小数 | 最大数 | 最大数の目安(10進桁数) |
$n/8$ | $n$ | $-2^{n-1}$ | $2^{n-1}-1$ | $\log_{10}2^{n-1}$ 桁 |
$1$ | $8$ | $-128$ | $127$ | $2.1$ 桁 |
$2$ | $16$ | $-32\,768$ | $32\,767$ | $4.5$ 桁 |
$4$ | $32$ | $-2\,147\,483\,648$ | $2\,147\,483\,647$ | $9.3$ 桁 |
$8$ | $64$ | $-9\,223\,372\,036\,854\,775\,808$ | $9\,223\,372\,036\,854\,775\,807$ | $18.9$ 桁 |
計算結果が最大数を上回ってしまうことをオーバーフロー(overflow)といいます。
計算結果が最小数を下回ってしまうことをアンダーフロー(underflow)といいます。
オーバーフローやアンダーフローが起こってしまうと、とんでもない結果がでてしまいますので、範囲を越えない計算を行うように注意しましょう。
4バイト整数の最大は約20億は暗記しておいた方がよいと思います。