如何优雅计算两个int32整数的中间值且避免溢出？

在做线段树、二分查找这类场景时，计算两个整数的中间值mid是高频操作，但常规写法总有溢出问题：

• 用mid = (a + b) / 2，当a和b同号时，a + b很容易超出int32的范围，比如1234567 + 2147483647或者-1234567 + (-2147483647)，直接触发溢出。
• 换成mid = (b - a) / 2 + a，虽然解决了同号溢出，但异号时又会出问题：比如int32下-2147483648和2147483647相减，结果会超出范围，照样溢出。

如果写一堆正负判断的分支代码又太繁琐，有没有更简洁的解决办法？

最优方案推荐 #

这里有几种无需分支、高效又优雅的写法，能彻底解决所有溢出场景：

1. 位运算组合（通用型，适用于多数语言）

int mid = (a & b) + ((a ^ b) >> 1);

原理：

• a & b：提取两个数二进制中同为1的位，这部分是加法时会产生进位的部分，每一位的进位相当于贡献了2的倍数，直接保留即可。
• a ^ b：得到两个数无进位的加法结果，右移1位就相当于除以2（因为没有进位，右移不会触发溢出）。
• 两者相加等价于(a + b) / 2，全程无溢出风险。

2. 无符号转换法（适用于支持无符号整数的语言，如C/C++）

int mid = (int)((unsigned int)a + (unsigned int)b) >> 1;

原理：

• 有符号整数溢出是未定义行为，但无符号整数溢出是按模2^n处理的，完全合法。把a和b转成无符号后相加，即使溢出也能得到正确的模值，右移1位后转回有符号整数，就是我们要的中间值。

3. 利用语言特性（比如Java）

Java里可以直接用无符号右移操作，一步到位：

int mid = (a + b) >>> 1;

原理：

• a + b哪怕溢出变成负数，无符号右移>>>会把最高位的符号位当作普通数值位处理，右移后得到的结果就是正确的中间值，完美规避所有溢出情况。

这些写法都不用写复杂的分支判断，代码简洁还高效，完全能替代分情况处理的繁琐代码。

内容的提问来源于stack exchange，提问作者Cary Zheng