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.

 

[Roberto Pavani]

Spoiler: Simple solutions

y=1+NOT(x) ≡ −x (mod $2^n$)

1+NOT(y) ≡ −y ≡ x (mod $2^n$).

Or even better:

T(x)=1+NOT(x) ≡ −x (mod $2^n$)
T(T(x)) ≡ −(−x) ≡ x (mod $2^n$)

 

[emillindberg]

The easiest way to see this is to treat n bit numbers as arithmetic modulo 2^n.

For any n bit number b, NOT b changes every 0 to 1 and every 1 to 0. Numerically, that means NOT b = 2^n - 1 - b.

So 1 + NOT b = 2^n - b, which is equivalent to -b modulo 2^n. In other words, NOT b + 1 gives you the additive inverse of b.

Now apply the same operation again. Since the additive inverse of -b is b, we get 1 + NOT(1 + NOT b) = b modulo 2^n.

So taking the two's complement twice always gives you the original n bit number.

 

[wrobel]

I am not a specialist in this field but it looks like $1+(1-(1+(1-x)))$
and I think that such operations must be considered in $\mathbb{Z}_2$

 

[Gavran]

We can define the function $f(x)=1+\text{NOT}x$ and prove that $f^{-1}(x)=f(x)$.

$\begin{align} f(x)=1+\text{NOT}x&\implies f(x)-1=\text{NOT}x\nonumber\\ &\implies \text{NOT}(f(x)-1)=x\nonumber\\ &\implies f^{-1}(x)=\text{NOT}(x-1)\nonumber\\ \end{align}$

For
$$ x=(\sum_{i=0}^{n}x_i10^i)_2 $$
where
$\begin{align} \text{NOT}x&=(\sum_{i=0}^{n}(1-x_i)10^i)_2\nonumber\\ &=(\sum_{i=0}^{n}1\cdot10^i-\sum_{i=0}^{n}x_i10^i)_2\nonumber\\ \end{align}\\$

we have

$\begin{align} f(x)&=1+\text{NOT}x\nonumber\\ &=(1+(\sum_{i=0}^{n}1\cdot10^i-\sum_{i=0}^{n}x_i10^i))_2\nonumber\\ &=(\sum_{i=0}^{n}1\cdot10^i-(\sum_{i=0}^{n}x_i10^i-1))_2\nonumber\\ &=\text{NOT}(x-1)\nonumber\\ &=f^{-1}(x)\nonumber\\ \end{align}\\$