【C++】intがオーバーフローするとどうなる?|符号付き整数の未定義動作で、ReleaseとDebugの答えが変わる例を実測して直す

【C++】intがオーバーフローするとどうなる?|符号付き整数の未定義動作で、ReleaseとDebugの答えが変わる例を実測して直す C++

intの最大値(2147483647)に、1を足すと、どうなるでしょうか。「最小値(-2147483648)に戻る」と、答える人は多いです。実際にも、そう動くことがあります。ただ、intのような符号付き整数では、標準が、動作を決めていません。

決まっていないとは、結果が、どうなってもよい、という意味です。コンパイラは、「オーバーフローは起きない」という前提で、式を書き換えて構いません。それが、本当に起きるのかを、MSVCのReleaseとDebugで、同じソースを動かして確かめました。ゲームで出会いやすい場面(二分探索の中点、abs、掛け算)も試しています。

検証は、Visual Studio 2022付属のMSVC(19.44、x64)で、Release(/O2 /MD)とDebug(/Od /MDd)の両方を動かして行いました。

整数のオーバーフローとは?

・符号なし整数(unsignedなど):上限を超えると、0に戻る。動作が、標準で決まっている

・符号付き整数(intなど):上限を超えたときの動作は、標準で決まっていない(未定義動作)

実験①:符号なしなら、0に戻る

まず、動作が決まっている、符号なし整数から、確かめます。unsignedの最大値に、1を足しました。

▼e3_wrap.cpp
// 符号なし(unsigned)なら、オーバーフローは「決まった動き」になる
#include <climits>
#include <cstdio>
#include <cstdlib>

__declspec(noinline) bool willWrapUnsigned(unsigned a)
{
    return a + 1 < a;                  // unsigned なら、0 に戻る(決まっている)ので、この判定は正しい
}

int main(int argc, char** argv)
{
    unsigned v = argc > 1 ? (unsigned)std::strtoul(argv[1], nullptr, 10) : UINT_MAX;
    std::printf("a = %u\n", v);
    std::printf("a + 1 < a (unsigned) : %s\n", willWrapUnsigned(v) ? "0に戻る と判定" : "戻らない と判定");
    std::printf("UINT_MAX + 1 = %u\n", (unsigned)(v + 1));
    return 0;
}
a = 4294967295
a + 1 < a (unsigned) : 0に戻る と判定
UINT_MAX + 1 = 0

UINT_MAX + 1は0になり、a + 1 < aという判定も、trueになりました。Debugでも、同じ結果です。符号なしの場合は、「戻る」のが決まりなので、どの環境でも、同じ答えになります。

【重要】実験②:符号付きでは、コンパイラが式を書き換える

符号付きのintで、オーバーフローが絡む4つの式を、a = INT_MAXで評価しました。どの式も、「オーバーフローしない」と考えると、trueかfalseのどちらかに、決まります。

▼e5_forms.cpp
// 「符号付き整数は、オーバーフローしない」という前提で、コンパイラが式を書き換えるか
#include <climits>
#include <cstdio>
#include <cstdlib>

__declspec(noinline) bool f1(int a) { return a + 1 > a; }          // 常に true になる、と見なせる
__declspec(noinline) bool f2(int a) { return a + 100 < a; }        // 常に false になる、と見なせる
__declspec(noinline) bool f3(int a) { return a * 2 / 2 == a; }     // 常に true になる、と見なせる
__declspec(noinline) bool f4(int a) { return (a + 1) - 1 == a; }   // 常に true になる、と見なせる

int main(int argc, char** argv)
{
    int a = argc > 1 ? std::atoi(argv[1]) : INT_MAX;
    std::printf("a = %d\n", a);
    std::printf("a + 1 > a        : %s\n", f1(a) ? "true" : "false");
    std::printf("a + 100 < a      : %s\n", f2(a) ? "true" : "false");
    std::printf("a * 2 / 2 == a   : %s\n", f3(a) ? "true" : "false");
    std::printf("(a + 1) - 1 == a : %s\n", f4(a) ? "true" : "false");
    return 0;
}
符号付き整数のオーバーフローを含む式を、ReleaseとDebugで実行した結果。a * 2 / 2 == a だけ答えが違った
4つの式のうち、`a * 2 / 2 == a`だけが、Releaseでtrue、Debugでfalseになった

同じソース、同じ入力(INT_MAX)で、a * 2 / 2 == aだけ、Releaseでtrue、Debugでfalseという、食い違いが出ました。Debugは、実際に計算しています。INT_MAX * 2は-2になり、それを2で割ると-1で、aとは、一致しません。

Releaseのアセンブリを見ると、理由が分かります。

; f1 : return a + 1 > a;
    lea eax, DWORD PTR [rcx+1]
    cmp eax, ecx
    setg al
    ret 0

; f3 : return a * 2 / 2 == a;
    mov al, 1
    ret 0

