Negative integers and subtraction

Humans usually use signed decimal notation for integers. We indicate whether a number is negative by preceding it with a minus sign. For instance, 837 is positive. (We could write +837, but a leading positive sign is usually omitted.) To make a number negative, just precede it with a minus sign: −837, for instance.

This notation has some advantages, including its "obviousness" to human readers, but binary notation is already so different from what we're most familiar with that this advantage is somewhat thin. It also makes it very easy to negate a number: just flip the first bit.

But this notation also has the somewhat strange property that there are two different representations for the number zero: 00000000_2S is one of them, of course. But consider what 10000000_2S means: it is −0, which is the same number as +0. What would happen if we did two different computations and asked if their results were equal... and they were both zero, but with different representations? We'd have to do an extra check for this case, always, if we wanted to give the correct answer.

Another disadvantage—of any representation of negative numbers—is that for a fixed number of bits (digits), there are a limited number of different values to represent. A three-digit base-10 number, for instance, can only have a thousand (10³) different values, 000-999. An eight-digit base-2 number can only represent 256 (2⁸) different values, from 00000000-11111111. If we "steal" that first bit to use as a sign bit, we can make an eight-bit representation of a possibly negative number able to represent as many as 128 (2⁷) negative numbers, but then we only can represent 128 different non-negative numbers. Still the same in total, but with a smaller maximum value. One effect of that is that in some particular situation, if we know for certain a number will never be negative, we can say so and thus our eight-bit numbers can represent values from 0-255 instead of −127-+127. We'll return to this problem a little later.

Finally, and most importantly, this notation has the disadvantage that extending basic arithmetic algorithms to work with negative numbers makes them a lot more complicated. Before we work further on that issue, though, let's review how subtraction works.

Subtraction

Although they are usually taught as very separate arithmetic subjects in elementary school, the concept of the negative number is closely related to the concept of subtraction. Let's take a moment to remind ourselves of how one standard subtraction algorithm works, and then see how we can connect it to negative numbers.

Adding and subtracting negative numbers

Basically, the entire group of algorithms was predicated on the idea that the core algorithms only worked on positive numbers, and when negatives would be involved, we first applied a separate set of transformations to make sure we could add or subtract positive numbers (and then maybe put a minus sign on the result).

Could engineers building a computer do that? Sure, they're algorithms and thus they can be implemented. But they're a bit complicated and we might hope for something better.

Two birds with one stone: complement notation

There are other ways to represent negative integers, one of which is complement notation. We'll first see how complement notation by working in base 10, and pretend for a moment that we have not yet come up with any representation for negative numbers. And we'll begin with a slightly artificial version of the task: let's say we can use three base-10 digits, but the only negative number we will ever need to represent is −1.

If we didn't need to represent any negative numbers, the choice of how to do the representation is fairly obvious: the representations 000-999 would represent the numbers 0-999 exactly as you'd expect.
Figure 1: The starting point But if we do want to represent −1, we simply cannot represent all of the numbers 0-999: we can still only represent a total of a thousand different values. One possibility that could be made to work but would be very confusing would be to just "shift over" by one, and say that 000 represents −1, 001 represents 0, and so on.
Figure 2: A first attempt at including −1 You can probably see how confusing that would be. But it could, in a pinch, represent −1 and all the numbers from 0-998, so it would technically meet our requirements.

But once we've acknowledged that just cannot represent 999 (at least, not while keeping the 3-digit limitation), we can imagine a different way to manage this offset: keep everything where it was, and simply replace 999 with −1 in the representation scheme.
Figure 3: A better attempt at including −1 This representation has the nice property that for most numbers, from 0-998, their representation is the "obvious" one. One way to describe the scheme to a human might be as follows: "Look, if you see a 999 it's special and represents −1, but anything else just represents itself." Any arithmetic done on the numbers 0-998 could work without modification.

If we tweak the task slightly to say that we need to also be able to represent −2, you can probably see that there's a straightforward update of this last system to represent all the integers from −2 to 997, by replacing 998 with −2 and keeping the rest the same.
Figure 4: Including −2 as well

So let's return to the original problem: representing negative numbers in general. We probably want to be able to represent more than just −1 and −2, though of course the more negative numbers we choose to include, the less positive numbers we'll be able to represent. It seems reasonable to aim for about half and half, so with a thousand representable numbers we'll try to represent about 500 negative numbers and about 500 positive numbers.
Figure 5: 10's complement (3 digits) This is called 10's complement notation, so named because negative numbers are represented as the complement of some power of ten. For instance, in this 3-digit version, the representation of −3 is 1000−3 or 997.

By convention, the halfway number (here 500) is assigned to the negatives, so that we can look only at the first digit of the representation to decide whether a representation corresponds to a positive number or a negative number: in 10's complement, which is in base 10, if the representation starts with 0-4 it is a positive number, and if it starts with 5-9 it is a negative number. To compute which negative number, you can subtract the appropriate power of ten (here, 1000).

It's also very important to remember that for the system to work (and to preserve that convenient odometer-rollover effect), the number of digits must be fixed at the start of the problem and not change. From here on, our 10's complement examples will be worked on six digits (to allow for more interesting problems), and that means that the representation of (for example) −3 will not be 997, but rather 999997. In a six-digit system, 997—or rather 000997—would in fact represent nine hundred and ninety seven, because it starts with a zero.

Adding with complement notation

So far, this seems pretty decent: at the cost of having a slightly more complicated algorithm to find the negative representation of a number (rather than just drawing a minus sign), we have made our addition algorithm simpler, because we don't have to do anything special or different if one or the other or both of the addends are negative.

Subtracting with complement notation

So far, we have seen the following equivalences.

The point of all of this: 2's complement

Everything we've just done to represent negative numbers in base 10 using 10's complement can be done just as well in binary, where the same techniques are called 2's complement.