Prove that 1 + NOT (1 + NOT x) = x

[lemonfrostt]

In binary, the two's complement representation of a negative number is found by NOT b + 1, with the leading bit being a sign bit. In general, prove that applying the operation NOT b + 1 twice to some n-bit binary number yields the original number b.

I found this conceptually straightforward but hard to satisfactorily prove. Try it yourself.

Spoiler: One possible proof

The set of n-bit binary numbers under (+) form a cyclic group (g = 1) of order 2ⁿ.

b + NOT b = 1^-1 (Ones' complement).

Therefore 1 + NOT b = b^-1. (b^-1)^-1 = b.

(b^-1 denotes additive inverse.)

 

[.Scott]

To be explicit about the order of operations, two's complement is NEG(b) = (NOT b)+1.

Spoiler

NOT b maps [00...00 ... 11...11[ to [11...11 ... 00...00]
(NOT b)+1 maps [00...00 ... 11...11] to [11...11 ... 00...00] and then to [00...00, 11...11, 00...01 ]
we can restate that as:
NEG(b) maps [00...00, 00...01 ... 11...11] to [00...00, 11...11, 00...01 ]
So it keeps 00...00 and reverses the order of all the others.
Doing hits twice will keep 00...00, and reverse the order of all the others twice. Yielding no change.

 

[berkeman]

In general, prove that applying the operation

Is this question for schoolwork? If so, I can move the thread to the schoolwork forums.

 

[lemonfrostt]

Is this question for schoolwork? If so, I can move the thread to the schoolwork forums.

The schoolwork question was much weaker. I made it somewhat more difficult to entertain myself.