[小ネタ] [0,n)のレンジチェックを1回で済ませる

TL;DR

これを見たとき、目から鱗が落ちた。

一般的な話

今まで、0～nまでのレンジチェックをするときは以下のように書いていた

if (index < 0 || index >= _size) throw new ArgumentException();

よくあるパターンなんだけど、値域の判定が2度入る。

ListのIndexerがしてたこと

if ((uint)index >= (uint)_size) throw new ArgumentException();

こんな風にuintにキャストしてチェックすることで判定を一度にすることが出来ている ¹ 。
で、ListのIndexerみたいに、ほぼほぼ正しい値域を伴って高頻度に呼ばれる様な場合、チェックを1回すっ飛ばせるコトは凄くでかいんじゃないかなと思ったし、こんなコト考えつかなかったのですげーなと思った。

なんでこんなコトが出来るのか

C#では、intは32bit符号ありuintは32bit符号無しの整数であり²、符号表現は2の補数となっている³。
で、intとuintの差は整数のビットをどのように解釈するのかという差のみなので、キャストにかかるコストは実質0となる³。

ここで、符号表現が2の補数であるから、負数をuintとして解釈したとき、とり得る全ての負数はint.MaxValueをuintで表現したときよりも大きくなる。
このことから、1度のレンジチェックで[0,n)のレンジチェックを完了できることになる。

興味深かったので小ネタとしてまとめてみた次第。

1. だからこそ、// Following trick can reduce the range check by one　こーかいてあったのかと。 ↩

2. このへんに書いてある。 ↩

3. このへんのI.12.1辺りに書いてる。ちなみに"コストが実質0"と言う点はおいらの推論 ↩ ↩²