符号付き整数加減算のオーバーフロー・フラグ

いにしえの話ですけど、 8 ビット・プロセッサで最初に普及したインテル 8080 プロセッサには、 2 の補数表現での符号付き整数加減算にオーバーフロー・フラグがなく、 符号なし整数加減算の桁あふれを表すキャリー・フラグしかありませんでした。 そのため、 8080 で 2 の補数表現符号付き整数の加減算と比較演算をするときは、 自力でオーバーフロー・チェックを機械語で記述しなければならなくて、 面倒な思いをしたものです。 モトローラの 6800 にはオーバーフロー・フラグがあり、 条件分岐命令も符号付きと符号なしのそれぞれで大小比較の分岐ができるようになっていました。 8080 系統では、 その後にザイログ Z80 プロセッサが、 パリティ・フラグのビット位置をオーバーフロー・フラグに流用するようになって、 ようやく符号付き整数を楽に利用できるようになったのでした。

8080 機械語プログラミング当時と似たことが C 言語でずっと続いています。 C 言語では長らく符号付き整数演算のオーバーフローをどう扱うべきか規格にすることを避けつづけてきました。 GCC 5 からは、 ビルトイン関数でオーバーフロー検出付きの整数の加減乗除を符号付き・符号なしの両方を提供しています。 便利になりましたが、 これはコンパイラ依存の独自機能なので、 移植性を考慮して遅いけれどポータブルな方法も選べるようにしておきたいわけです。

論理回路でオーバーフロー・フラグの求めるには、 最上位の符号ビットのフルアダーのキャリー入力とキャリー出力の排他的論理和をとります。 これを 4 ビットの符号付き整数加減算に対して、 ソフトウェアで真似してみます。

まず、 フラグの値を表にして出力する手続きを用意します。 ブロックの値が真なら 1 と、偽なら ゼロと出力します。

def list_flag_table
  puts '                             a'
  puts '    ' + (-8 .. 7).map{|a| '%2d' % [a] }.join(' ')
  (-8 .. 7).reverse_each do |b|
    s = ' %2d ' % [b]
    s[0] = 'b' if b == 0
    (-8 .. 7).each do |a|
      flag = yield a, b
      s += '%2d ' % [flag ? 1 : 0]
    end
    puts s
  end
  true
end

まずは、 オーバーフローになるべき組を求めてみましょう。 例えば、7 と 1 の加算は 8 なので、 範囲外になってオーバーフローとします。

> list_flag_table{|a, b| a + b < -8 || 7 < a + b }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1 
  6  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1 
  5  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1 
  4  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1 
  3  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1 
  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1 
  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -2  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -3  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -4  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0 
 -5  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0 
 -6  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0 
 -7  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0 
 -8  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 

符号ビットのフルアダーのキャリー入力は、 符号なし 3 ビット加算の桁あふれと言い換えても同じです。 結果の 4 ビット目が 1 になる場合を真にします。

> list_flag_table{|a, b| (((a & 7) + (b & 7)) & 8) != 0 }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  0  1  1  1  1  1  1  1  0  1  1  1  1  1  1  1 
  6  0  0  1  1  1  1  1  1  0  0  1  1  1  1  1  1 
  5  0  0  0  1  1  1  1  1  0  0  0  1  1  1  1  1 
  4  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1 
  3  0  0  0  0  0  1  1  1  0  0  0  0  0  1  1  1 
  2  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1 
  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  0  1  1  1  1  1  1  1  0  1  1  1  1  1  1  1 
 -2  0  0  1  1  1  1  1  1  0  0  1  1  1  1  1  1 
 -3  0  0  0  1  1  1  1  1  0  0  0  1  1  1  1  1 
 -4  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1 
 -5  0  0  0  0  0  1  1  1  0  0  0  0  0  1  1  1 
 -6  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1 
 -7  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1 
 -8  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 

符号ビットのフルアダーのキャリー出力は、 符号なし 4 ビット同士の加算の桁あふれと言い換えても同じです。 加算の結果の 5 ビット目が 1 になる場合を真にします。

