How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results?

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?

Solution 1:

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.

Solution 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. :-)

Solution 3:

~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.

Solution 4:

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:

-2    10
-1    11
 0    00
+1    01

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+1 inverting the bits. You can easily verify that using +1 and -1 in our 2-bit example.

Solution 5:

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.