1

作为谜题的一部分，我被要求实现一个函数，该函数检查两个整数是否可以加在一起而不会溢出。法律行动：！~ & ^ | + << >>。

例如，对于 x = 0x80000000 和 y = 0x80000000，函数应该返回 0，因为它溢出，但对于 x = 0x80000000 和 y = 0x70000000，结果将是 1。

到目前为止，我的解决方案是：

int addOK(int x, int y) {
    int mask = ~(1 << 31);        // 0x7fffffff
    int newX = (mask & (x >> 1)); // Shift 1 to the right to make space for overflow bit
    int newY = (mask & (y >> 1));
    int add = newX + newY;        // Add shifted x and y - overflow bit will be the MSB
    int res = (add & ~mask);      // Set all bits to 0 except MSB - MSB 1 iff overflow 0 otherwise
    int endRes = !res;            // 0x80000000 -> 0x00000000, 0x00000000 -> 0x00000001
    printf("mask %x newX %x newY %x add %x ~mask %x res %x endRes %x\n",mask, newX, newY, add, ~mask, res, endRes);
    return endRes;
}

对于 x = 0x80000000 和 y = 0x80000000，该函数打印以下内容：

mask 7fffffff newX 40000000 newY 40000000 add 80000000 ~mask 80000000 res 0 endRes 1

现在我的问题是为什么是res0？它应该是 0x80000000，因为add和~mask都是 0x80000000。谁能向我解释这种行为？

4

1 回答 1

0

我在 32 位 Linux 上尝试了我的代码，但没有出现上述特定问题。

我得出结论，问题是由于我使用的操作系统和/或编译器造成的。由于我自己没有编写测试或 makefile 并且到目前为止对 C 还不够熟悉，所以我仍然不明白到底出了什么问题。

但正如帕特指出的（谢谢）

您是在为有符号或无符号溢出而拍摄吗？您的所有值都是有符号的，但您显然只是在寻找第 31 位的进位，这不是有符号溢出。-拍

我写的算法一开始就被破坏了。我对溢出有错误的想法。我必须检查当添加两个负整数并溢出到正数或两个正数到负数时发生的有符号溢出。（根据二进制补码算术）。

如果有人对这里感兴趣是我的工作代码：

int addOK(int x, int y) {
    int mask = 1 << 31;   // 0x80000000
    int msbX = mask & x;  // Set all bit to 0 except sign bit
    int msbY = mask & y; 
    int msbSum = mask & (x + y);
    int prob1 = !(msbX ^ msbY);   // == 1 iff x and y have the same sign - thats when an overflow may occur
    int prob2 = !(msbX ^ msbSum); // == 0 iff x + y and x have a different sign - thats when an overfolow may occur
    return (!prob1) | prob2;      // There is an overflow iff prob1 == 1 and prob2 == 0
}

在这段代码中，我上面询问的问题甚至没有发生，我可以再次直接在我的 Mac 上运行它。

于 2014-09-23T14:49:33.713 回答