5

As we all know usually negative numbers in memory represents as two's complement numbers like that

from x to ~x + 1

and to get back we don't do the obvious thing like

~([~x + 1] - 1)

but instead we do

~[~x + 1] + 1

can someone explain why does it always work? I think I can proof it with 1-bit, 2-bit, 3-bit numbers and then use Mathematical induction but it doesn't help me understand how exactly that works.

Thanks!

Solar Dia
  • 53
  • 4
  • 1
    Related: [How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results?](https://stackoverflow.com/q/2278518) other 2's complement identities. – Peter Cordes Dec 05 '20 at 22:39

2 Answers2

5

That's the same thing anyway. That is, ~x + 1 == ~(x - 1). But let's put that aside for now.

f(x) = ~x + 1 is its own inverse. Proof:

~(~x + 1) + 1 =
(definition of subtraction: a - b = ~(~a + b))
x - 1 + 1 =
(you know this step)
x

Also, ~x + 1 == ~(x - 1). Why? Well,

~(x - 1) =
(definition of subtraction: a - b = ~(~a + b))
~(~(~x + 1)) =
(remove double negation)
~x + 1

And that (slightly unusual) definition of subtraction, a - b = ~(~a + b)?

~(~a + b) =
(use definition of two's complement, ~x = -x - 1)
-(~a + b) - 1 =
(move the 1)
-(~a + b + 1) =
(use definition of two's complement, ~x = -x - 1)
-(-a + b) =
(you know this step)
a - b
harold
  • 61,398
  • 6
  • 86
  • 164
  • thats perfect. i was struggling with removing parentheses correctly there. where can i read about that definition of subtraction more detail? – Solar Dia Nov 07 '15 at 07:02
  • @SolarDia I don't know but I added a proof for that as well, but maybe it's turning slightly circular now.. – harold Nov 07 '15 at 10:02
  • thank u sir, its not circular and it looks very consistent. definition of two's complement -> definition of subtraction -> ~(~x + 1) + 1 == x not sure if its even fair to do so but i like that) will up this comment when i get enough reputation. – Solar Dia Nov 09 '15 at 09:52
2

This is because if you increment ~x (assuming no overflow). Then converting it to back to x, you've incremented relative to ~x, but decremented relative to x. Same thing applies vice versa. Assuming your variable x has a specific value, every time you increment it, relative to ~x you'll notice it decrements.

From a programmer's point of view, this is what you'd essentially witness.

Let short int x = 1         (0x0001)
then ~x = 65534             (0xFFFE)
~x + 1 =  65534 + 1         (0xFFFF)
~(~x+1) = 0                 (0x0000)
~(~x+1) + 1 = 0 + 1         (0x0001)
Iancovici
  • 5,574
  • 7
  • 39
  • 57