はじめに
Method of complementsを使った計算について記載します。
補数を使った計算のことです。
Wikipediaには次のように説明されています。
正の数の加算を使って減算する方法とあります。
またmechanical calculatorで使われていたとあります。
In mathematics and computing, the method of complements is a technique used to subtract one number from another using only addition of positive numbers. This method was commonly used in mechanical calculators and is still used in modern computers.
コンピュータではTwo's complementを負の数とみなします。
では、なぜコンピュータではTwo's complementで負の数を表現するのでしょうか。
次の理由があると思います。
- 加算を使って減算できる：減算を負の数の加算とする
- Two's complementを容易に計算できる：ビット反転と+1で計算できる
- 正、負が容易に判定できる：先頭bitが0→正、1→負になる
用語・記法
使用する記号を説明します。
2進数と10進数が頻繁にでてきます。混乱を避けるために、
2進数の最後にb(binary)をつけます。
桁数を$n$とします。基数を$b$とします。例を示します。
- 4桁の2進数はn=4, b=2です。具体例 1001b
- 5桁の10進数はn=5, b=10です。具体例 12789
ある数 $x$ のradix complementを$\bar{x}^{b}$と表記します。
桁数をnとすると$\bar{x}^{b} = b^n - x$です。
b=10の場合、$\bar{x}^{10} = 10^n - x$です。Ten's complementといいます。
b=2の場合、$\bar{x}^{2} = 2^n - x$です。Two's complementといいます。
と表記します。文脈からbが明らかな場合は単に$\bar{x}$と表記します。
ある数とそのradix complementを足すと桁あふれします。
$\bar{x}^{b} + x = b^n ： 桁あふれが発生する$
radix complementを-1したものをdiminished radix complementといいます。
$\bar{x'}^{b-1}$と表記します。
桁数をnとすると$\bar{x'}^{b-1} = b^n - 1 - x$です。
b=10の場合、$\bar{x'}^{9} = 10^n - 1 - x$です。Nines' complementといいます。
b=2の場合、$\bar{x'}^{1} = 2^n - 1 - x$です。Ones' complementといいます。
ある数とそのdiminished radix complementを足すと桁あふれ直前の値になります。
$\bar{x'}^{b-1} + x = b^n - 1 ： 桁あふれする直前の値$
b=10の場合、$\bar{x'}^{9} + x = 999...999(9がn個並ぶ)$となります。
b=2の場合、$\bar{x'}^{1} + x = 111...111(1がn個並ぶ)$となります。
Nines' / Nine's の違い
少し脱線しますが、
Nines' / Ones' complementの'(apostrophe)の位置には意味があります。
Nines' complementは"9がたくさん並んだもの"のcomplementというニュアンスがあります。
例. n=4, b=10とすると 1234のNines' complementは 9999 - 1234 = 8765です。
'(apostrophe)の位置を変えてNine's complementにすると9進数の10000に対するcomplementと解釈できるわけです。
つまり、次の通りです。
Nine's -> b=9のradix complement
Nines' -> b=10のdiminished radix complement
文脈から明らかになることが多いのでこのような勘違いをする人は少ないと思います。
WikiPedia(word:Method of complements)には次のように記載されています。
Most writers use one's and nine's complement, and many style manuals leave out the apostrophe, recommending ones and nines complement.
上記のような'(apostrophe)の使用方法は推奨されていますが、
使い分けている書き手は少数派のようです。
Ten's complement
Two's complementの前に、我々に馴染みの深い10進数でのTen's complementを説明します。
桁数は3桁で考えます。n=3, b=10です。
Ten's complementは次の式で計算します。これが定義です。
$\bar{x} = 10^{n} - x = 10^{3} - x = 1000 -x$
上記を移項するとわかるのですが桁数は3桁で考えていますので
$x + \bar{x} = 1000$となり、ちょうど桁あふれします。
ある数がちょうど桁あふれする数をTen's complementと定義したのです。
$x$に具体値を入れてみます。$x=123$とします。
$\bar{123} = 10^{3} - 123 = 1000 - 123 = 877$
つぎにTen's complementを使って減算してみます。
400から123を引く計算を400に$\bar{123}$を足す計算に置き換えることで
減算を加算で代用します。
$400 - 123 → 400 + \bar{123} =$
$400 + (1000 - 123) = 400 + 877 = 1277 =$
$1000 + 277 → 277$
3桁で考えているので、桁あふれを無視すると277という正しい答えになりました。
1000を足しておいて後から1000を引いた(桁あふれを無視した)ためです。
Two's complement
次にコンピュータで負の数、減算に利用されるTwo's complementを説明します。
Ten's complementと同様に考えることができます。
Two's complementは次の式で計算します。これが定義です。
n=4です。
$\bar{x} = 2^{n} - x = 2^{4} - x = 10000b - x$
上記を移項するとわかるのですが桁数は4桁で考えていますので
$x + \bar{x} = 10000b$となり、ちょうど桁あふれします。
ある数がちょうど桁あふれする数をTwo's complementと定義したのです。
$x$に具体値を入れてみます。$x=0011b$とします。
$\bar{0011b} = 2^{4} - 0011b = 10000b - 0011b = 1101b$
Two's complementの計算は上記の通り行うと減算が必要になります。
減算なしでTwo's complementを求めることができます。
- 0011bの各ビットを反転します。つまり1を0に、0を1にします。
- 1100bとなります。これをOnes' complementといいます。
- 次に1を足します。
- 1101bとなります。これがTwo's complementです。
ビット反転と加算でTwo's complementが計算できました。
つぎにTwo's complementを使って減算してみます。
0111b(7)から0011b(3)を引く計算を0111bに$\bar{0011b}$を足す計算に置き換えることで
減算を加算で代用します。
$0111b - 0011b → 0111b + \bar{0011b} =$
$0111b + (10000b - 0011b) = 0111b + 1101b = 10100b =$
$10000b + 0100b → 4$
4桁で考えているので、桁あふれを無視すると4という正しい答えになりました。
10000bを足しておいて後から10000bを引いた(桁あふれを無視した)ためです。
2進数の加算、減算
変数α, βについて加算(add)、減算(sub)の組み合わせを考えます。
計算結果がγです。
α op β = γ
と表現します。
α, β は正(+) or 負(-);Two's complement、opは加算(add) or 減算(sub)です。
減算は負の数との加算とみなします。 つまりα sub β = α add (-β)です。
次の組み合わせが考えられます。
| # | α | op | β | comment |
|---|---|---|---|---|
| 1 | + | add | + | |
| 2 | + | add | - | |
| 3 | + | sub | + | same as #2 ;+ add - |
| 4 | + | sub | - | same as #1 ;+ add + |
| 5 | - | add | + | |
| 6 | - | add | - | |
| 7 | - | sub | + | same as #6 ;- add - |
| 8 | - | sub | - | same as #5 ;- add + |
#3 #4 #7 #8は別の項目と同じなので#1 #2 #5 #6が残ります。
桁数n=4とするとα、β、γのビットと計算の対応は以下となります。
CFはCarry(or borrow) Flagです。0はCarryなし、1はCarryありです。
OFはOverflow Flagです。0はOverflowなし、1はOverflowありです。
CF と OFの違いについては後で説明します。
table Aは#、α、βの符号、OF=0で期待されるγの符号の対応です。
#1は正の数の加算なので結果は正となります。負になるとOverflowが発生します。
#6は負の数の加算なので結果は負となります。正になるとOverflowが発生します。
#2,5は正と負の加算なので符号は場合によりますがOverflowは発生しません。
CF flagはopに依存します。addの場合はγがビット幅を超えた時にCF=1になります。
subの場合はβがαよりも大きいときにCF=1になります。これはBorrowです。
CF と OF
演算結果が表現できる範囲を超えた時にoverflowといいます。
整数演算では2種類のoverflowがあります。
- 符号なしoverflow、Carry Flag(CF=1)で表現します。
- 符号ありoverflow、Overflow Flag(OF=1)で表現します。