比方说，我要求你通过反复猜测一个数字来找到我正在考虑的介于 -1000 和 1000 之间的数字。每次猜测，我都会告诉你你的猜测是正确的，比我的数字小还是大。二进制搜索算法尝试通过使用越来越小的间隔重复查找中点来找到间隔中的值。您可以从 0 开始，然后使用 -500 或 500 等等。
因此，我们有时需要一种快速算法来找到整数区间中的中点。以下用于查找中点的简单例程是不正确的：
int f ( int x , int y ) { 返回( x + y ) / 2 ; }
如果整数使用 64 位二进制补码表示，我们可以为 x 选择 1，为 y 选择 9223372036854775807，然后函数的结果可能是一个很大的负值。
为了构建更好的解决方案，我们可以使用以下恒等式： x == 2*(x>>1) + (x&1) 。因此我们有(x>>1) + (y>>1)接近中点：在 ( (x+y)/2-2, (x+y)/2 ) 内。如果我们添加((x&1 ) + (y&1))/2 = x&y&1 ，那么我们与中点的距离小于 1。因此，我们有以下快速函数来计算中点而不会溢出：
int f ( int x , int y ) { 返回( x > > 1 ) + ( y > > 1 ) + ( x&y& 1 ) ; }
它编译为 5 或 6 条指令（x64 或 ARM）。
Warren 在 Hacker’s Delight（第 2.5 节）中提供了一个更有效的解决方案：
int f ( int x , int y ) { 返回( x|y ) - ( ( x^y ) > > 1 ) ; }
Harold Aptroot 向我建议了另一种表述：
int f ( int x , int y ) { 返回( ( x ^ y ) >> 1 ) + ( x & y ) ; }
原文： https://lemire.me/blog/2022/12/06/fast-midpoint-between-two-integers-without-overflow/