二の補数

二の補数は、コンピューターで符号付き整数を表す代表的な方式だ。n ビット語の最上位の重みを +2ⁿ⁻¹ から −2ⁿ⁻¹ に変え、8 ビットなら −128–127 を表す。全ビットを反転して 1 を加えると符号反転になり、減算を加算へ変えられる。

符号なし用の加算器で、符号別の分岐なしに符号付きパターンも加えられる。最上位を独立した符号フラグにする符号絶対値方式と違い、符号を位の重みに組み込む。数学的な和が範囲に収まれば正しい符号付き結果となり、収まらなければオーバーフローの検出が必要だ。

最上位も位の重み

符号なしの 10110101 は 128+32+16+4+1=181。二の補数は最高位の重みだけを変える。ビット 6 は 64、ビット 0 は 1 のままだ。

11111100 は −128+64+32+16+8+4=−4 となる。負数の最上位は 1 で、合計を負にできる唯一の列だ。ただし独立して反転する標識ではなく、加算に参加する重みである。

任意の 8 ビットパターン x と、その反転 ~x は各列でちょうど一方だけが 1 になる。その和 11111111 は二の補数で −1。固定幅の剰余演算として整理すると ~x+1=−x が得られる。最小負数の数学的な反対符号は収まらず、そのビットパターンへ戻る。

列ごとの加算器は二つの入力ビットと桁上がりを足し、下位ビットを書き、上位ビットを次列へ渡す。符号を検査しない。最上位の外へ出たキャリーを捨て、法 2ⁿ の下位 n ビットを残す。符号付きの範囲を越えたかは別に判定する。

ステップ実行

既定例は x = 4 を 8 ビットで符号反転する。元のパターン、反転、結果の三行を表示する。

1. 左から −128、64、32、16、8、4、2、1 の 8 列を用意する。別のマイナス記号の位置はない。
2. 絶対値 |x| = 00000100 を書く。重み 4 の列だけが 1。
3. 全ビットを反転して 11111011 にする。各列は独立して反転する。これは一の補数で、まだ −4 ではない。
4. 1 を加える。末尾二つの 1 を消してキャリーを左へ送り、ビット 2 で受け止める。結果は 11111100。5 の場合は反転後 11111010 のビット 0 が既に 0 なので、この連鎖は起きない。
5. 正の重みを足す。ビット 6、5、4、3、2 は 64+32+16+8+4=124。全体を符号なしと誤読すると 252 になる。
6. 最上位の −128 を加え、124−128=−4 を得る。
7. 完了。11111100 を再び反転して 1 を足すと 4 に戻り、操作を確認できる。

構築中の行を明るくし、完了した行は参照用に薄くする。列の下の正の重みはまとめて点灯し、続いて負の最上位の重みが加わって合計が完成する。

一つの加算器で処理できる理由

add へ切り替えると、既定値は a = 5（00000101）、b = −3（11111101）。普通のリップルキャリー加算器がビット 0 から処理する。

結果は 00000010=2 で、5+(−3)=2 と一致する。別の減算回路の規則は使っていない。最上位から出たキャリーを捨てても結果は正しく、破棄自体はエラーを意味しない。

符号付きオーバーフローは、最上位へ入るキャリーと出るキャリーが異なるときに起きる。上例では両方 1 なので発生しない。Overflow: 127 + 1 は入力キャリー 1、出力 0 で不一致となる。数学的な和 128 は範囲外で、残る 10000000 は −128 と読まれる。

アニメーションは比較結果を示すが例外を発生させない。ハードウェアフラグや言語の検査は異なり、符号付きオーバーフローを常に無言の折り返しとは見なせない。トレースは中間値を n ビットへマスクして固定幅を表す。レジスターが低位を保存しても、C の符号付きオーバーフローは未定義で、Rust は検査して panic する場合がある。

境界ケース

• 範囲は非対称。8 ビットには −128 があるが +128 はない。−128 のパターンを反転して 1 を足すと再び 10000000 になる。数学的な絶対値が負なのではなく、+128 が同じ型に入らない。abs(INT_MIN) が有効な正数を返すと仮定してはいけない。
• ゼロは 00000000 の一種類。一の補数と符号絶対値方式には負のゼロもあり、二つのパターンを等しく扱う必要がある。
• 出力キャリーはオーバーフローではない。5+(−5) はキャリーが出ても正しく 0、127+1 はキャリーが出なくてもオーバーフローする。
• 4 ビットでは範囲が −8–7 となり、7+1 は −8 のパターンを残す。規則は同じで範囲だけが狭い。
• 負数の右シフトは二種類ある。算術シフトは符号ビットを埋め、論理シフトはゼロを埋める。後者を正の量だけ行うと負のパターンが非負になり得る。選択は言語と型に依存する。

よくある間違い

• 最上位を独立した符号フラグとして反転する。それは符号絶対値の発想であり、二の補数の符号反転は全反転と加算 1 が必要。
• 一の補数で止める。11111011 は −4 でなく −5。
• 出力キャリーだけで検出する。5+(−5) を誤報し、127+1 を見逃す。最上位の入力と出力キャリーを比べる。
• 言語が符号付き折り返しを保証すると考える。C と C++ では符号付きオーバーフローは未定義で、最適化は起きないと仮定できる。そのため if (x + 1 < x) のような検出が除去され得る。
• 符号付きと符号なしを混ぜて比較する。一般的な環境で int と size_t を比べると符号なしへ変換され、−1 が大きい正値になる。厳密な変換は型の順位と表現範囲に従い、符号付きの順序が残るとは限らない。