2

我正在尝试确定是否可以计算两个 32 位整数之和而不会溢出，同时仅使用某些按位运算符和其他运算符。因此，如果整数 x 和 y 可以相加而不会溢出，则以下代码应返回 1，否则返回 0。

(((((x >> 31) + (y >> 31)) & 2) >> 1))

但是，它应该为 1 时返回 0，反之亦然。当我使用逻辑 NOT (!) 运算符或使用 0x1 的按位 XOR (^) 时，它不能解决问题。

!(((((x >> 31) + (y >> 31)) & 2) >> 1))

(((((x >> 31) + (y >> 31)) & 2) >> 1) ^ 0x1)

^ 这些不起作用。

提前致谢。

4

5 回答 5

8

这有点干净：

~(x & y) >> 31

更新

克里斯的评论是正确的。这段代码所做的只是检查两个 MSB 是否都已设置。

我只是在看 kriss 的答案，我突然想到，假设无符号整数，只需一个加法和按位运算符就可以完成同样的事情。

((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)

第一个带括号的部分将两个 MSB 都设置为 0，然后将结果相加。任何进位都将在结果的 MSB 中结束。下一个位掩码隔离该进位。最后一项检查 x 或 y 上的集合 MSB，这会导致总体进位。要满足问题中的规范，只需执行以下操作：

~(((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)) >> 31
于 2010-09-13T00:57:42.770 回答
2

假设这两个数字都是无符号整数。如果您使用有符号整数，则会有点棘手，因为有两种方法可以溢出，要么添加两个大的正数，要么添加两个大的负数。无论如何检查最高有效位是不够的，因为加法会传播进位位，您必须将其考虑在内。

对于无符号整数，如果您不想作弊，一个简单的方法是：

 (x+y < x) || (x+y < y)

这将起作用，因为大多数编译器在发生溢出时不会做任何事情，就让它发生吧。

您还可以指出，要发生溢出，两个数字中的至少一个必须将其最高有效位设置为 1。因此，类似的东西应该可以工作（当心，未经测试），但它比其他版本更复杂。

/* both Most Significant bits are 1 */
(x&y&0x80000000)        
/* x MSb is 1 and carry propagate */
 ||((x&0x80000000)&&(((x&0x7FFFFFFF)+y)&0x80000000))
/* y MSb is 1 and carry propagate */
 ||((y&0x80000000)&&(((y&0x7FFFFFFF)+x)&0x80000000))
于 2010-09-13T02:45:26.520 回答
1

合乎逻辑！对我来说很好。

me@desktop:~$ cat > so.c
#include <stdio.h>

void main() {
    int y = 5;
    int x = 3;
    int t;
    t = (((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
    t = !(((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
}
^D
me@desktop:~$ gcc -o so so.c
me@desktop:~$ ./so
0
1
me@desktop:~$ uname -a
Linux desktop 2.6.32-23-generic #37-Ubuntu SMP Fri Jun 11 07:54:58 UTC 2010 i686 GNU/Linux
于 2010-09-13T01:00:49.540 回答
1

没有简单的基于位算术的溢出测试，因为加法涉及进位。但是有一些简单的溢出测试不涉及调用溢出或无符号整数换行，它们甚至比进行加法然后检查溢出更简单（这当然是有符号整数的未定义行为）：

对于无符号整数x和y：(x<=UINT_MAX-y)

对于有符号整数，首先检查它们是否有相反的符号。如果是这样，添加是自动安全的。如果它们都是正面的，请使用(x<=INT_MAX-y). 如果它们都是负数，请使用(x>=INT_MIN-y).

于 2010-09-13T04:30:37.687 回答
0

那些有符号整数是偶然的吗？您的逻辑看起来应该适用于无符号整数（无符号整数），但不适用于常规整数，因为在这种情况下，移位将保留符号位。

于 2010-09-13T02:07:53.710 回答