> list_flag_table{|a, b| (((a & 15) + (b & 15)) & 16) != 0 }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  0  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
  6  0  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
  5  0  0  0  1  1  1  1  1  0  0  0  0  0  0  0  0 
  4  0  0  0  0  1  1  1  1  0  0  0  0  0  0  0  0 
  3  0  0  0  0  0  1  1  1  0  0  0  0  0  0  0  0 
  2  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0 
  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  1  1  1  1  1  1  1  1  0  1  1  1  1  1  1  1 
 -2  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1 
 -3  1  1  1  1  1  1  1  1  0  0  0  1  1  1  1  1 
 -4  1  1  1  1  1  1  1  1  0  0  0  0  1  1  1  1 
 -5  1  1  1  1  1  1  1  1  0  0  0  0  0  1  1  1 
 -6  1  1  1  1  1  1  1  1  0  0  0  0  0  0  1  1 
 -7  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  1 
 -8  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 

ソフトウェア向けの求め方では、 符号なし 4 ビット同士の加算の桁あふれを、 加算の結果 4 ビットに対する符号なし比較を使います。 足して小さくなるときに桁あふれしていることを利用すれば良いのです。

> list_flag_table{|a, b| (((a & 15) + (b & 15)) & 15) < (a & 15) }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  0  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
  6  0  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
  5  0  0  0  1  1  1  1  1  0  0  0  0  0  0  0  0 
  4  0  0  0  0  1  1  1  1  0  0  0  0  0  0  0  0 
  3  0  0  0  0  0  1  1  1  0  0  0  0  0  0  0  0 
  2  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0 
  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  1  1  1  1  1  1  1  1  0  1  1  1  1  1  1  1 
 -2  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1 
 -3  1  1  1  1  1  1  1  1  0  0  0  1  1  1  1  1 
 -4  1  1  1  1  1  1  1  1  0  0  0  0  1  1  1  1 
 -5  1  1  1  1  1  1  1  1  0  0  0  0  0  1  1  1 
 -6  1  1  1  1  1  1  1  1  0  0  0  0  0  0  1  1 
 -7  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  1 
 -8  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 

これでオーバーフローを求めることができます。

> def plus_carry_in(a, b) (((a & 7) + (b & 7)) & 8) != 0 end
 => :plus_carry_in
> def plus_carry_out(a, b) (((a & 15) + (b & 15)) & 15) < (a & 15) end
 => :plus_carry_out
> list_flag_table{|a, b| plus_carry_in(a, b) ^ plus_carry_out(a, b) }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1 
  6  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1 
  5  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1 
  4  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1 
  3  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1 
  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1 
  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -2  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -3  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -4  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0 
 -5  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0 
 -6  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0 
 -7  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0 
 -8  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 

今度は減算です。 減算でも ALU の符号ビットへの桁あふれと符号ビットからの桁あふれの排他的論理和でオーバーフローを求めることができます。 キャリー出力を比較演算で求めるときは、 加算とは逆で、 結果が大きくなるときに桁あふれが生じていることを利用します。

> list_flag_table{|a, b| a - b < -8 || 7 < a - b }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0 
  6  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0 
  5  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0 
  4  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0 
  3  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
  2  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1 
 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1 
 -4  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1 
 -5  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1 
 -6  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1 
 -7  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1 
 -8  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1 
> def minus_carry_in(a, b) (((a & 7) - (b & 7)) & 8) != 0 end
 => :minus_carry_in
> def minus_carry_out(a, b) (((a & 15) - (b & 15)) & 15) > (a & 15) end
 => :minus_carry_out
> list_flag_table{|a, b| minus_carry_in(a, b) ^ minus_carry_out(a, b) }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0 
  6  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0 
  5  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0 
  4  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0 
  3  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
  2  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
b 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1 
 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1 
 -4  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1 
 -5  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1 
 -6  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1 
 -7  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1 
 -8  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1 

符号付き減算のオーバーフロー・ビットは、 符号付き整数の比較演算を正しくおこなうために必要になります。 単純に符号なし整数として減算して符号ビットを調べるだけでは正しい大小比較ができません。 オーバーフローしている領域で判定結果が逆転してしまいます。 これが、 D. Knuth The Art of Computer Programming Volume 1 Fascicle 1 section 1.3.1'. Exercise 22 記載のダメな実例がやらかしていることです。 正しい結果にするには、 符号ビットとオーバーフロー・フラグの排他的論理和を求めます。

