Qiitaからの移植です。
これは数学とコンピュータ Advent Calendar 2017の20日目の記事です。計算機科学の基本的な内容について話そうと思います。元ネタはとある本に書いてあった内容ですが、どの本だったのかはよく覚えていません1。
ここで問題です
皆さんは次の引き算はできますか?
はい、簡単ですね。答えは $7$ です。さて、この引き算はどうでしょう?
答えは です。はい、面倒くさいですね。繰り下がりとかを考えて筆算で計算しないといけません。
複雑な筆算を避ける
繰り下がりとかを考えると、引き算は面倒ですね。そこで複雑な筆算を避ける引き算をやってみましょう。今から示す方法では
- 足し算の知識
- 9から1桁の数を引くことができるレベルの引き算の知識
があればできます。手順は次の通りです。
- 適当に0埋めして、引かれる数と引く数の桁数を揃える
- 引く数の変換:各桁の数字を9から引き、最後に1を足す
- 引かれる数と変換後の引く数を足して、最上位の桁にある1を無視
手順を見ただけではピンとこないと思うので、具体例を使いましょう。まずは、で上の手順を追ってみます。
はい、無事に答えにたどり着きました。
次にを同じ手順で実行してみましょう。
- 0埋めの必要なし
こちらも無事に答えにたどり着きました。
なぜこの手順でOKなのか?
具体例を使って説明しましょう。例としてで説明しましょう。
この変形がすべてを物語っています。手順2はに、手順3は最後の
に対応しています。手順1の0埋めは、
と引くという作業を最上位の桁の数字を無視するだけという簡単な作業に落とし込むためです。
念のために$30021-15497$もでも同じ変形をしてみましょう。
コンピュータと何か関係あるの?
コンピュータでは数は2進数で表現されます。2進数の場合、手順2では引き算すら出てこなくなり、ビットを反転して最後に1を足すだけの作業になります。つまり、引き算を足し算だけで行うことができるようになるのです。
足し算だけで済むようになると、引き算用にわざわざ論理回路を作る必要がなくなり、コンピュータの設計で楽になるのです。詳しくは「2の補数2」等のキーワードで検索してください。
-
たぶん『エレガントな解答をもとむ selections』です。間違っていたらすみません。↩
-
2の補数については、@marmot1123 さんが書いた本Advent Calendar初日の記事で触れられています。↩