hotaruの蛍雪日記

競プロとゲームをしています

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

なんですか

ダブリング(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 オーバーフローしていない
}

右シフトを使う

左シフト演算子でオーバーフローが発生しているので、代わりに右シフトを使う。 nにi番目のフラグが立っているかどうかの判定をn & (1 << i)ではなく(n >> i) & 1と書く。

参考

qiita.com qiita.com