~x + ~y == ~(x + y) 总是错误的吗？

Question

~x + ~y == ~(x + y) 总是错误的吗？

153

这段代码是否总是会计算为false？两个变量都是二进制补码的有符号整数。

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

我觉得应该有一些符合条件的数字。我尝试测试介于-5000和5000之间的数字，但从未达到相等的情况。是否有一种设置方程式以找到满足条件的解决方案？

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

- Steve

6

你需要证明还是什么？ - Alvin Wong

26

请注意，在有符号整数溢出的情况下，其技术上是未定义行为。因此，即使在假定严格的二进制补码的情况下也有可能返回 true。 - Mysticial

1

@AlvinWong 是的，一个解释会很好。 - Steve

4

当我最初发布这个问题时，我假设将问题标记为“作业”会要求人们提供提示来帮助我解决问题（正如“作业”标签的描述所述），而不仅仅是给出答案。那就是为什么我只是简单地提出了问题:) @AlexLockwood - Steve

1

@JonaChristopherSahnwaldt，是的，这是一个更好的理由，谢谢 :) - Alex Lockwood

显示剩余8条评论

11个回答

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)始终为假。

尽管如此，事实上C语言不要求使用二进制补码，因此我们还必须考虑...

一进制补码

在一进制补码中，-x表示为~x。零是一个特殊情况，它具有所有0（+0）和所有1（-0）的表示方法，但我记得C语言要求+0 == -0，即使它们具有不同的位模式，所以这不应该是问题。只需用-替换~即可。

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

这对于所有的x和y都是真的。

- dan04

13

+1 是为了一个实际上平等考虑补码和反码的答案。 - user

13

@dan04，+0 == -0。这是C语言中有意义的表达方式。 :) - Alex Lockwood

32

只考虑x和y的最右边一位（例如，如果x == 13是二进制中的1101，我们只看最后一位，即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：

这个也留给你自己完成。

你可以证明无论输入什么，最右边的位在等式的左边和右边总是不同的，因此你已经证明了两边不相等，因为它们至少有一个位不同。

- Paul

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。

- Karthik Kumar Viswanathan

4

你问@nhahtdh如何定义非固定宽度数字的~操作？ - hamstergene

1

我使用这些位数给出了这个答案，以便与课堂教学相对应。请注意，~x高度依赖于用于表示数字的位数n。因此，在尝试实验验证时，坚持使用一个位数是明智的选择。 - Karthik Kumar Viswanathan

1

@hamstergene：我知道位数是固定的，但我的观点是它不一定要是那些数量（8、16等）。 - nhahtdh

1

这些值很容易编写一个程序来验证答案。只要~x和~y与给定的匹配，它就适用于任何n。 - Karthik Kumar Viswanathan

1

@hamstergene：我对证明没有问题，只是这些数字给人一种错误的印象，认为它只适用于那些情况。 - nhahtdh

显示剩余3条评论

27

提示:

x + ~x = -1 (mod 2ⁿ)

假设问题的目标是测试您的数学能力（而不是阅读C规范的技能），这个方程式可以帮助您得到答案。

- user541686

2

只有在二进制补码机器上才能实现。（C标准并不要求这样） - Billy ONeal

12

这句话的意思是“这就像是说‘只适用于双臂人’”。 - dan04

2

@dan04：不，它并不是。我很想说所有的有符号数和反码表示法已经从世界上消失了。但如果这样说，那就错了。C标准不允许你做出这种假设；因此，我会说大多数情况下做出这种假设的代码都是糟糕的代码。（特别是当有更好的处理有符号数的方法时，而且通常无符号数在大多数情况下可能是更好的选择时） - Billy ONeal

10

在补码表示法中，包括1的补码、2的补码（甚至42的补码），都可以被证明：

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

现在让 a = y，我们有：

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

或：

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

因此，在二进制补码中，~0 = -1这个命题是错误的。

而在一的补码中，~0 = 0这个命题是正确的。

- ypercubeᵀᴹ

7

根据Dennis Ritchie的书籍，C语言默认不实现二进制补码。因此，你的问题可能并非总是正确的。

- user1457474

5

假设 MAX_INT 是由 011111...111 （无论有多少位）表示的整数。那么你知道，~x + x = MAX_INT 和 ~y + y = MAX_INT，因此你可以确定 ~x + ~y 与 ~(x + y) 之间的差异是 1。

- Adrian Monk

5

C语言并不要求实现二进制补码。然而，对于无符号整数，类似的逻辑被应用。在这种逻辑下，差异将始终为1！

- user1422551

3

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

- user1472392

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex Lockwood · Accepted Answer

假设反证法成立，存在某个 x 和某个 y (mod 2ⁿ) 满足以下条件：

~(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(mod 2ⁿ)而言，~(x+y) != ~x + ~y。

^{*值得注意的是，在使用一补数算术的机器上，等式实际上对所有的x和y都成立。这是因为在一补数下，~x = -x。因此，~x + ~y == -x + -y == -(x+y) == ~(x+y)。}