> list_flag_table{|a, b| a < b }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0 
  6  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0  0 
  5  1  1  1  1  1  1  1  1  1  1  1  1  1  0  0  0 
  4  1  1  1  1  1  1  1  1  1  1  1  1  0  0  0  0 
  3  1  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0 
  2  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0 
  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
b 0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 -1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0 
 -2  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0 
 -3  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0 
 -4  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0 
 -5  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -6  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -7  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -8  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
> list_flag_table{|a, b| ((a & 15) - (b & 15)) & 8 != 0 }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  0 
  6  0  0  0  0  0  0  1  1  1  1  1  1  1  1  0  0 
  5  0  0  0  0  0  1  1  1  1  1  1  1  1  0  0  0 
  4  0  0  0  0  1  1  1  1  1  1  1  1  0  0  0  0 
  3  0  0  0  1  1  1  1  1  1  1  1  0  0  0  0  0 
  2  0  0  1  1  1  1  1  1  1  1  0  0  0  0  0  0 
  1  0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
b 0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 -1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  1 
 -2  1  1  1  1  1  1  0  0  0  0  0  0  0  0  1  1 
 -3  1  1  1  1  1  0  0  0  0  0  0  0  0  1  1  1 
 -4  1  1  1  1  0  0  0  0  0  0  0  0  1  1  1  1 
 -5  1  1  1  0  0  0  0  0  0  0  0  1  1  1  1  1 
 -6  1  1  0  0  0  0  0  0  0  0  1  1  1  1  1  1 
 -7  1  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1 
 -8  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1 
> def minus_overflow(a, b) minus_carry_in(a, b) ^ minus_carry_out(a, b) end
> def minus_negative(a, b) ((a & 15) - (b & 15)) & 8 != 0 end
 => :minus_negative
> list_flag_table{|a, b| minus_negative(a, b) ^ minus_overflow(a, b) }
                             a
    -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
  7  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0 
  6  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0  0 
  5  1  1  1  1  1  1  1  1  1  1  1  1  1  0  0  0 
  4  1  1  1  1  1  1  1  1  1  1  1  1  0  0  0  0 
  3  1  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0 
  2  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0 
  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
b 0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 -1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0 
 -2  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0 
 -3  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0 
 -4  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0 
 -5  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -6  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -7  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 -8  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 

C++11 で加減算の事前にオーバーフローするかどうかを同じやりかたでチェックすることができます。 例えば 32 ビット符号付き整数のオーバーフローチェックを書いてみます。

#include <cstdint>

// x + y が桁あふれするなら真
bool
plus_overflow(std::int32_t x, std::int32_t y)
{
    static const std::uint32_t mask = (1LU << 31) - 1LU;
    std::uint32_t const u = static_cast<std::uint32_t> (x);
    std::uint32_t const v = static_cast<std::uint32_t> (y);
    return (u + v < u) ^ ((u & mask) + (v & mask) > mask);
}

// x - y が桁あふれするなら真
bool
minus_overflow(std::int32_t x, std::int32_t y)
{
    static const std::uint32_t mask = (1LU << 31) - 1LU;
    std::uint32_t const u = static_cast<std::uint32_t> (x);
    std::uint32_t const v = static_cast<std::uint32_t> (y);
    return (u - v > u) ^ ((u & mask) - (v & mask) > mask);
}

ソフトウェアで事前にオーバーフローを計算するには、 上のやりかたと等価の別の書き方もあります。 どちらが良いかは、 アーキテクチャコンパイラ次第です。 コンパイラによっては、 符号付き整数演算のオーバーフロー検出時処理を挿入するものがあるので、 キャストで符号なし整数演算を強制させています。

bool
plus_overflow(std::int32_t x, std::int32_t y)
{
    std::int32_t const z = static_cast<std::int32_t> (
        static_cast<std::uint32_t> (x) + static_cast<std::uint32_t> (y));
    return (static_cast<std::uint32_t> (z) < static_cast<std::uint32_t> (x)) ^ (x < 0) ^ (y < 0) ^ (z < 0);
}

bool
minus_overflow(std::int32_t x, std::int32_t y)
{
    std::int32_t const z = static_cast<std::int32_t> (
        static_cast<std::uint32_t> (x) - static_cast<std::uint32_t> (y));
    return (static_cast<std::uint32_t> (z) > static_cast<std::uint32_t> (x)) ^ (x < 0) ^ (y < 0) ^ (z < 0);
}