如何证明 C 语句 -x、~x+1 和 ~(x-1) 产生相同的结果？
我想知道这个说法背后的逻辑，证据。 C 表达式 -x、~x+1 和 ~(x-1) 对于任何 x 都会产生相同的结果。我可以通过具体例子证明这是正确的。我认为证明这一点的方法与补码的性质有关。有什么想法吗？
I want to know the logic behind this statement, the proof. The C expression -x, ~x+1, and ~(x-1) all yield the same results for any x. I can show this is true for specific examples. I think the way to prove this has something to do with the properties of two's complement. Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
考虑一下当您将一个数字与其按位补码相加时会得到什么。 n 位整数 x 的按位补码在 x 为 0 的地方都为 1，反之亦然。因此可以清楚地看到：
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。
Consider what you get when you add a number to its bitwise complement. The bitwise complement of an n-bit integer x has a 1 everywhere x has a 0, and vice versa. So it's clear to see:
x + ~x = 0b11...11 (n-bit value of all ones)
Regardless of the number of bits in x. Further, note that adding one to an n-bit number filled with all ones will make it wrap to zero. Thus we see:
x + ~x + 1 = 0b11...11 + 1 = 0
and ~x + 1 = -x.
Similarly, note (x - 1) + ~(x - 1) = 0b11...11. Then (x - 1) + ~(x - 1) + 1 = 0, and ~(x - 1) = -x.
我不确定你可以从任何有用的公理来证明这一点，除了相当简单的归约到我们在现代整数 ALU 中将负数定义为二进制补码这一事实。
计算机不必用二进制补码二进制硬件来实现，只是有各种吸引人的属性，而且现在几乎所有东西都是这样构建的。 （但不是浮点数！这些是 1 的补码！）
因此，我们构建了一台恰好以 2 的补码表示负数的机器。显示以二进制补码表示的负数的表达式是准确的，但这仅仅是因为我们以这种方式定义了它们。这是现代机器中负整数的公理基础。
由于我们用二进制补码来定义否定，因此您本质上是指公理，尽管我认为这就是所有证明最终要做的事情。
也许这就是为什么我不是一个真正的理论家。 :-)
I'm not certain you can prove this from any sort of useful axiom other than the rather trivial reduction back to the fact that we have defined negative numbers in modern integer ALUs to be in twos complement.
Computers don't have to be implemented with twos complement binary hardware, it's just that there are various attractive properties and almost everything is built that way these days. (But not floating point! Those are one's complement!)
So we build a machine that happens to represent negative numbers in 2's complement. Expressions that show negative numbers to be represented in two's complement are accurate, but only because we defined them that way. That's the axiomatic basis for negative integer numbers in modern machines.
Since we define negation in terms of two's complement, you are essentially referring to the axioms, although I suppose that's what all proofs ultimately do.
Maybe this is why I'm not really a theory guy. :-)
~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。
~x+1 is equivalent to 2's complement + 1 (i.e. negative number) representations of -x, ~(x-1) also represents the same (consider the case where last bit is 1, ~(x-1) = ~(b1b2.b(n-1)1 - 0) = b1'b2'...b(n-1)'1 = b1'b2'...b(n-1)'0 + 1 = ~x+1. Similar case hold for last bit is 0. ~(x-1) = ~(b1b2..bi100..00 - 1) = ~b1b2..bi011..11 = b1'b2'..bi'100..00 = b1'b2'..bi'011..11 + 1 = ~x + 1.
我将尝试提供一个直观的解释，每个人都会觉得方便。如果您坚持，我们可以尝试更正式的方法。
在二进制补码表示中，为了获得零元素的唯一表示，我们牺牲一个正元素。结果，就多了一个没有正镜像的负数。
因此，给定 2 位，我们得到：
{+1, 0, -1, -2}，用二进制表示为：因此，我们可以将零视为镜像。现在，给定一个整数 x，如果我们想要反转它的符号，我们可以从反转所有位开始。如果正数和负数之间没有零就足够了。但由于零发生了积极的转变，我们已经对此进行了补偿。
问题中提到的两个表达式在
~(x-1)之前和~x+1反转位之后进行补偿。您可以在我们的 2 位示例中使用+1和-1轻松验证这一点。I'll try to present an intuitive explaination that everybody should find handy. If you insist we may try a more formal approach.
In two's complement representation, in order to have a unique representation of the zero element, we sacrifice one positive element. As a result, there is an extra negative number that has no positive mirror.
So, given 2 bits, we get:
{+1, 0, -1, -2}which would be represented in binary as:So, we may think of the zero as a mirror. Now, given an integer x, if we want to invert its sign, we can start by inverting all bits. This would have been enough if there was no zero between the positives and negatives. But since the zero makes a shift, in positives, we have compensate for that.
The two expressions mentioned in the question make this compensation before
~(x-1)and after~x+1inverting the bits. You can easily verify that using+1and-1in our 2-bit example.一般来说，这是不正确的，因为 C 标准不要求使用二进制补码来表示负数。
特别是，将 ~ 应用于有符号类型的结果未定义。
然而，据我所知，所有现代机器都使用整数的二进制补码。
In general this is not true, as the C standard doesn't require the use of twos complement to represent negative numbers.
In particular, the result of applying ~ to a signed type is not defined.
However, as far as I know all modern machines use twos complement for integers.