Search code examples
cprooftwos-complement

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

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