153

此代码是否总是评估为假？两个变量都是二进制补码符号整数。

~x + ~y == ~(x + y)

我觉得应该有一些满足条件的数字。我尝试测试两者之间的数字-5000，5000但从未达到相等。有没有办法建立一个方程来找到条件的解决方案？

将一个换成另一个会在我的程序中导致一个潜在的错误吗？

4

11 回答 11

237

为了矛盾起见，假设存在 some xand some y(mod 2 n ) 使得

~(x+y) == ~x + ~y

通过二进制补码*，我们知道，

      -x == ~x + 1
<==>  -1 == ~x + x

注意到这个结果，我们有，

      ~(x+y) == ~x + ~y
<==>  ~(x+y) + (x+y) == ~x + ~y + (x+y)
<==>  ~(x+y) + (x+y) == (~x + x) + (~y + y)
<==>  ~(x+y) + (x+y) == -1 + -1
<==>  ~(x+y) + (x+y) == -2
<==>  -1 == -2

因此，矛盾。因此，~(x+y) != ~x + ~y对于所有x和y(mod 2 n )。

*有趣的是，在具有补码算法的机器上，等式实际上对所有x和都成立y。这是因为在一个补码下，~x = -x。因此，~x + ~y == -x + -y == -(x+y) == ~(x+y).

于 2012-06-20T02:35:44.440 回答
113

二进制补码

在绝大多数计算机上，如果x是整数，则-x表示为~x + 1。等效地，~x == -(x + 1)。在您的等式中进行此替换给出：

  • ~x + ~y == ~(x + y)
  • -(x+1) + -(y+1) = -((x + y) + 1)
  • -x - y - 2 = -x - y - 1
  • -2 = -1

这是一个矛盾，所以~x + ~y == ~(x + y)总是false。

也就是说，学究们会指出 C 不需要二进制补码，所以我们还必须考虑......

一个人的补充

在一个的补码中，-x简单地表示为~x。零是一种特殊情况，同时具有全 0 ( +0) 和全 1 ( -0) 表示，但 IIRC、C 要求+0 == -0即使它们具有不同的位模式，所以这应该不是问题。只需替换~为-.

  • ~x + ~y == ~(x + y)
  • -x + (-y) = -(x + y)

这对所有和都是正确的。xy

于 2012-06-20T05:42:05.910 回答
32

只考虑两者的最右边的位x和y（即，如果x == 13它1101在基数 2 中，我们将只看最后一位， a 1）然后有四种可能的情况：

x = 0，y = 0：

左轴：~0 + ~0 => 1 + 1 => 10
右轴：~(0 + 0) => ~0 => 1

x = 0，y = 1：

左轴：~0 + ~1 => 1 + 0 => 1
右轴：~(0 + 1) => ~1 => 0

x = 1，y = 0：

我将把它留给你，因为这是家庭作业（提示：它与前面的 x 和 y 交换相同）。

x = 1，y = 1：

我也会把这个留给你。

您可以证明在给定任何可能的输入的情况下，等式的左侧和右侧的最右边的位总是不同的，因此您已经证明两边不相等，因为它们至少有一个被翻转的位从彼此。

于 2012-06-20T02:25:19.980 回答
27

如果位数为 n

~x = (2^n - 1) - x
~y = (2^n - 1) - y


~x + ~y = (2^n - 1) +(2^n - 1) - x - y =>  (2^n + (2^n - 1) - x - y ) - 1 => modulo: (2^n - 1) - x - y - 1.

现在，

 ~(x + y) = (2^n - 1) - (x + y) = (2^n - 1) - x - y.

因此，它们总是不相等的，相差 1。

于 2012-06-20T02:21:15.067 回答
27

暗示：

x + ~x = -1（模 2 n）

假设问题的目标是测试您的数学（而不是您阅读 C 规范的技能），这应该可以让您找到答案。

于 2012-06-20T02:24:52.570 回答
10

在 one's 和 two's（甚至 42's）补码中，可以证明：

~x + ~y == ~(x + a) + ~(y - a)

现在让a = y我们有：

~x + ~y == ~(x + y) + ~(y - y)

或者：

~x + ~y == ~(x + y) + ~0

因此，在二进制补码中~0 = -1，命题为假。

反之~0 = 0，命题为真。

于 2012-06-20T13:12:40.833 回答
7

根据 Dennis Ritchie 的书，C 默认情况下不实现二进制补码。因此，您的问题可能并不总是正确的。

于 2012-06-20T04:12:24.807 回答
5

让MAX_INT是由011111...111（无论有多少位）表示的 int 。然后您知道~x + x = MAX_INT和~y + y = MAX_INT，因此您将确定~x + ~y和之间的区别~(x + y)是1。

于 2012-06-20T03:21:16.947 回答
5

C不要求二进制补码是实现的。但是，对于无符号整数，应用了类似的逻辑。在这个逻辑下，差异永远是 1！

于 2012-06-20T03:23:59.897 回答
3

当然，C 不需要这种行为，因为它不需要二进制补码表示。例如，~x = (2^n - 1) - x&~y = (2^n - 1) - y会得到这个结果。

于 2012-06-21T14:21:25.430 回答
0

啊，基础离散数学！

看看德摩根定律

~x & ~y == ~(x | y)

~x | ~y == ~(x & y)

对于布尔证明非常重要！

于 2012-06-23T01:25:33.450 回答