えびちゃんの日記

えびちゃん(競プロ)の日記です。

自分で未定義動作を書いて逆ギレする人かわいそう

お店に入るときにドアが開いているか確認せずに歩いていって、ドアにぶつかって怒っている人がいたらおかしい話じゃないですか*1

未定義動作を起こして怒るのはこれと似ている気がします。 競プロでよくあるコーナーケースなども同じです。

「いま書いている処理は、ありえる入力のどれに対しても適切に動くか?」というのをちゃんと意識するといい気がします。

昔の記事 では、未定義動作を書いたらどうなりうるかがメインだった気がします。 今回は、競プロの人々がよくやっている or やりそうな未定義動作の紹介集みたいなのに近いつもりです。

「複雑な書き方をするとこわれます」というのはまた今度書くとして、「簡単にこわれます」というのがメインです。

以下では、int は 32 bit の 2 の補数表現ということで書きます。AtCoder など多くの環境と同じです。

演算子

多くの演算子、入力によってはすぐ未定義動作を起こしてしまう...(かなしい)

+

#include <climits>
int main() {
  int bad = INT_MAX + 1;
}

オーバーフローはだめ、それはそう。

-

#include <climits>
int main() {
  int bad = INT_MIN - 1;
}

負のオーバーフローも気をつけましょう。

*

#include <climits>
int main() {
  int bad = INT_MAX * 2;
  int bad2 = INT_MIN * (-1);
}

オーバーフロー定期。

/

#include <climits>
int main() {
  int bad = 1 / 0;
  int bad2 = INT_MIN / (-1);
}

ゼロ除算は当然気をつけましょう。 オーバーフローにも気をつけましょう。

%

#include <climits>
int main() {
  int bad = 1 % 0;
  int bad2 = INT_MIN % (-1);
}

INT_MIN % (-1)0 でしょうと思うんですが、x / y がオーバーフローするときは x % y も未定義です。

<<

int main() {
  int bad = 1 << 100;
  int bad2 = 1 << (-5);
}

x << y は、y が負の場合や、x の(汎整数拡張後の)ビット幅以上の場合は未定義です。

[]

int main() {
  int a[5] = {31, 41, 59, 26, 53};
  int bad = a[5];
}

配列外参照もだめ。

標準関数

<cmath> の関数とかは予想に反しがちなときがあるかも? 適宜調べておきましょう。

en.cppreference.com

<algorithm> の関数、特に sort など順序が絡むものは誤る人が多いので気をつけましょう。 「順序としてこわれているものを第三引数に渡しちゃお〜」とすると、無限ループになったり Segfault になったりします*2

GCC 拡張の関数

gcc.gnu.org

__builtin_clz __builtin_ctz

x のうち先頭・末尾の 0 のビットの個数を数えるものです。 x == 0 のとき(すなわち 1 が現れないとき)の動作は未定義です。

ビット幅を返してくれるとは言っていません。

飽きたよね

えびちゃんも飽きました。

何をやるにしても未定義動作が絡んできて、覚えておくのが大変すぎてつらいというのは、えびちゃんもわかります。 「こんな処理が未定義じゃなかったら、やばいだろ」というような感覚を養うといいかもしれません。

「未定義動作なんて非本質すぎて考えたくない」と思ってしまうタイプの人には、C++ 以外の言語が向いているかもしれません?

ねこ

典型コーナーケースに対する「自分で場合分けを放棄して WA に逆ギレする人かわいそう」という記事や、「自分で定数倍の遅いコードを書いて TLE に逆ギレする人かわいそう」のような記事も書こうとしていました。「誤読して逆ギレする人かわいそう」という気持ちはありますが、記事に書くことはあまりないような気もします?

人々が何らかの対象に逆ギレしているのを見て、お気持ち表明したくなったらまた書きます。

*1:え、もしかして実在しますか?

*2:未定義なので、もちろん、こうなることは保証されていませんが。