気をつけよう！左シフトのオーバーフロー！

なんですか

ダブリング(doubling)を実装するときビット演算を書いていたら左シフト演算子でオーバーフローした。

どういうこと

競プロではビット演算をしたいことがある。 ビット演算ではある整数を2進数で表したときにi+1桁目が1かどうか（ある整数にi番目のフラグが立っているかどうか）を知りたいことがある。

C++(GCC 9.3.0 C++17) ではnにi番目のフラグが立っているかどうかを判定するときにn & (1 << i)と書くかもしれない。 1 << iは1をi回左シフトした数で、i番目のフラグのみが立っている数となる。 1 << iがint型に収まらないときにオーバーフローするから気をつけよう！

オーバーフローしない対策

左シフトの左オペランドをlong long型にする

1 << iがlong long型に収まるならば、LLサフィックスを使用して左オペランドをlong long型にする。右オペランドがlong long型でも左オペランドがint型だとオーバーフローする。

下のコードを実行するとコメントの結果が得られるということ。

#include <iostream>
using namespace std;

int main() {
    long long i = 60;

    cout << (1 << i) << "\n";
    // 268435456 オーバーフローした
    cout << (1LL << i) << "\n";
    // 1152921504606846976 オーバーフローしていない
}