这两个公式之间有什么区别
mid = low + (high - low) / 2;
mid = (high + low) / 2;
在第二个版本中，如果high + low大于int的最大值(假设high是int(，则它可能溢出，从而调用未定义的行为。第一个版本解决了这个特殊的错误。
第1个版本仍然存在问题，例如，如果low是一个非常大的负数，则差值仍然可能溢出。
从c++20开始，您应该使用std::midpoint来实现这一点，它处理了一大堆角落案例，并为所有这些案例做了正确的事情。
这个看似简单的函数实际上很难实现，事实上，Marshall Clow在2019年cppcon上做了一个小时的演讲，只介绍了这个函数的实现。
第一个是优越的(尽管仍然不完美，请参阅二进制搜索：如何确定数组的一半(：
-
它适用于没有为
high和low定义加法，而是为向low添加区间而定义的情况。指针就是这样一个例子，日期类型的对象可以是另一个。 -
high + low可能使类型溢出。对于有符号的积分类型，其行为是未定义的。
两者都存在潜在的溢出。有符号整数溢出是未定义的行为(UB(。
使用无符号数学(通常用于数组索引(，当low <= high时，low + (high - low) / 2;不会溢出，这与潜在的(high + low) / 2不同。
与low <= high和0 <= low时的符号数学相同。
为了避免使用带符号数学的任何溢出(或使用low > high的无符号数学(，并且仍然只使用int/unsigned数学，我认为下面的方法会起作用。
mid = high/2 + low/2 + (high%2 + low%2)/2;
然而，当high/2 + low/2的符号与(high%2 + low%2)的符号不同时，这可能会失败。
下面是一个更健壮且经过测试的版本。也许我稍后会简化。
#include <limits.h>
#include <stdio.h>
int midpoint(int a, int b) {
int avg = a/2 + b/2;
int small_sum = a%2 + b%2;
avg += small_sum/2;
small_sum %= 2;
if (avg < 0) {
if (small_sum > 0) avg++;
} else if (avg > 0) {
if (small_sum < 0) avg--;
}
return avg;
}
int midpoint_test(int a, int b) {
intmax_t lavg = ((intmax_t)a + (intmax_t)b)/2;
int avg = midpoint(a,b);
printf("a:%12d b:%12d avg_wide_math:%12jd avg_midpoint:%12dn", a,b,lavg,avg);
return lavg == avg;
}
int main(void) {
int a[] = {INT_MIN, INT_MIN+1, -100, -99, -2, -1, 0, 1, 2, 99, 100, INT_MAX-1, INT_MAX};
int n = sizeof a/ sizeof a[0];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (midpoint_test(a[i], a[j]) == 0) {
puts("Oops");
return 1;
}
}
}
puts("Success");
return 0;
}
这两个公式不同：
根据low和high的值，- 两者都可能溢出
- 即使没有溢出，它们也不一定会产生相同的结果：第一个计算中点，第二个计算2个数字的平均值
在接下来的讨论中，我们将假设low、mid和high具有相同的类型。我们正在寻找一种安全的方法来找到low和high之间的中点或平均值，它总是在类型的范围内。
如果类型是有符号的，则第一个公式mid = low + (high - low) / 2;向low取整，如果类型是带符号的，并且high和low太远，则可能溢出。
第二个公式mid = (high + low) / 2;向0取整，但对于有符号和无符号类型的high和/或low的大值可能溢出。
在您的特定应用程序中，计算排序数组的中间元素的索引以执行二进制搜索，索引值low和high是非负的，并且是low <= high。有了这个约束，两个公式计算的结果相同，但第二个公式可以溢出，而第一个公式不能。
因此，对于您的情况，您应该使用mid = low + (high - low) / 2;作为mid = (high + low) / 2;的安全替代品。
在一般情况下，计算没有溢出的平均值(第二个公式(是一个棘手的问题。下面是一组平均公式的解决方案，以及一个受chux答案启发的测试程序。它们可以适用于任何有符号整数类型：
#include <limits.h>
#include <stdio.h>
#include <stdint.h>
int average_chqrlie(int a, int b) {
if (a <= b) {
if (a >= 0)
return a + ((b - a) >> 1);
if (b < 0)
return b - ((b - a) >> 1);
} else {
if (b >= 0)
return b + ((a - b) >> 1);
if (a < 0)
return a - ((a - b) >> 1);
}
return (a + b) / 2;
}
int average_chqrlie2(int a, int b) {
if (a > b) {
int tmp = a;
a = b;
b = tmp;
}
if (a >= 0)
return a + ((b - a) >> 1);
if (b < 0)
return b - ((b - a) >> 1);
return (a + b) / 2;
}
int average_chqrlie3(int a, int b) {
int half, mid;
if (a < b) {
half = (int)(((unsigned)b - (unsigned)a) / 2);
mid = a + half;
if (mid < 0)
mid = b - half;
} else {
half = (int)(((unsigned)a - (unsigned)b) / 2);
mid = b + half;
if (mid < 0)
mid = a - half;
}
return mid;
}
int average_chux(int a, int b) {
int avg = a / 2 + b / 2;
int small_sum = a % 2 + b % 2;
avg += small_sum / 2;
small_sum %= 2;
if (avg < 0) {
if (small_sum > 0)
avg++;
} else if (avg > 0) {
if (small_sum < 0)
avg--;
}
return avg;
}
int run_tests(const char *name, int (*fun)(int a, int b)) {
int array[] = { INT_MIN, INT_MIN+1, -100, -99, -2, -1, 0, 1, 2, 99, 100, INT_MAX-1, INT_MAX };
int n = sizeof(array) / sizeof(array[0]);
int status = 0;
printf("Testing %s:", name);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int a = array[i], b = array[j];
intmax_t lavg = ((intmax_t)a + (intmax_t)b) / 2; // assuming sizeof(intmax_t) > size(int)
int avg = fun(a, b);
if (lavg != avg) {
printf("na:%12d b:%12d average_wide:%12jd average:%12d", a, b, lavg, avg);
status = 1;
}
}
}
puts(status ? "nFailed" : " Success");
return status;
}
int main() {
run_tests("average_chqrlie", average_chqrlie);
run_tests("average_chqrlie2", average_chqrlie2);
run_tests("average_chqrlie3", average_chqrlie3);
run_tests("average_chux", average_chux);
return 0;
}
与第二个不同，第一个不会导致低/高的大值溢出。通常最好使用mid = low + (high - low) / 2。