Negative integers and subtraction

Robert P. Webber, Don Blaheta, Longwood University
Why are we working on this? We know what binary is but have not yet considered how 1s and 0s can help us to represent negative numbers—place-value notation is not enough. When all you have are digits—0 and 1 or 0 through 9—you can still represent negative numbers if you know you'll need them. Skills in this section: Convert negative numbers with written sign to complement notation — Use complement notation to subtract numbers — Interpret result of subtraction in this system Concepts: Data representation, Limitations of representation, Interpretation of computed results, Classic algorithms

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.

The most obvious way to represent negative numbers in a binary notation would thus be a signed binary notation. Just write the absolute value of the number in base two, and affix a negative sign if necessary. For example, 28 and −41 in signed binary are
28 = 16 + 8 + 4 = 111002
−41 = −(32 + 8 + 1) = −1010012
But remembering that our eventual goal is to represent everything with nothing but 0s and 1s, can we represent the minus sign? Sure: for the sign, there are just two possibilities (plus or minus), and so we can very straightforwardly map those two possibilities to 0 and 1 (say, 0 means plus and 1 means minus). If we have eight bits to work with, we use one for the sign and the remaining seven for the digits of the number:
0 0 0 1 1 0 0 0
sign
= +00110002 = 2810
1 0 1 0 1 0 0 1
sign
= −01010012 = −4110
Though it is not standard, we will here use the subscript "2S" to indicate that a bit sequence, normally eight bits, is a complete signed binary representation, including sign bit: 000110002S = +110002, 101010012S = −1010012. While leading zeroes may be omitted when dealing with simple binary notation, formally speaking, signed binary notation requires a fixed number of bits, declared in advance, so leading zeroes should not be omitted when writing signed binary in its 1-and-0-only form (what we're subscripting as "2S").

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: 000000002S is one of them, of course. But consider what 100000002S 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 (103) different values, 000-999. An eight-digit base-2 number can only represent 256 (28) 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 (27) 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.

One of the most standard paper-and-pencil subtraction algorithms involves writing the number being subtracted (the subtrahend, if you want to be picky) underneath the number being subtracted from (the minuend), with the digits lined up in columns. (Why are the digits in columns? Because place-value notation means that digits in the same places are related to the same power of ten.) Consider a simple subtraction, like 743−51:
7 4 3
5 1
We proceed right-to-left, subtracting down the columns. If the top number isn't big enough, we "borrow" from the the digit in the next column:
6 14
7 4 3
5 1
6 9 2
What does "borrowing" really mean here? What are we borrowing? Well, since the place-value system tells us that the next higher column is "worth" ten times as much as this one, decreasing it by 1 should let us increase this one by ten. In the context of this example, 7×100 + 4×10 = 6×100 + 14×10. Performing the explicit borrowing step lets us rearrange the subproblems to be easier, always involving subtracting a one-digit smaller number from a larger number (which might be in the teens, but no larger than that).
Now consider the problem of subtracting 2146 minus 857. Lots of borrowing is necessary.
10 13
1 0 3 16
2 1 4 6
8 5 7
1 2 8 9
The system really does work, but it's kind of a mess: complicated, and fairly error-prone. In practice, for a problem like this we would probably pull out the little computer we carry with us at all times, fire up the calculator app, and get the answer more quickly (and confidently!) that way. We're reminding ourselves of this classic algorithm for two reasons right now: one, to remind ourselves that it does work, and two, to remind ourselves that it's more complicated than addition.
Would this standard subtraction algorithm work on binary numbers? It certainly would, and the only change would be to remember that when we're working in binary, when we write "10" this does not represent the number ten, but rather the number two (because it is now 1×21 + 0×20). Consider 1001102 − 11012 (which is 3810 − 1310):
0 1 10 0 10
1 0 0 1 1 0
1 1 0 1
0 1 1 0 0 1
The result, as we would have hoped, is 110012 (2510). The process is... not very pretty, but it works.

Adding and subtracting negative numbers

At some point when we were first learning about negative numbers, we were presented with problems such as 24175 + −42. They're really not amenable to the traditional addition algorithm:
2 4 1 7 5
+ 4 2
because no amount of borrowing or carrying is going to make this work:
2 4 1 7 5
+ 4 2
? 11 7 ?????
The answer, we were told, was to change it into an equivalent subtraction problem involving only positive numbers:
2 4 1 7 5
4 2
At this point, it is no harder than any standard subtraction. Similarly, presented with an expression like 2473 − −238, our solution was to convert it into 2473 + 238 and proceed as usual. Slightly different sets of rules applied if the negative number had a magnitude larger than the positive number, or if they were both negative, or if the minuend was negative and the subtrahend was positive.

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. [illustration of 3-digit base-10 representation, no offset]
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. [illustration of 3-digit base-10 representation, offset of
        one, bad]
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. [illustration of 3-digit base-10 representation, offset of
        one, good]
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.
And here's a surprising bonus: if you add 1 to −1, you'd like the answer to be zero. If our representation for −1 is
9 9 9
what happens when we add 1 to that? Normally we'd get 1000, but because our representation is limited to three digits, just like an odometer that's run out of digits, we roll over to
0 0 0
That's our representation for zero! So indeed, when we add 1 to (the representation of) −1, the result we get is (the representation of) 0, without having to do any special cases at all.
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. [illustration of 3-digit base-10 representation, offset of
        two]
Figure 4: Including −2 as well
Following on our earlier observation, what would happen if we add 5 to −2? Since our representation of −2 is
9 9 8
we can do normal arithmetic to add 5 to that and get 1003; but because of the odometer-rollover effect, that turns out to be
0 0 3
So adding 5 to −2 gives us 3—again without any special work on our part. Here, a well-chosen data representation is actually giving us algorithmic power. If adding numbers is the sort of thing we might want to do frequently (and it is), then this representation might be particularly useful to us.
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. [illustration of 3-digit base-10 10's complement representation]
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.

We've said that the 10's complement representation of a negative number, like −837, can be computed by subtracting from a power of ten. We could subtract 837 from 1000000 (with all the borrowing that entails) to find its six-digit 10's complement form. But there is a less obvious, but easier, algorithm to compute complement form:
  1. Decide how many digits are required in the representation, and add zeroes on the left of the number to fill out the necessary digits.
  2. "Flip" each digit in the original by subtracting it from 9.
  3. Add 1 to the result.
In our example, we find the six digit 10's complement of 837: We can check our work by confirming that 999163 + 837 = 1000000. When it's important to distinguish, we'll use the (non-standard) subscript "C" to indicate that a number is written in complement notation: 99916310C.

Adding with complement notation

Let's return to our example of adding negative numbers. Before we wrote the negative number using standard signed notation:
2 4 1 7 5
+ 4 2
Now, though, let's try it in our new 10's complement system. What is the six digit 10's complement representation of −42? We can then use that to set up our addition problem:
0 2 4 1 7 5
+ 9 9 9 9 5 8
Remember, 99995810C is just the representation of the same number previously represented as −4210. Because of the rollover effect, we should be able to perform this addition—which includes a negative number—exactly the same as any other addition (just ignoring the rollover, if any). Let's try it:
1 1 1 1 1 1
0 2 4 1 7 5
+ 9 9 9 9 5 8
(1)0 2 4 1 3 3
Here's where it's crucially important to remember that we've set this problem up in a six-digit system: that extra one on the left end is the rollover 1, and should be ignored when reporting the final answer: 24133. You can use a calculator or the traditional subtraction algorithm to verify that this answer is correct: 24175 + −42 = 24133.

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

What can complement notation do for subtraction? Recall our example of a "complicated" subtraction problem, 2146 minus 857, involving a great deal of borrowing.
10 13
1 0 3 16
2 1 4 6
8 5 7
1 2 8 9
Nothing prevents the standard subtraction algorithm from working, but since negative numbers now work just fine with the addition algorithm—which is much simpler—let's try computing this as 2146 + −857 instead.
First, we convert −857 into 10's complement notation: Then, use that in an addition problem:
1 1 1
0 0 2 1 4 6
+ 9 9 9 1 4 3
(1)0 0 1 2 8 9
We ignore the rollover 1 as usual, and straightforwardly interpret 00128910C as 128910, the same answer we got from the subtraction algorithm.
What if the result is negative? Consider the problem 268 − 1830. To follow the process we've set up so far, we rewrite that as 268 + −1830 and set up the addition. First, negate 1830: Then, the addition:
1
0 0 0 2 6 8
+ 9 9 8 1 7 0
9 9 8 4 3 8
The result of the addition is 99843810C.
But it's important to interpret this result. Since it is in complement notation, we can see (because of the leading 9s) that it represents a negative number, and since we were only using complement notation to solve a problem, we need to remember that "998438" is probably not a very helpful answer to the question "What is 268 minus 1830?". To report our answer in a more human-readable form, we should convert it into a signed notation. The negation algorithm for 10's complement is exactly the same whether you are switching from positive to negative or vice versa, so we apply that: This shows that 99843810C is the negation of 00156210C. Thus we can report our final answer, to the original question "what is 268 minus 1830?", as −1562. We can use a calculator or other addition/subtraction algorithms to verify that this is correct.

So far, we have seen the following equivalences.

Signed decimal 10's complement (six digits)
−837 999163
−569 999431
In the 21st century, the main use for 10's complement is as a teaching aid and introduction for 2's complement, which we'll see in a minute. But historically, it had an important use in manual bookkeeping: because the addition algorithm is less error-prone than the subtraction algorithm, and because you can add more than two things at a time, complement notation was sometimes used to store negative numbers (debts or corrections) in the ledger, so the whole column could still be added up and achieve the correct result.

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.

Addition works just the same whether the numbers being added are positive or negative. Subtraction always works by negating the number being subtracted, and then adding (regardless of whether one or the other or both are negative to start with). Negating a number follows the same algorithm as with 10's complement, except that the "flip" step is even easier:
  1. Decide how many bits are required in the representation, and add zeroes on the left of the number to fill out the necessary digits.
  2. Flip each bit in the original.
  3. Add 1 to the result.
Modern computers use 2's complement notation, usually in a 32-bit or 64-bit form, for nearly all situations requiring representation of integers, precisely because of the fact that this data representation lends extra power to the existing algorithms: addition works without modification, and a separate subtraction algorithm doesn't need to be implemented at all (once negation and addition are implemented). In our examples, for convenience, we will normally use an eight-bit 2's complement representation, which can represent numbers from −128 through +127.
What does it look like to find the 2's complement representation of a negative number? Let's try finding the representation of −4510, using an 8-bit form. First, find out what 4510 is in binary:
4510 = 32 + 8 + 4 + 1 = 1011012
We want the negation of that, so: The representation of −4510 is thus 110100112C.
Just as in 10's complement notation, the representation of a positive number is just the usual way of writing the number (but padded with zeroes on the left). Since 0 and 1 are the only possible values for a bit, every positive 2's complement number must begin with 0 (and every negative number begins with 1). So,
Signed decimal Signed binary 2's complement (eight digits)
−45 −101101 or 101011012S 110100112C
45 101101 or 001011012S 001011012C
We can remind ourselves of the "complement" nature of this by looking at the fact that if we add the 2's complement representations of −45 and 45, we would get (1)00000000: the (1) here is the rollover, and 000000002C is just 0.
Because they use 2's complement, computers subtract by negating-then-adding. Consider the task of using 2's complement notation, as a computer does, to evaluate 85 − 38. First, we rewrite the problem:
85 − 38 = 85 + −38
Next, represent 8510 and −3810 using 2's complement (8-bit):
8510 = 64 + 16 + 4 + 1 = 10101012 = 010101012C
−3810 = −(32 + 4 + 2) = −1001102
  • 00100110 (fill out to eight bits)
  • 11011001 (flip each bit)
  • 11011010 (add one)
−3810 = 110110102C
Finally, perform the addition:
1 1 1
0 1 0 1 0 1 0 1
+ 1 1 0 1 1 0 1 0
(1)0 0 1 0 1 1 1 1
And interpret the result: the leftmost 1 (shown here in parentheses) is the rollover digit, so the result 001011112C is positive and equals 1011112 = 32 + 8 + 4 + 2 + 1 = 4710, which is the correct answer.

Exercises

  1. Complete the table. The first two rows were done above.
    Signed decimal 10's complement (six digits)
    −837 999163
    −569 999431
    −12781
    001781
    92
    939216
    −2480
    999980
  2. Complete the table.
    Signed decimal 10's complement (six digits)
    214
    000017
    −4
    999171
    −23417
    899100
    −500000
    231407
  3. Complete the table. The first two rows were done above.
    Signed decimal Signed binary 2's complement (8 bits)
    −45 −101101 11010011
    45 101101 00101101
    100
    −1100001
    00011001
    1100
    11000011
    −66
    0
    1
    −1
  4. Complete the table.
    Signed decimal Signed binary 2's complement (8 bits)
    −1101100
    17
    01101100
    100001
    −58
    10001001

    In problems 5 through 12, do the decimal subtraction by using six-digit 10's complements, not by the standard subtraction algorithm and borrowing. Interpret the answers—your final result should be in signed decimal notation.

  5. 37 − 12
  6. 37 − 18

  7. 37 − 37
  8. 37 − 62

  9. 37 − 78
  10. 4285 − 1277

  11. 462 − 498
  12. 805 − 1486

    In problems 13 through 18, do the binary subtraction by using 2's complements. You may leave your final answer in (signed) binary, but you should interpret the result (remove the rollover digit (if any) and leading zeroes, and identify and convert negative numbers).

  13. 101 − 11
  14. 1011 − 10
  15. 1110 − 111
  16. 1001 − 1100
  17. 101 − 1101
  18. 11011011 − 1101101

    Will subtraction by adding the complement work if the first term is negative? In problems 19 through 22, do the arithmetic using six-digit 10's complements for all negative numbers, and check your answers using ordinary arithmetic.

  19. −44 − 21
  20. −108 − 97
  21. −16 − 95
  22. −16 − 209

    In problems 23 and 24, the problems are presented as subtraction of decimal numbers; perform the entire computation, start to finish, using 2's complement arithmetic. This will require translating the numbers into 2's complement notation, performing the appropriate arithmetic operation(s), and interpreting the result back into a decimal form.

  23. 68 − 22
  24. 97 − 35
  25. What is the largest positive base 10 number that can be stored in 2's complement using 8 bits? What is the smallest negative number? Hint: Think about the bit patterns in base 2 and translate back to decimal.

  26. What is the largest positive base 10 number that can be stored in 2's complement using 16 bits? What is the smallest negative number?

  27. One of the sections above was titled "Two birds with one stone". The stone was complement notation. What were the two birds?
  28. The three-step algorithm for computing a negation in 10's complement notation is described as "less obvious, but easier" than subtracting a number from a power of ten. Why does the algorithm work? Show why we can be sure that the three-step algorithm is correct.

Credits and licensing

This article is by Robert P. Webber and Don Blaheta, licensed under a Creative Commons BY-SA 3.0 license.

Version 2017-Jan-17 04:30