如何证明C语句-x,~x + 1和〜(x-1)产生相同的结果？

Question

我想知道这个陈述背后的逻辑,证据.对于任何x,C表达式-x,~x + 1和〜(x-1)都产生相同的结果.我可以证明这对于具体的例子是正确的.我认为证明这一点的方法与两个补码的属性有关.有任何想法吗？

Answer 1

考虑将数字添加到其按位补码时得到的结果.n位整数x的按位补码具有1,其中x具有0,反之亦然.所以很明显看到:

x + ~x = 0b11 ... 11(所有1的n位值)

无论x中的位数如何.此外,请注意,向填充了所有1的n位数添加1将使其换行为零.因此,我们看到:

x + ~x + 1 = 0b11 ... 11 + 1 = 0且~x + 1 = -x.

同样,注(x - 1)+〜(x - 1)= 0b11 ... 11.然后(x-1)+〜(x-1)+ 1 = 0,并且〜(x-1)= -x.

Answer 2

我不确定你可以从任何有用的公理证明这一点,除了相当简单的减少回到我们已经在现代整数ALU中定义负数以二进制补码的事实.

计算机不具备与二进制补码硬件实现,它只是有各种吸引人的特性,几乎一切都建立了这样的这些日子.(但不是浮点!这是一个补充!)

因此,我们构建了一个恰好代表2的补码的负数的机器.显示负数以二进制补码表示的表达式是准确的,但这仅仅是因为我们以这种方式定义它们.这是现代机器中负整数的公理基础.

既然我们用二元补语来定义否定,那么你实际上指的是公理,尽管我认为这就是所有证明最终的作用.

也许这就是为什么我不是一个理论家.:-)