x が符号なし型の変数だとします。C/C++ では size_t 型などが該当します。

6 * x のような式があり、この計算がオーバーフローするかどうかを知りたいとします。つまり、6 * x がその型で表現可能な値の範囲を超えるかどうかを確認したいのです。ほとんどの場合、size_t 型の変数は [0, 2^64-1] の範囲のすべての値を表現できます。代わりにビット数を変数で表すと [0, 2^L-1] となります。

最も簡単な方法は、x を (2^L-1) // 6 と比較することです。ここで // は整数除算を表す記号（/ とは異なる）として用います。

他に方法はあるでしょうか？

値がオーバーフローしない場合、(6 * x)//6 == x であることは確実です。オーバーフローした場合に何が起こるかが興味深い問題です。任意の非ゼロ定数 a（範囲 [1, 2^L-1]）について直接答えることができます。

k = (a*x)//2^L を、乗算が何回ラップアラウンドしたかを示す数とします。マシンが実際に計算した（ラップされた）値は r = a*x - k*2^L で、0 <= r < 2^L となります。オーバーフローはちょうど k >= 1 のときに発生します。x<2^L であるため、k <= a − 1 となります。

r = a*x - k*2^L を a で整数除算すると、x に -k*2^L//a を加えた値が得られます。k が非ゼロの場合、この最後の値（-k*2^L//a）は -2^L//a、-2* 2^L//a、…、-(a-1) * 2^L//a のいずれかになります。

  • k = 0（オーバーフローなし）の場合: r // a = x。
  • k ≥ 1 の場合: r // a = x + (負の整数) ≠ x。

よって次の結果が得られます。

定理 x が符号なし型で a が非ゼロ定数のとき、a * x がオーバーフローするのは、(a * x)//a != x の場合に限ります。

実際には、x を (2^L-1) // a と比較する方が効率的である可能性が高いです。最適化コンパイラは (a * x)//a != x を単純な比較に変換できるかもしれませんが、Go コンパイラ（例）にはできません。

より数学的に洗練されたチェック方法が存在するかどうかは未解決の問題です。

Published by

Post navigation