a + 1 > a(f1)は、足し算と比較が、そのまま残っています。ところが、a * 2 / 2 == a(f3)は、計算がすべて消え、mov al, 1(常にtrueを返す)だけになりました。コンパイラが、「符号付きのa * 2は、オーバーフローしない」と見なして、a * 2 / 2を、aに簡単にしたためです。

オーバーフローが起きる値を渡した瞬間に、この前提は、崩れます。それでも、Releaseは、「常にtrue」の関数を、実行してしまいます。デバッグビルドで確認して、問題がなかったのに、Releaseだけ、結果が変わる、という形のバグは、こうして生まれます。

4つのうち、書き換えられたのは、1つだけでした(a + 1 > aとa + 100 < aは、書き換えられませんでした)。「書き換えられる式」と「そうでない式」の境目は、コンパイラのバージョンや、最適化の強さで変わります。どれが無事かを、覚えておくことは、できません。

実験③:i

n = INT_MAXのとき、for (int i = n - 3; i <= n; ++i)は、4回で終わるはずです。止まらなかったときのために、100回で打ち切る、安全装置を付けて試しました。

▼e2_loop.cpp
// i <= n のループで、n が INT_MAX だと、i は INT_MAX を超えられず、終わらない
#include <climits>
#include <cstdio>
#include <cstdlib>

__declspec(noinline) int countTo(int n)
{
    int count = 0;
    for (int i = n - 3; i <= n; ++i)      // n-3, n-2, n-1, n の4回のはず
    {
        ++count;
        if (count >= 100) break;          // 止まらなかったときの安全装置
    }
    return count;
}

int main(int argc, char** argv)
{
    int n = argc > 1 ? std::atoi(argv[1]) : 100;
    int c = countTo(n);
    std::printf("n = %d のとき、ループが回った回数 = %d (4回のはず)%s\n", n, c, c >= 100 ? "  ← 安全装置で止めた" : "");
    return 0;
}
nReleaseDebug
10004回(正常)4回(正常)
2147483647(INT_MAX)100回(安全装置で、強制的に止めた)100回(安全装置で、強制的に止めた)
安全装置が無ければ、iがINT_MAXを超えて負に戻るため、永遠に終わらない

i <= nの条件は、nがINT_MAXだと、iがINT_MAXのあとに、負の数へ戻って、永遠に成立し続けます。nが、ふだんは小さい値のときは、気づけません。配列の要素数や、ユーザーが入力した値が、たまたま上限に近づいたとき、初めて、止まらなくなります。

実験④:ゲームやアルゴリズムで、出会う形

もう少し、現実に近い形でも、試しました。二分探索の中点、abs(INT_MIN)、intの掛け算の3つです。

▼e4_real.cpp
// ゲームや、アルゴリズムで、実際に出会う形のオーバーフロー
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <numeric>

__declspec(noinline) int midBad(int lo, int hi)  { return (lo + hi) / 2; }
__declspec(noinline) int midGood(int lo, int hi) { return lo + (hi - lo) / 2; }
__declspec(noinline) int absInt(int x)           { return std::abs(x); }
__declspec(noinline) int mul(int a, int b)       { return a * b; }

int main(int argc, char** argv)
{
    // 実行時に決まる値にして、コンパイル時の計算を避ける
    int big = argc > 1 ? std::atoi(argv[1]) : 2000000000;

    std::printf("【二分探索の中点】lo = %d, hi = %d\n", big - 10, big);
    std::printf("  (lo + hi) / 2        = %d\n", midBad(big - 10, big));
    std::printf("  lo + (hi - lo) / 2   = %d\n", midGood(big - 10, big));
    std::printf("  std::midpoint(lo,hi) = %d\n", std::midpoint(big - 10, big));

    int minv = INT_MIN;
    std::printf("\n【abs(INT_MIN)】 x = %d\n", minv);
    std::printf("  abs(x)               = %d  (負のまま)\n", absInt(minv));

    std::printf("\n【掛け算】100000 * 100000 = %d  (実際は 10000000000)\n", mul(big / 20000, big / 20000));
    std::printf("  long long で掛けると = %lld\n", (long long)(big / 20000) * (big / 20000));
    return 0;
}
【二分探索の中点】lo = 1999999990, hi = 2000000000
  (lo + hi) / 2        = -147483653
  lo + (hi - lo) / 2   = 1999999995
  std::midpoint(lo,hi) = 1999999995

【abs(INT_MIN)】 x = -2147483648
  abs(x)               = -2147483648  (負のまま)

【掛け算】100000 * 100000 = 1410065408  (実際は 10000000000)
  long long で掛けると = 10000000000
式結果本来の値
(lo + hi) / 2(lo = 1999999990, hi = 2000000000)-1474836531999999995
abs(INT_MIN)-2147483648(負のまま)2147483648
100000 * 100000141006540810000000000
intのまま計算した結果。ReleaseでもDebugでも、同じ値になった

二分探索の中点を、(lo + hi) / 2で出すと、要素が、20億個に近い範囲では、足し算がオーバーフローして、負の添字になります。直し方は、lo + (hi - lo) / 2(結果は1999999995)か、C++20のstd::midpointです。

abs(INT_MIN)は、2147483648がintに収まらず、負のまま返ってきます。ダメージの、絶対値を取る処理などで、INT_MINが入ってくる経路があると、「ダメージが負」という、不思議な結果になります。掛け算も同じで、100000 * 100000は、1410065408という、まったく別の値になりました。

実験⑤:「足したあとで、調べる」書き方

「オーバーフローしたか」を、足したあとの結果と比べて調べる書き方も、よく見かけます。a + 1 < aです。a = INT_MAXで、足す前に調べる書き方と、比べました。

▼e1_check.cpp
// 「オーバーフローしたか」を、足したあとで調べる書き方は、最適化で消えることがある
#include <climits>
#include <cstdio>
#include <cstdlib>

__declspec(noinline) bool willOverflowBad(int a)
{
    return a + 1 < a;                  // a が INT_MAX なら、オーバーフローして負になるはず…という判定
}

__declspec(noinline) bool willOverflowGood(int a)
{
    return a == INT_MAX;               // 足す前に、上限と比べる
}

int main(int argc, char** argv)
{
    int v = argc > 1 ? std::atoi(argv[1]) : INT_MAX;       // 実行時に決まる値にして、コンパイル時の計算を避ける
    std::printf("a = %d\n", v);
    std::printf("a + 1 < a      (足したあとで調べる) : %s\n", willOverflowBad(v) ? "オーバーフローする" : "しない と判定");
    std::printf("a == INT_MAX   (足す前に調べる)     : %s\n", willOverflowGood(v) ? "オーバーフローする" : "しない と判定");
    return 0;
}
a = 2147483647
a + 1 < a      (足したあとで調べる) : オーバーフローする
a == INT_MAX   (足す前に調べる)     : オーバーフローする

どちらも、「オーバーフローする」と、正しく判定できました。このMSVCでは、a + 1 < aも動きました。ただし、実験②のとおり、コンパイラは、符号付きの足し算が、オーバーフローしない前提で、式を書き換えてよい、と標準が認めています。動いたからといって、次のバージョンでも動くとは、限りません。調べるなら、足す前に、a == INT_MAXやa > INT_MAX - bと比べるのが、確実です。

直し方

  • 大きい型で計算する:long long(int64_t)で、計算してから、範囲を確かめて、intに戻す。経験値やダメージの足し込みは、最初からint64_tにする
  • 足す前に調べる:a > INT_MAX - bのように、足し算が、上限に届くかを、足す前に比べる
  • 中点は、lo + (hi - lo) / 2かstd::midpoint
  • i <= nのループは、nが上限になり得るか確かめる。i < n + 1に直す手もあるが、n + 1が、オーバーフローしない型で書く
  • オーバーフローを、「巻き戻り」として使いたいなら、unsignedを使う(動作が、決まっているため)

よくある失敗例と対処法

①Debugでは動いたので、Releaseも大丈夫だと思う

実験②のとおり、a * 2 / 2 == aは、Releaseだけtrueでした。符号付き整数の計算で、値が上限に近づく可能性があるなら、Releaseで、同じ入力を試します。

②足し込みを、intのままで続ける

経験値、スコア、所持金、累計ダメージのような、増え続ける値は、intの上限に届きます。int64_tにするか、上限で止める処理(クランプ)を入れます。

③二分探索の中点を、(lo + hi) / 2と書く

要素数が、少ないうちは動きます。要素が増えて、上限に近づいたときに、突然、壊れます。

④abs()に、INT_MINが来る可能性を考えない

符号付き整数の最小値の絶対値は、同じ型では、表せません。INT_MINが来るかもしれない経路では、long longに変換してから、absを取ります。

注意点

  • 符号なし整数のオーバーフローは0に戻る(動作が決まっている)。符号付きは未定義動作
  • a * 2 / 2 == aは、Releaseでmov al, 1(常にtrue)に置き換えられ、Debugでは、falseになった
  • i <= nのループは、nがINT_MAXのとき、終わらなかった(ReleaseでもDebugでも)
  • (lo + hi) / 2は-147483653、abs(INT_MIN)は負のまま、100000 * 100000は1410065408になった
  • a + 1 < aは、このMSVCでは、動いた。ただし、標準は保証していない
  • 今回の検証は、MSVC 19.44(Visual Studio 2022付属、x64)で行った。どの式が書き換えられるかは、コンパイラや最適化設定で変わる

この記事のポイント

  • 符号付き整数のオーバーフローは、「戻る」のではなく、「結果が決まっていない」
  • コンパイラは、「起きない」前提で式を書き換える。ReleaseとDebugで、答えが変わることがある
  • 増え続ける値はint64_t。中点はlo + (hi - lo) / 2。調べるなら、足す前に
  • 巻き戻りに頼るなら、unsignedを使う

2147483647 + 1が、何になるかを、暗記する必要はありません。覚えておきたいのは、答えが決まっていない計算を、コードの中に残さない、ということだけです。

あわせて読みたい