作为一个谜题的一部分,我被要求实现一个函数来检查两个整数是否可以加在一起而不会溢出。法律行动:! ~ & ^ | + << >>.
例如,对于 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
现在我的问题是为什么 res
是 0?它应该是 0x80000000,因为 add
和 ~mask
都是 0x80000000。任何人都可以向我解释这种行为吗?
最佳答案
我在 Linux 32 位上尝试了我的代码,但没有出现上述特定问题。
我断定问题是由于我使用的操作系统和/或编译器造成的。由于我自己没有编写测试或 makefile,并且到目前为止对 C 还不够熟悉,所以我仍然不明白究竟出了什么问题。
但正如 pat 指出的那样(谢谢)
Are you shooting for signed or unsigned overflow? All of your values are signed, but you're apparently only looking for a carry-out of bit 31, which is not a signed overflow. -pat
我写的算法一开始就坏了。我对溢出的想法是错误的。我必须检查有符号溢出,当添加两个负整数并溢出到一个正数或两个正数到一个负数时会发生这种情况。 (根据补码算法)。
如果有人感兴趣,这里是我的工作代码:
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 上运行它。
关于c - C 中 & 运算符的奇怪行为,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25982218/