需要帮助理解整数运算功能

Question

请有人亲切地为我解释这个功能谢谢!

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));  
}

Answer 1

它正在计算加法运算的积分溢出"标志",它表示结果的大小是否小于INT_MIN或大于INT_MAX.它假设int是32位,2的补码,并且有符号数的右移是"算术"移位,它复制高阶位 - 没有安全假设.

如果的符号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 );

编辑:Woops,我没想到函数对溢出标志做了什么.如果没有溢出,它显然会返回结果,INT_MAX如果存在正溢出则返回,INT_MIN如果存在负溢出则返回.换句话说,它是饱和的补充.这样做的方式有点复杂,看起来作者努力消除分支.但溢出通常不会发生,并且可预测的分支比许多算法更便宜,因此可能值得尝试使用更简单的实现if … else.