プログラマーが式を使うのを見たことがある
mid = start + (end - start) / 2
より単純な式を使用する代わりに
mid = (start + end) / 2
配列またはリスト内の中央の要素を検索します。
なぜ前者を使用するのでしょうか?
ベストアンサー1
理由は3つあります。
まず、1 がオーバーフローしないstart + (end - start) / 2
限り、ポインターを使用している場合でも動作します。end - start
int *start = ..., *end = ...;
int *mid = start + (end - start) / 2; // works as expected
int *mid = (start + end) / 2; // type error, won't compile
第二に、とが大きな正の数であるstart + (end - start) / 2
場合はオーバーフローしません。符号付きオペランドの場合、オーバーフローは未定義です。start
end
int start = 0x7ffffffe, end = 0x7fffffff;
int mid = start + (end - start) / 2; // works as expected
int mid = (start + end) / 2; // overflow... undefined
( はend - start
オーバーフローする可能性がありますが、それは またはstart < 0
の場合のみですend < 0
。)
または、符号なし演算では、オーバーフローは定義されていますが、間違った答えが返されます。ただし、符号なしオペランドの場合、start + (end - start) / 2
がオーバーフローすることはないのは、 の場合だけですend >= start
。
unsigned start = 0xfffffffeu, end = 0xffffffffu;
unsigned mid = start + (end - start) / 2; // works as expected
unsigned mid = (start + end) / 2; // mid = 0x7ffffffe
最後に、要素に向かって丸めることがよくありますstart
。
int start = -3, end = 0;
int mid = start + (end - start) / 2; // -2, closer to start
int mid = (start + end) / 2; // -1, surprise!
脚注
1 C 標準によれば、ポインタ減算の結果が として表現できない場合ptrdiff_t
、動作は未定義です。ただし、実際には、char
アドレス空間全体の少なくとも半分を使用して配列を割り当てる必要があります。