为何存在整数溢出的三整数排序代码仍能输出正确结果？

先看这段用于输出三个整数升序的C++代码：

#include <iostream>

using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int mn = a, mx = a;
  if (b > mx)
    mx = b;
  if (c > mx)
    mx = c;
  if (b < mn)
    mn = b;
  if (c < mn)
    mn = c;
    
  int mid = (a + b + c) - (mn + mx);
  
  cout << mn << " " << mid << " " << mx << "\n";
}

问题现象 #

已知输入整数范围是-10^9 ≤ a, b, c ≤ 10^9，当a + b + c的和超过INT_MAX时，单独打印这个和会得到负数（明显溢出），但mid变量却能输出正确的中间值。这是不是编译器优化导致的？

答案 #

这不是编译器优化的结果，而是基于补码硬件的溢出特性，加上代码里的数学关系刚好抵消了溢出的影响：

1. 数学恒等式基础
   从逻辑上看，mn是三个数的最小值，mx是最大值，mid是中间值，所以数学上必然满足：

   a + b + c = mn + mid + mx
   

   因此mid = (a + b + c) - (mn + mx)是恒成立的数学推导。

2. 补码溢出的特性
   在大多数现代硬件中，有符号整数采用补码存储，当计算溢出时，实际结果是按2^N取模（N是int的位数，比如32位int就是2^32）。也就是说，溢出后的数值等于(真实值) mod 2^N。

3. 溢出影响的抵消

   • 首先，mn + mx的范围是-2*10^9到2*10^9，而32位int的INT_MAX是2^31-1≈2.1*10^9，所以mn + mx不会溢出，计算结果就是它的真实值。
   • 当a + b + c溢出时，硬件计算出的结果是(mn + mid + mx) mod 2^32。用这个值减去mn + mx（真实值），得到的结果刚好等于mid本身——溢出带来的模运算偏移被减法完全抵消了，因为mid的范围远小于2^31，不会被模运算影响。

4. 注意事项
   虽然这段代码在当前硬件上能正常运行，但有符号整数溢出在C++标准中属于未定义行为，标准并没有规定编译器必须按照补码模运算来处理溢出。如果更换编译器、目标硬件或者开启特定优化选项，这段代码可能会出现不可预料的错误，属于不安全的写法。

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