Qiitaからの移植です。

これは数学とコンピュータ Advent Calendar 2017の20日目の記事です。計算機科学の基本的な内容について話そうと思います。元ネタはとある本に書いてあった内容ですが、どの本だったのかはよく覚えていません¹。

ここで問題です

皆さんは次の引き算はできますか？

$15 - 8$

はい、簡単ですね。答えは $7$ です。さて、この引き算はどうでしょう？

$30021 - 15497$

答えは $14524$ です。はい、面倒くさいですね。繰り下がりとかを考えて筆算で計算しないといけません。

複雑な筆算を避ける

繰り下がりとかを考えると、引き算は面倒ですね。そこで複雑な筆算を避ける引き算をやってみましょう。今から示す方法では

があればできます。手順は次の通りです。

手順を見ただけではピンとこないと思うので、具体例を使いましょう。まずは、 $15-8$ で上の手順を追ってみます。

はい、無事に答え $7$ にたどり着きました。

次に $30021 - 15497$ を同じ手順で実行してみましょう。

こちらも無事に答えにたどり着きました。

具体例を使って説明しましょう。例として $15-8$ で説明しましょう。

$\begin{align} 15 - 8 &= 15 - 08 \\ &= 15 - 08 + (99 + 1 - 100) \\ &= 15 + (99 - 08 + 1) - 100 \end{align}$

この変形がすべてを物語っています。手順2は $(99-08+1)$ に、手順3は最後の $-100$ に対応しています。手順1の0埋めは、 $100$ と引くという作業を最上位の桁の数字を無視するだけという簡単な作業に落とし込むためです。

念のために$30021-15497$もでも同じ変形をしてみましょう。

$\begin{align} 30021 - 15497 &= 30021 - 15497 + (99999 + 1 - 100000) \\ &= 30021 + (99999 - 15497 + 1) - 100000 \end{align}$

コンピュータでは数は2進数で表現されます。2進数の場合、手順2では引き算すら出てこなくなり、ビットを反転して最後に1を足すだけの作業になります。つまり、引き算を足し算だけで行うことができるようになるのです。

足し算だけで済むようになると、引き算用にわざわざ論理回路を作る必要がなくなり、コンピュータの設計で楽になるのです。詳しくは「2の補数²」等のキーワードで検索してください。