怎么作除法

考虑下面的程序。printf 输出了什么结果？

  1 #include <stdio.h>
  2 
  3 int main() {
  4   unsigned low = 1;
  5   unsigned high = 4294967295U;
  6   unsigned mid = (low + high) / 2;
  7   printf("%u\n", mid);
  8   return 0;
  9 }

答案是0。

因为4294967295 = 2³² - 1，所以第6行出现了overflow。如果把第6行换成：

  6   unsigned mid = low + (high - low)  / 2;

mid就会等于正确的：2147483648。

用>> 1代替/ 2，这个错误还是一样会出现。顺便提一句，据说很多binary search的程序都因为这个小错误而存在bug。另外编程时如果遇到很长的四则混合运算也要小心设计运算的先后顺序，避免可能出现的overflow的情况。

- Written on Sat Dec 29 07:20:30 2007.