6

我想知道这句话背后的逻辑，证明。C 表达式 -x、~x+1 和 ~(x-1) 对于任何 x 都产生相同的结果。对于具体的例子，我可以证明这是正确的。我认为证明这一点的方法与二进制补码的性质有关。有任何想法吗？

4

5 回答 5

16

考虑将数字添加到其按位补码时得到的结果。n 位整数 x 的按位补码在 x 为 0 的任何地方都为 1，反之亦然。所以很明显：

x + ~x = 0b11...11（全为 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。

于 2010-02-17T07:07:01.797 回答
8

我不确定您是否可以从任何有用的公理中证明这一点，除了相当微不足道的归约，回到我们在现代整数 ALU 中将负数定义为二进制补码这一事实。

计算机不必用二进制补码硬件来实现，只是有各种吸引人的特性，而且现在几乎所有东西都是这样构建的。（但不是浮点数！那些是补码！）

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

由于我们根据二进制补码定义否定，因此您本质上是指公理，尽管我认为这就是所有证明最终要做的事情。

也许这就是为什么我不是一个真正的理论家。:-)

于 2010-02-17T05:40:54.063 回答
3

~x+1 等价于 -x 的 2 的补码 + 1（即负数）表示，~(x-1) 也表示相同（考虑最后一位为 1 的情况，~(x-1) = ~( b1b2.b(n-1)1 - 0) = b1'b2'...b(n-1)'1 = b1'b2'...b(n-1)'0 + 1 = ~x+ 1. 最后一位的类似情况保持为 0。~(x-1) = ~(b1b2..bi100..00 - 1) = ~b1b2..bi011..11 = b1'b2'..bi'100。 .00 = b1'b2'..bi'011..11 + 1 = ~x + 1。

于 2010-02-17T05:40:08.480 回答
2

我将尝试提供一个每个人都应该方便的直观解释。如果您坚持，我们可能会尝试更正式的方法。

在二进制补码表示中，为了使零元素具有唯一表示，我们牺牲了一个正元素。结果，有一个额外的负数没有正镜像。

因此，给定 2 位，我们得到：{+1, 0, -1, -2}在二进制中表示为：

-2    10
-1    11
 0    00
+1    01

因此，我们可以将零视为一面镜子。现在，给定一个整数 x，如果我们想反转它的符号，我们可以从反转所有位开始。如果正面和负面之间没有零，这就足够了。但由于零发生了转变，从积极的方面来说，我们已经弥补了这一点。

问题中提到的两个表达式在反转位之前~(x-1)和之后进行了这种补偿。您可以在我们的 2 位示例中使用和~x+1轻松验证这一点。+1-1

于 2010-02-17T05:52:33.097 回答
1

通常这是不正确的，因为 C 标准不需要使用二进制补码来表示负数。

特别是，未定义将 ~ 应用于有符号类型的结果。

但是，据我所知，所有现代机器都对整数使用二进制补码。

于 2010-02-17T06:33:07.087 回答