c - 为什么在计算数组的中间时更喜欢 start + (end - start)/2 而不是 (start + end)/2？

Question

我见过程序员使用公式

mid = start + (end - start) / 2

而不是使用更简单的公式

mid = (start + end) / 2

用于查找数组或列表中的中间元素。

为什么他们使用前者？

Answer 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!

脚注

¹ 根据 C 标准，如果指针减法的结果不能表示为 ptrdiff_t ，则行为未定义。然而，在实践中，这需要分配一个 char至少使用整个地址空间一半的数组。