Numbers in programming languages are represented as binary sequences. All bits are equal to $0$ or $1$ except the most significant bit (MSB), which is equal to (has meaning as) $0$ or $−1$. For example, let us consider $8$-bit signed integers:
$$23_{10} = 16_{10} + 4_{10} + 2_{10} + 1_{10} = 00010111_2$$ $$-15_{10} = -128_{10} + 64_{10} + 32_{10} + 16_{10} + 1_{10}= 11110001_2$$
Prove that for an integer $n$
$$ \text{~} n = -(n+1)$$
where $~n$ is the bitwise complement to $n$
For example, if $n = 3_{10} = 00000011_2$ then ~$n$$ = 11111100_2 = -128_{10} + 64_{10} + 32_{10} + 16_{10} + 8_{10} + 4_{10} = -4_{10}$
Hint: use the fact that
$$\sum_{i=0}^N 2^i = 2^{N+1} - 1$$
I've been stuck on this exercise for more than an hour, and still don't see what to do.
The $-1$ in the hint can be represented in binary as $$11111111_2 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1$$
If the N in the hint equals $1$ for example, we have
$$2^{1+1} - 1 = 4 - 1 = 00000100_2 + 11111111_2 = 00000011_2$$
which does in fact equal $3$
I know how to add binary numbers together. I also learned that to find the negative of a binary number, we switch all $0$ to $1$, and all $1$ to $0$, and then add $1$, which is basically what they ask us to prove it seems. For me, this is just an axiom, nothing else, isn't it ?
Do you know how to prove that ? Even just a few hints would really help me a lot. Thank you so much for your help
Let $\tilde{n}$ denote the bit-wise complement of $n$. HINT: Note that $\tilde{n}+n=11111111_2 = -1$. Then using algebra from the equation $\tilde{n}+n=-1$, this yields the desired equation $\tilde{n} = -1-n = -(n+1)$, or in particular, $\tilde{n}=-(n+1)$.