2の補数

6 + 4 = 10 である． このとき，4 は 10 に対する 6 の補数であるという． 補数は，余数とも呼ばれる．
補数を用いれば，減算(M - N)を加算(M + [Nの補数])に変換して求めることができる． →補数を利用した減算の説明

コンピュータでは負の整数を表現する際に，補数が使用される．
Nを正の整数とするとき， 負数 -N を2の補数である 2^K-N により表す． (ただし，0≤N≤2^K-1)

[例] 2³の補数

2³(=8)の補数

N	1	2	3	4
-N	-1	-2	-3	-4
補数	7	6	5	4
ビット列	111	110	101	100

3ビットを使って2進数をカウントアップする

  000, 001, 010, 011, 100, 101, 110, 111, 000, 001, 010, 011, 100, 101, ...

ここで，111から000へカウントアップする場合の桁溢れは無視している．

負数の表現に補数を用いると， 次のように数値を割り当てることができ，たし算をする場合に都合がよい。

...,	0002,	0012,	0102,	0112,	1002,	1012,	1102,	1112,	0002,	0012,	0102,	0112,	1002,	1012,	...
					-4	-3	-2	-1	0	1	2	3

M, N を2進数 K-1 ビットで表される正の整数とする． このとき，0≤N<2^K-1, 0≤M<2^K-1である．

このMとNの減算，M-Nの補数を利用した計算方法を説明する．

      M + (2K - N)  = M - N + 2K

• M ≥ N の場合は，2^K は桁溢れ分となり， 桁溢れを無視すると，減算値と一致する
• M < N の場合は，加算結果(M-N+2^K)の補数を求めると，

        2K - (M - N + 2K) = N - M
  

  であるから，減算値の補数と一致する．
  なお，この場合は，必ず，M-N+2^K > 2^K-1 となり， 2進数Kビットで表したときの先頭は1になる．

例えば，2進数3ビットの場合， 2₁₀=010₂に対する2³(=8)の補数は 6(=8-2)であり，6₁₀=110₂であるから，

       0112  (=  310)
    +) 1102  (= -210)
    ------------------------
      10012  桁溢れを無視すると  0012 (=  1)

次に，3に対する2^{3(=8)の端数は 5₁₀=101₂であり，}

       0102  (=  210)
    +) 1012  (= -310)
    ------------------------
       1112　　桁溢れなし

• 符号ビットが0の場合は0または正整数であり， ピットパターンを2進表現と解釈する
• 符号ビットが1の場合は負整数である．
  桁溢れを除いて， そのビットパターンに加算したとき結果が0になるよう加える数にマイナス符号(-)を付けた数値を表現する

      n + m = 11...12

      n + m + 1 = 000...0002 = 0

      n = -(m+1)

• n = -{(ビットパターンの0と1を入れ替える) + 1}

      m = (-n) - 1 = |n| - 1

1. 符号を取り除いた値を2進数で表す
2. 先頭に0を追加する
3. 下位の桁から，上位へ向かって次の操作をする
   • その桁の値が1であれば，それを1のままにして， 残りの上位のすべての桁の0と1を入れ替える．その後，操作を終える
   • その桁の値が0であれば，0のままにして，隣の上位の桁を調べる

[例]  -3を4桁の補数で表す．

         3 = (0001)2  →  1101

[例]  -20を8桁の補数で表す．

• 20=10100₂ であるから，20を8桁の２進数で表記すると 00010100

         20 = (00010100)2  →  11101100

[別法]

• 20 = 00010100₂
• 下位の桁から，順に上位へ向かって調べると，下から３桁目に初めて1が現れる． (00010100)
• 下から４桁目とその上位桁のすべての，0と1を入れ替える． (11101100)
• 以上の操作により -20 = 11101100₂ が求まる