2025/10/01

補数と引き算

本記事の目的

この記事では、コンピュータで負の数を表現する方法の一つである補数表現について解説する。また、補数を用いた足し算で引き算を実現する方法について解説する。

まずは馴染み深い十進数で考えることにする。

例えば \(6532 + 7644\) は

\[\begin{array}{r} 6532 \\[-3pt] \underline{+ \phantom{0}7644} \\[-2pt] (1) 4176 \end{array}\]

であるから、頭の (1) は無視して \(6532 + 7644 = 4176\) となる。

ところで、この電卓は、足し算はできるが引き算ができない、とする。その状況で何とか引き算を行う方法を考えてみよう。

例として \(6532 - 2356 = 4176\) をやってみる。この電卓では１万の位は無視しているから、数式に１万を足したり引いたりしても結果が変わらないことに気が付けば、

\[\begin{array}{r} 6532 \\[-3pt] \underline{- \phantom{0}2356} \end{array}\]

は

\[\begin{array}{r} 6532 \\[-3pt] + \phantom{0}10000 \\[-3pt] \underline{- \phantom{01}2356} \end{array}\]

を計算すれば良い事が分かる。ここで \(10000 - 2356 = 7644\) である。（引き算ができないのにこの計算をどうするのかという問題が残るが、一旦それは横に置いておいて）先ほどの足し算の例で見たように、上記の計算は

\[\begin{array}{r} 6532 \\[-3pt] \underline{+ \phantom{0}7644} \\[-2pt] 4176 \end{array}\]

となって、\(6532 - 2356\) の答えである \(4176\) が得られる。

この例のように 2356 を引く代わりに 7644 を足すことで、引き算をせずに、足し算で引き算を行うことができた。

このように 2356 にある別の数を足して、桁あふれ（繰り上がり）を発生させる最小の数を 2356 の補数という。もう少し具体的には、基数を指定して、「7644 は 2356 の 10 の補数」であると言う。

さて、補数を使えば、足し算をすることで引き算ができると分かったが、補数を求めるために \(10000 - 2356\) と引き算をしているのでは意味がない。

そこでさらに少し工夫して \(10000 = 9999 + 1\) と分解しておき、計算の順序を入れ替えることで \(+ 10000 - 2356 = + 9999 - 2356 + 1\) と変形できるから、

\[\begin{array}{r} 6532 \\[-3pt] + \phantom{0}9999 \\[-3pt] - \phantom{0}2356 \\[-3pt] \underline{+ \phantom{0000}1} \end{array}\]

そして、\(9999 - 2356\) を先に計算すれば

\[\begin{array}{r} 6532 \\[-3pt] + \phantom{0}7643 \\[-3pt] \underline{+ \phantom{0000}1} \end{array}\]

となり、足し算だけの式に変形できた。やはり引き算が残っているように見えるが、先ほどまでの引き算と根本的に違うのは、引かれる数の全ての位が最大の９になっている。この引き算では繰り下がりが決して発生しない。つまり、それぞれの位ごとに引き算ができればよい。

以前の記事で、ビット演算 (Bitwise Operators) を解説しているので、そちらも読んでおいてほしいが、各ビット（各位）毎に演算を適用するというのは、繰り上がりや繰り下がりで他の位の計算結果に依存する演算に比べてコストが低い。

それでも９から引くという計算が残っているがこれは、単純に各位毎に \(0 \leftrightarrow 9, 1 \leftrightarrow 8, \ldots,\) というような変換を行うだけで良いから、演算コストはそれほど高くない。

今は十進数で説明しているため、ここで９から引くという引き算が入っているように見えるが、実際にはコンピュータの世界では二進数が基本であり、その場合は、\(1 - x\) という計算は、 \(x\) の 0 と 1 を入れ替えるという演算で実現できる。

つまり 1111 - x = ~x (not x) または 1111 - x = 1111 ^ x (x と 11…1 の xor) で計算できるので、引き算をすることなく、補数を求めることができる。

tags: