C++でint型同士の演算結果をlong longで受け取っても、オーバーフローで正しい値にならない場合がある - ABC 162 D - RGB Triplets

緊急事態宣言に伴う自粛期間中なので、昨日は家にこもってAtCoder(競技プログラミング)の過去問を練習していました。

昨日は「ABC 162 D - RGB Triplets」を解いていたのですが、なぜかtestcase_17とtestcase_18だけACにならず、長時間悩みました。

結論から言ってしまうとint型同士の演算によるオーバーフローが原因だったのですが、実際のプログラム例を掲載します。

オーバーフローで結果が異なる例

次のC++プログラムにある「R1,R2」「G1,G2」「B1,B2」の各変数は、それぞれ1333を代入しています。 1333は小さな数で、int型の範囲内です。

ただし計算結果は大きな値となるため、long longで受け取ることにしました。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int R1 = 1333;
    int G1 = 1333;
    int B1 = 1333;
    long long res1 = R1 * G1 * B1;
    cout << res1 << endl; // -1926374259

    long long R2 = 1333;
    long long G2 = 1333;
    long long B2 = 1333;
    long long res2 = R2 * G2 * B2;
    cout << res2 << endl; // 2368593037
}

見てわかるように、計算結果をlong longで受け取ったとしても、1333をint型にしたパターンでは結果が正しくなりません。

ハードコードで書き直してみる

変数に代入するパターンではオーバーフローが起きていたため、次にハードコードで書き直してみました。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ハードコードのint
    long long res1 = 1333 * 1333 * 1333;
    cout << res1 << endl; // -1926374259

    // ハードコードのlong long
    long long res2 = 1333LL * 1333LL * 1333LL;
    cout << res2 << endl; // 2368593037
}

計算結果は相変わらずですが、私の環境(GCC 9.2.0)では次の警告が発生しました。これにより、オーバーフローが発生していることがわかります。

$ g++-9 test.cpp
test.cpp: In function 'int main()':
test.cpp:9:34: warning: integer overflow in expression of type 'int' results in '-1926374259' [-Woverflow]
    9 |     long long res1 = 1333 * 1333 * 1333;
      |                      ~~~~~~~~~~~~^~~~~~

同じ型同士の演算と、異なる型による演算の違い

発生した警告の内容を見るに、int型同士の演算結果はintになるため、オーバーフローが発生したと推測できます。 左辺で計算結果をlong longで受け取ったとしても、右辺の演算の時点でダメだったようです。

そこで右辺にlong longを組み合わせてみたところ、想定した値が返却されるようになりました。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ハードコードのint
    long long res1 = 1333 * 1333 * 1333;
    cout << res1 << endl; // -1926374259

    // ハードコードのlong long
    long long res2 = 1333LL * 1333LL * 1333LL;
    cout << res2 << endl; // 2368593037

    // intとlong longを組み合わせた例
    long long res3 = 1333 * 1333 * 1333LL;
    cout << res3 << endl; // 2368593037
}