2
$\begingroup$

I'm learning about how computers store and manipulate integers, and I want to understand two's complement. Despite an abundance of web-sites demonstrating how to perform complement arithmetic, the only resource I've found explaining the math behind why it works is wikipedia, and I'm having a hard time following it.

Can anyone point me in the right direction?

$\endgroup$
3
$\begingroup$

Let's have a look at unsigned integers first.

With a fixed number of bits, one can only represent a finite "chunk" of the natural numbers, right? Say you have three bits, then you can represent up to $2^3=8$ different numbers. For unsigned arithmetic the natural choice is to take $\mathtt{000}$ to represent $0$, then $\mathtt{001}$ to represent $1$, and so on until $\mathtt{111}$ represents $7$. Then the arithmetic operations look almost like the "normal" ones, just with binary digits instead of decimal: $\mathtt{010}+\mathtt{011}=\mathtt{101}$. That is, until you consider overflow. What happens when you do $\mathtt{111}+\mathtt{001}$? If you had more than three bits you would say the result is $\mathtt{1000}$ and call it a day. But you only have three, so if you want to have a well defined result at all you'll have to discard some bits. But which ones?

In this case, one discards the most significant bits (that is, the ones at the left) and keeps only the three least significant ones. So in our example, $\mathtt{111}+\mathtt{001}=\mathtt{000}$. In technical terms one would say that our arithmetic implements the cyclic group $\mathbb{Z}_8$. What that means is that we can see our numbers as arranged in a circle, with $\mathtt{000}$, then $\mathtt{001}$, etc., until $\mathtt{111}$, and then wrapping back around at $\mathtt{000}$.

Now let's say we want to represent a different chunk of the integers, this time one including negative numbers. We know that we can only take eight of them, and we would like it to be as symmetric as possible around $0$. So we'll take the numbers from $-4$ through $3$; that is four negative ones and four nonnegative ones. $0$ through $3$ map just as before, to $\mathtt{000}$ through $\mathtt{011}$. What do we do with the negative ones? We would like them to come "before" $\mathtt{000}$. And what's the number just before $\mathtt{000}$ in our cyclic group? None other than $\mathtt{111}$. So we map $-1$ (the integer just before $0$) to $\mathtt{111}$ (the number just before $\mathtt{000}$ in the cycle). The rest of the negative numbers map accordingly.

Here's a visual way to interpret all this. Imagine the integers as a straight line of dots extending in both directions, and $\mathbb{Z}_8$ as a circle of eight notches. Now match up the dot for $0$ with the notch for $\mathtt{000}$ and wrap both "tails" of the integer line around the cycle, matching up dots to notches. Every dot maps uniquely to a notch, but every notch maps back to infinitely many dots. "Unsigned arithmetic" means "map back the notches to the contiguous segment of positive integers starting at $0$". "Complement arithmetic" means "map back the notches to the contiguous segment of integers with an equal number of negative and nonnegative dots".

$\endgroup$
2
  • $\begingroup$ This is an excellent explanation. I really like the cyclic analogy. $\endgroup$
    – ivan
    Mar 18 '15 at 2:24
  • $\begingroup$ Thanks :) I suppose you can also see now why this mapping lets one interpret the leading bit as a "minus sign bit" ($\mathtt{1}$ iff the number is negative). $\endgroup$
    – askyle
    Mar 18 '15 at 7:39

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .