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
}

さいごに

1333のような小さな値であれば、単にint型へ保存すれば十分だと思っていました。

しかし演算に用いるケースでは、演算結果がとり得る値の範囲や、演算結果の型も考慮したプログラミングが必要であると言えそうです。

C++は競プロのために入門コンテンツを使って速習したくらいの実力なのですが、奥が深くまだまだ学べることがたくさんありそう。