転を行えばよいのです。
3
このことから、000001012の補数を求める操作とは、000001012の各bitを反転し、その後に12
4
を加える、という操作と考えることができます。単純な bitの反転と12の加算のみです。そのた
5
め、補数は非常に簡単に求めることができるのです。
6
一般化して述べます。nbitの2進数bnbn−1...b2b1の補数を求めるには、以下の2段階の操作を
7
行います。
8
• bnbn−1...b2b1の各bitの0/1を反転し、2進数cncn−1...c2c1を求めます。このcncn−1...c2c1
9
をbnbn−1...b2b1の1の補数(1’s complement)と呼びます。
10
• cncn−1...c2c1に12を加えます。求められた補数を、1の補数と対比して、特に2の補数(2’s
11
complement)と呼びます。
12
考察 (1) 8 bitの2進数000000002の補数が000000002であることを確認しなさい。(2) 8 bit
13
の2進数000000012の補数が111111112であることを確認しなさい。
14
+ 6
1 0 0 0 1
5桁目への繰り上がりを無視すれば、1が求められています。
5
もうひとつは、(−510)∗(−510) = 2510 となる事実です。
6
9 9 9 5
× 9 9 9 5
4 9 9 7 5
8 9 9 5 5
8 9 9 5 5
+ 8 9 9 5 5
9 9 9 0 0 0 2 5
7
5桁目以上を無視すれば、25が求められています。
8
10進数の補数を簡単に求めるには、まず各桁が9であるような数から対象とする数を引きます。
9
たとえば−12310 の場合、以下の通りです。
10
9 9 9 9 ...被減算数
− 0 1 2 3 ...減算数
9 8 7 6 ...減算結果
11
このようにして求められた数を 9の補数 と呼びます。次に、これに1を加えると、9877 を得ま
12
す。これが −12310を表す数です。この数を 10の補数 と呼びます。
13
このようにして私たちがよく知る10進数においても補数の概念は成り立つことが理解できます。
14
10.7 補数表現を用いた計算の理屈
15
(ここの内容は期末試験対象外です。参考程度に理解してください)
16
何故、補数表現は加減乗算に正しい結果を与えるのでしょうか。
17
簡単のため、8 bit の場合を考えます。−12810から12710の中の任意の数m、nが与えられた 時、その補数表現C(m)、C(n)を以下の式で定義します。
C(m) = (256M+m)mod256, C(n) = (256N+n)mod256
ただしM、Nは1以上の任意の正数とします。すなわちC(m)の値は、mに256の倍数 (256、
18
512、768、...などの数) を加え、256の剰余を求めたものであると定義します。
19
C(m) +CC(n) = (C(m) +C(n))mod256, C(m)×CC(n) = (C(m)×C(n))mod256 と定義します。そうすると以下が成り立ちます。
C(m) +CC(n) = (C(m) +C(n))mod256
= ((256M +m)mod 256 + (256N+n)mod256)mod 256
= (256M +m+ 256N+n)mod256
= (256(M +N) + (m+n))mod256
= (256M′+ (m+n))mod256 (M′=M+N)
= C(m+n)
すなわち、mとnのそれぞれの補数表現の和は、mとnの和の補数表現に等しいのです。減算は、
減算数を符号反転することで加算に置換できます。積についても同様の式の変形が可能です。
C(m)×CC(n) = (C(m)×C(n))mod256
= (((256M +m)mod256)×((256N+n)mod256))mod256
= ((256M+m)×(256N+n))mod256
= (2562M N + 256(M n+N m) +mn)mod256
= (256N′+mn)mod256 (N′ = 256M N+ (M n+N m))
= C(mn)
これらのことから、負数を含む整数の加減乗算を行うには、演算する正負の数をそれぞれ補数で表
1
現しておき、補数間の加減乗算を行い、最終的に得られた演算結果の補数表現を元の正負の数の表
2
現に変換することで実現可能です。もちろん、その際にはオーバーフローが起きないことが前提で
3
す。なお、除算は取り扱いが複雑になるため、この講義では考えません。
4
います。私たちは9章、10章を通して、既に2進数には十分に慣れ親しみましたから、この章で
4
は8章を補足説明します。
5