Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
At the moment the maths behind binary 2s compliment seems like voodoo to me.
If I take 0011 (+3) and "flip and add 1", I get 1101 (-3)
If I apply the same process to 1101, ("flip and add 1"), I get back to the original positive value.
How is this so?
First, if we wouldn't get the same number after negating it twice, it wouldn't make much sense, right?
So we just need to prove that the "complement and add 1" has indeed the effect of negation, i.e., taking $x$ into $-x$ (and thus, $-x$ to $x$). (well, maybe except for an edge case I will mention below.)
A signed number of $n$ bits, $b_{n-1}, \ldots, b_1,b_0$ where each $b_i\in\{0,1\}$, is to be interpreted in the following way: the $i$-th bit amount $2^i$ except for the last bit (MSB). The MSB $b_{n-1}$ is what makes the number negative, and can be seen as having the value $-2^{n-1}$.
Sanity check.
4 bits. The number 5 is 0101 = 2^2+ 2^0 = 4+1. The number -5 is 1011 = -2^{3}+ 2^1+2^0 = -8+2+1 = -5.
With this in mind, given $x = -2^{n-1}b_{n-1} + \sum_{i=0}^{n-2}2^ib_i$ if we complement each bit ($b_i \to (1-b_i)$) we will get $$\begin{align}NOT(x) &= -2^{n-1}(1-b_{n-1}) + \sum_{i=0}^{n-2}2^i(1-b_i) \\ & = -2^{n-1} + \sum_{i=0}^{n-2}2^i - [-2^{n-1}b_{n-1} + \sum_{i=0}^{n-2}2^ib_i] \\ &= -1 -x \end{align}$$ therefore, $NOT(x)+1$ equals $-x$.
Note the edge case(s).If $x=0$ then negating it should give 0. Yet complementing each bit gives $111111 \ne 0$ and after +1 we will get back 0 (ignoring the carry). The other edge case is the maximal negative number $1000$ for 4-bit numbers. If we negate it we get $0111$ after complementing and $1000$ after adding 1 to the complemented number. In this case (and this case only) the 2-complement system "doesn't work" and gives that the negation of $x$ is $x$.
If we look at the numbers in an unsigned way, flipping a binary number $x$ on $n+1$ bits is computing $(2^{n+1} -1) - x = M - x$.
Proof for that: $x = \sum_0^n b_i2^i$. $x$ flipped : $\sum_0^n (1-b_i)2^i = \sum_0^n 2^i -\sum_0^n b_i2^i = (2^{n+1} - 1) - x$
Therefore, flip and add one : $y = (M - x) + 1$
Again : $z = (M - y) +1 = (M - ((M - x) + 1)) + 1$
$z = (M - (M - x) - 1) + 1$
$z = M - M + x - 1 + 1$
$z = x$
The other answers have given rigorous mathematical answers, so I'll try to give a more intuitive way to understand 2's complement. I'll use 4-bit numbers like the original example.
First principle: for a 4-bit number n, 1111 - n is the same as flipping the bits of n. If you try a few examples, hopefully this is obvious.
Second principle: since we ignore carries out of our 4-bit number, 10000 and 0000 are the same.
Using the first principle, flipping bits and adding 1 is the same as (1111 - n) + 1. Rearranging, this is (1111 + 1) - n, or 10000 - n. By the second principle, this is just 0 - n which is the negation of n.
This demonstrates that "flip and add 1" negates a number. Negating a number twice yields the original number, so doing "flip and add 1" twice also yields the original number.
This might not be a formal answer but give you a idea what happens when you do 2's complement. Take any binary number and do the following:
This is shortcut method to get 2's complement of a number Example:
Binary number= 01000100
2's complement= 10111100 (You can verify the answer and this shortcut always works)
You can see we started from right, copied bits until a 1 is reached, then flip the rest. So this means for our example, last 3 bits wont be flipped and rest will be flipped. If we again apply 2's complement on this number, last 3 bit wont be flipped and rest will be.
i.e: Original Number = 01000100
2's Complement = 10111100
2's complement of 10111100 = 01000100 (original number obtained)
So you can imagine 2's complement flips few bits and always leaves few bits at the Left End. This is why 2's complement work because we flip only specific bits every time. If you don't understand any part please comment
