whileでハマってTLE

前回このような記事を書いたのでついでにTLEとなったしまった例をもう一つ備忘録としてメモ。
https://jsapachehtml.hatenablog.com/entry/2022/06/05/163223

以下のコードはMを超える最小の2の指数を求める処理。無限ループに陥る場合があるがどのようなケースか思いつくだろうか？

using ll = long long;

ll M = <問題の入力値>

int m = 0;
while ((1<<m) <= M) ++m;

cout << m << endl;

答えは、(1<<m)がintの最大値を超えた場合。つまりMの値がintの最大値を超えているとき。(1<<m)だとintとして扱われてしまうためオーバーフローして小さい値となってしまう。そのためいつまでも条件式が満たされることはない。

long longとして扱うには以下のように書く必要がある（見やすいよう大文字にしてる）

while ((1LL<<m) <= M) ++m;

これだけしかコードがないので上記の場合はちょっと考えると気づくかもしれないが、他にもいろいろ書いてあると意外と気づけないので注意。