~x + ~y ==〜(x + y)总是假的？

Question

此代码是否总是评估为false？这两个变量都是两个补码签名的整数.

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

我觉得应该有一些数字满足条件.我试过测试之间的数字-5000,5000但从未达到平等.有没有办法建立一个方程来找到条件的解？

将一个换成另一个导致我的程序中的一个阴险的错误？

Answer 1

假设为了矛盾,存在一些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) != ~x + ~y对于所有x和y(mod 2 ⁿ).

^{*有趣的是,在具有一个补码算术的机器上,相等实际上适用于所有x和y.这是因为在一个人的补充下,~x = -x.因此,~x + ~y == -x + -y == -(x+y) == ~(x+y).}

Answer 2

两个人的补充

在绝大多数计算机上,如果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.零是一种特殊情况,具有all-0(+0)和all-1(-0)表示,但IIRC,C要求+0 == -0即使它们具有不同的位模式,所以这应该不是问题.刚刚替补~使用-.

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

这是真正的所有x和y.

Answer 3

只考虑两者的最右边x和y(IE.如果x == 13它1101在基数2中,我们只查看最后一位,a 1)然后有四种可能的情况:

x = 0,y = 0:

LHS:~0 + ~0 => 1 + 1 => 10
RHS:〜(0 + 0)=> ~0 => 1

x = 0,y = 1:

LHS:~0 + ~1 => 1 + 0 => 1
RHS:〜(0 + 1)=> ~1 => 0

x = 1,y = 0:

我会把这个留给你,因为这是作业(提示:它与之前的x和y交换相同).

x = 1,y = 1:

我也会把这个留给你.

你也可以说最右边的位将一直在给定的任何可能的输入方程的左手边,右手边不同,所以你已经证明双方不相等的,因为他们至少是翻转一个位彼此.

Answer 4

如果位数是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.

Answer 5

暗示:

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

假设问题的目标是测试你的数学(而不是你的阅读C规范技能),这应该可以帮助你找到答案.

Answer 6

在一个和两个(甚至是42个)的补充中,这可以证明:

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

现在让a = y我们拥有:

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

要么:

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

因此,在两个补语中~0 = -1,命题是错误的.

在一个补充中~0 = 0,命题是正确的.

Answer 7

根据Dennis Ritchie的书,C默认不实现二进制补码.因此,您的问题可能并非总是如此.

Answer 8

让MAX_INT是由表示的INT 011111...111(器,用于许多位有).然后,你知道,~x + x = MAX_INT和~y + y = MAX_INT,所以你会因此肯定知道之间的差别~x + ~y,并~(x + y)为1.

Answer 9

C不要求两个补码是实现的.但是,对于无符号整数,应用类似的逻辑.在这个逻辑下,差异总是1!