C 在减法期间检查溢出

Question

我一直想判断两个32位的数相减是否溢出。我得到的规则是：

Can only use: ! ~ & ^ | + << >>
 *   Max uses: 20
Example: subCheck(0x80000000,0x80000000) = 1,
 *       subCheck(0x80000000,0x70000000) = 0
No conditionals, loops, additional functions, or casting

到目前为止我有

int dif = x - y; // dif is x - y
int sX = x >> 31; // get the sign of x
int sY = y >> 31; // get the sign of y
int sDif = dif >> 31; // get the sign of the difference
return (((!!sX) & (!!sY)) | (!sY)); // if the sign of x and the sign of y 
                                    // are the same, no overflow. If y is 
                                    // 0, no overflow.

我现在意识到我不能在实际函数中使用减法(-)，所以我的整个函数无论如何都是无用的。如何使用不同于减法的方法并仅使用位运算来判断是否有溢出？

Answer 1

为避免未定义的行为，我将假设整数以二进制补码表示，这是根据您对 sX、sY 和 sDif 的计算得出的。我还假设 sizeof(int) 是 4。如果您只使用 32 位整数，使用 int32_t 可能会更好，因为 int 的大小可能因平台而异。

既然你被允许使用加法，你可以把减法想象成一个数的负数的加法。可以通过翻转所有位并加一来取反存储在补码中的数字。这给出了以下修改后的代码：

int ny = 1 + ~y; // -y
int dif = x + ny; // dif is x - y
int sX = x >> 31; // get the sign of x
int sNY = ny >> 31; // get the sign of -y
int sDif = dif >> 31; // get the sign of the difference
return ((sX ^ sNY) | (~sDif ^ sX)); // if the sign of x and the sign of y 
                                    // are the same, no overflow. If the
                                    // sign of dif is the same as the signs
                                    // of x and -y, no overflow.

Answer 2

谢谢大家的帮助！这是我想出的办法来解决我的问题：

int ny = 1 + ~y; // -y
int dif = x + ny; // dif is x - y
int sX = x >> 31; // get the sign of x
int sY = y >> 31; // get the sign of -y
int sDif = dif >> 31; // get the sign of the difference
return (!(sX ^ sY) | !(sDif ^ sX));

我尝试过的每个案例都有效。我通过获取 y 而不是 ny 的符号来改变@HackerBoss 的建议，然后反转 return 语句中的两个检查。这样，如果符号相同，或者结果的符号与 x 的符号相同，则 return 为真。

Answer 3

请购买并阅读 Hacker's Delight 以获得这些内容。很好的一本书。

int overflow_subtraction(int a, int b, int overflow)
{
    unsigned int sum = (unsigned int)a - (unsigned int)b; // wrapround subtraction
    int ssum = (int)sum;
    // Hackers Delight: section Overflow Detection, subsection Signed Add/Subtract
    // Let sum = a -% b == a - b - carry == wraparound subtraction.
    // Overflow in a-b-carry occurs, iff a and b have opposite signs
    // and the sign of a-b-carry is opposite of a (or equivalently same as b).
    // Faster routine: res = (a ^ b) & (sum ^ a)
    // Slower routine: res = (sum^a) & ~(sum^b)
    // Oerflow occured, iff (res < 0)
    if (((a ^ b) & (ssum ^ a)) < 0)
        panic();
    return ssum;
}

C 在减法期间检查溢出

C checking for overflow during subtraction

c

integer-overflow

bitwise-operators