3

有人能帮我解释一下这个功能吗，谢谢！

int overflow(int x, int y)
{
   int result, non_overflow, overflow, result_sign, mask;

   result = x + y;
   result_sign = result >> 31;  //Need help starting from here... I know
                                //it is shifting 31 bits... but why??
   non_overflow = ((x ^ y) | ~(y ^ result)) >> 31;
   overflow = ~non_overflow;

   mask = overflow << 31;

   return (non_overflow & result) | (overflow & (result_sign ^ mask));  
}
4

1 回答 1

5

它正在为加法运算计算一个整数溢出“标志”，它表示结果的大小是小于INT_MIN还是大于INT_MAX。它假设int是 32 位，二进制补码，并且有符号数的右移是复制高位的“算术”移位 - 没有安全的假设。

如果x和的符号y相同，但结果的符号相反，则结果溢出。这就是它的全部计算。没必要这么复杂。

假设加法不会产生整数异常并且没有奇怪的奇偶校验位，这个表达式将通过以与原始代码相同的精神来操作符号位来工作：

( x ^ y ) < 0 && ( x ^ result ) < 0 /* (A^B)<0 iff A and B have opposite sign */

如果我们想对依赖定义明确的行为挑剔，如果结果可能溢出，则执行x + y是非法的。允许符合 C 标准的机器在这种溢出（或自毁等）时终止程序，因此我们首先需要避免这样做。

我们要执行的测试是

x + y > INT_MAX
x + y < INT_MIN

x和y直接之间没有安全操作。我们必须将一个移到等式的另一边，这意味着反转它的符号并做减法。只有从 中减去正数INT_MAX或从 中减去负数才是安全的INT_MIN，所以我们可以修改这些：

y > INT_MAX - x
y < INT_MIN - x

最安全的方法是

x < 0? ( y < INT_MIN - x ) : ( y > INT_MAX - x );

编辑：糟糕，我没有猜到该函数对溢出标志做了什么。如果没有溢出，它显然返回结果，INT_MAX如果有正溢出则返回，INT_MIN如果有负溢出则返回。换句话说，它是饱和加法。它这样做的方式有点复杂，看起来作者煞费苦心地消除了分支。但是溢出通常不会发生，并且可预测的分支比许多算术便宜，因此可能值得尝试使用更直接的实现if … else。

于 2013-02-06T23:06:11.187 回答