C/C++の算術加算でオーバーフローが起きる仕組み｜2の補数による検出方法

2の補数とは

2の補数（2's Complement）は、コンピュータアーキテクチャにおいて最も広く採用されている符号付き整数の表現方式です。

Nビットの2の補数システムでは、-2^n-1 ～ 2^n-1-1 の範囲の整数を表現できます。具体例は以下の通りです。

• 4ビットの場合： -8 ～ 7
• 5ビットの場合： -16 ～ 15

オーバーフローが発生する仕組み

2つのNビットの2の補数を加算した結果が、Nビットで表現できる範囲を超えると「オーバーフロー」が発生します。

コンピュータ内部には固定長のNビットレジスタが搭載されており、2つのNビット数の加算結果は最大でもN+1ビットになります。この余分な1ビットはキャリーフラグに格納されますが、キャリーが発生しても必ずしもオーバーフローを意味するわけではない点に注意が必要です。

オーバーフローの検出方法

加算時にオーバーフローが発生するのは、主に次のようなケースです。

• 負の数同士を加算した結果が正になる場合
• 正の数同士を加算した結果が負になる場合

そのため、2つのオペランドと演算結果それぞれの最上位ビット（MSB：Most Significant Bit）を確認すれば、オーバーフローを検出できます。

しかし、3ビットコンパレータを実装しなくても、MSBからのキャリーイン（Carry-in）とキャリーアウト（Carry-out）だけを比較する2ビット構成でもオーバーフロー検出は可能です。ここでは、2の補数によるNビット加算を例に考えてみましょう。

オーバーフローは「キャリーインとキャリーアウトが一致しない」場合に発生します。この条件が成り立つ理由を、以下の分析で詳しく見ていきます。

ケース1： 2つの数のMSBがどちらも0の場合、両方とも正の数です。ここでキャリーインが1になると、結果のMSBが1となり、結果が負であることを示します（＝オーバーフロー）。このときキャリーアウトは0です。キャリーインとキャリーアウトが一致しないため、オーバーフローが発生していることが分かります。

ケース2： 2つの数のMSBがどちらも1の場合、両方とも負の数です。ここでキャリーインが0になると、結果のMSBが0となり、結果が正であることを示します（＝オーバーフロー）。このときキャリーアウトは1です。こちらもキャリーインとキャリーアウトが一致しないため、オーバーフローが発生しています。

つまり、MSBにおけるキャリーインとキャリーアウトを確認するだけで、オーバーフローを確実に検出できるのです。

上図のように、XORゲートを使えばオーバーフロー検出回路を簡単に実装できます。キャリーインとキャリーアウトが異なる場合にXORの出力が1となるため、その出力をオーバーフローフラグとして利用できるのです。