22C:18, Lecture 3, Fall 1996

Douglas W. Jones
University of Iowa Department of Computer Science

Just about every introduction to assembly language or machine language programming ever written begins with a section like this. The IBM 7040/7044 Data Processing System Student Text (IBM, 1963) begins with with a chapter on this subject that is entirely up to date on this subject, and the Introduction to Programming for the PDP-8 (DEC, 1973) has a nice "Number System Primer" that covers this ground.

Arithmetic

Recall that the value of a simple binary number, represented as a string S of digit symbols, is defined as:

                i=digits(S)-1           i
     value(S) =      SUM     v(S[i]) × 2        (radix r)
                     i=0
This is the same place-value system we use for the decimal number system, except that instead of the 1's, 10's and 100's places, we have the 1's, 2's and 4's places.

It should not be surprising, then, that binary arithmetic strongly resembles decimal arithmetic. To add two decimal numbers, for example, to add 132 to 39, we arrange the numbers as follows:

    1 3 2  augend
   +  3 9  addend
  --------
And then do the addition one pair of digits at a time, starting with 2+9. To add one pair of digits, we use an addition table that most of us should have memorized in elementary school:
 +   0  1  2  3  4  5  6  7  8  9
   +-----------------------------
 0 | 0  1  2  3  4  5  6  7  8  9
 1 | 1  2  3  4  5  6  7  8  9 10
 2 | 2  3  4  5  6  7  8  9 10 11
 3 | 3  4  5  6  7  8  9 10 11 12
 4 | 4  5  6  7  8  9 10 11 12 13
 5 | 5  6  7  8  9 10 11 12 13 14
 6 | 6  7  8  9 10 11 12 13 14 15
 7 | 7  8  9 10 11 12 13 14 15 16
 8 | 8  9 10 11 12 13 14 15 16 17
 9 | 9 10 11 12 13 14 15 16 17 18
   |10 11 12 13 14 15 16 17 18 19 (see notes)
For the example, looking up 2+9 in the table gives a sum of 11; we split this sum into two pieces, the sum digit and the carry digit, writing the result as follows:
      1    carry
    1 3 2  addend
   +  3 9  augend
  --------
        1  sum
In adding up the digits in the next column, we face a small problem: There are three numbers in this column, but our addition table only allows for the addition of two digits. There are many ways to solve this problem. One is to use the same addition table, with the augend as the column index and the addend as the row index, but use the row below the indexed row. Adding the carry to the addend before using the table or adding the carry to the table entry both produce the same result. Doing this to solves the 1+3+3 problem gives 7, so we write this into our work:
      1    carry
    1 3 2  addend
   +  3 9  augend
  --------
      7 1  sum
Finally, we solve the trivial problem of the most significant digits of the addend where there were no carries by simply copying them down, giving a sum of 171.

Binary Addition

Binary addition can be done using exactly the same approach as was described above, but substituting the following table for the addition table:

 +   0  1
   +-----
 0 | 0  1
 1 | 1 10
   |10 11
If this seems too simple, it is because it really is simple! All the rules are the same as for decimal arithmetic because the place-value system is the same system. The only change is a reduction in the number of values each digit can take on, and this means that remembering things like the addition and multiplication tables is far easier in binary than in decimal. The penalty we pay is that, in any arithmetic problem, we have more digits to deal with. To represent quantities that would be comfortably represented in 1 decimal digit, it takes 4 binary digits. To represent a 3 decimal digit quantity takes 10 binary digits. Converting decimal to binary, adding the binary numbers using the above rules, and converting the binary sum back to decimal gives:
  1               1
   0 1             2 6 3 1
    0 0 1  place    8 4 2 6 8 4 2 1
      1    carry            1
    1 3 2  addend   1 0 0 0 0 1 0 0
   +  3 9  augend  +    1 0 0 1 1 1
  --------        ------------------
           sum      1 0 1 0 1 0 1 1    = 171 !
Not surprisingly, the sum is the same.

If there is a limit on the number of bits allowed, as on a computer with a fixed word size, we say that an overflow has occurred if the carry out of the topmost bit of our fixed size word is nonzero. Note that this applies to words used to hold unsigned data, and that the conventions for detecting overflow are more complex if we are interested in also representing negative numbers.

Fast Binary/Decimal Conversion

To convert binary to decimal using pencil and paper, just write the place values over each bit position, in decimal, and then add up the place values over the 1 bits in the number. For example:

                            2
       1                   128
        2 6 3 1             32
         8 4 2 6 8 4 2 1     8
                             2
         1 0 1 0 1 0 1 1  +  1
                         ------
                           171
To convert decimal to binary using pencil and paper, divide the number by two repeatedly, discarding any fractional parts, until you reach 1, writing your numbers in a column. To convert 171 to binary, for example, this gives:
   171
    85
    42
    21
    10
     5
     2
     1
Then, write a 1 next to each odd number and a 0 next to each even number. These 1s and 0s are the remainders after division by the target radix, and they make up the successive digits of the result, in that radix:
   171  1
    85  1
    42  0
    21  1
    10  0
     5  1
     2  0
     1  1
The least significant bit of the binary number is the topmost number in the stack, so, written normally, the result is 10101011.

Negative Numbers

Subtraction in binary is as easy as subtraction in decimal. Borrowing follows the same rules in binary and decimal, but binary subtraction involves more digits and far simpler details at each digit. Subtraction, however, introduces the problem of negative numbers, and these are not usually represented in computers in the same way that we usually represent them on paper!

Consider the problem of representing positive and negative numbers using 4 bits for each number. One way to do this is to follow our intuition from the world of pencil and paper and simply reserve one bit to represent the sign. In this case, we can think of the sign bit as taking on the values + and -, while the 3 magnitude bits take on the values 0 and 1 and follow a place-value system of interpretation. This allows the representation of the following 16 values:

4-bit Signed Magnitude Numbers

 0 0 0 0  +0
 0 0 0 1  +1
 0 0 1 0  +2
 0 0 1 1  +3
 0 1 0 0  +4
 0 1 0 1  +5
 0 1 1 0  +6
 0 1 1 1  +7
 1 0 0 0  -0
 1 0 0 1  -1
 1 0 1 0  -2
 1 0 1 1  -3
 1 1 0 0  -4
 1 1 0 1  -5
 1 1 1 0  -6
 1 1 1 1  -7
This number system works, an in the sense that representation systems are, ultimately, arbitrary, it is as good as any, and many early binary computers used the signed magnitude number system. It turns out, however, that it is easier to build arithmetic hardware for other systems of signed numbers, so this system is not commonly used for integer arithmetic on modern computers.

Signed magnitude numbers also pose minor problems because there are two values for zero, one positive and one negative, but it turns out that all systems of signed numbers either have this problem or a related problem at the extreme negative end of their number range.

4-bit One's Complement Numbers

 0 0 0 0  +0
 0 0 0 1  +1
 0 0 1 0  +2
 0 0 1 1  +3
 0 1 0 0  +4
 0 1 0 1  +5
 0 1 1 0  +6
 0 1 1 1  +7
 1 0 0 0  -7
 1 0 0 1  -6
 1 0 1 0  -5
 1 0 1 1  -4
 1 1 0 0  -3
 1 1 0 1  -2
 1 1 1 0  -1
 1 1 1 1  -0
The one's complement number system, illustrated above, has a number of useful properties. To negate a signed magnitude number, the sign bit in that number was inverted. To negate a one's complement number, all bits in the number are inverted. This is the source of the name for this number system.

In a signed magnitude system, to add two numbers, if the signs are the same, just add the magnitudes. If the signs are different, subtract the smaller magnitude from the larger magnitude and set the sign of the result to the sign of the larger magnitude. In contrast, the rules for adding two one's complement numbers are simple. Treat the "sign" bit as a magnitude bit and add the numbers. Then, if this sum produces a carry out of the topmost bit, add one to the result.

This rule for addition is so simple that, when building computer hardware to do signed magnitude arithmetic, subtraction is always done by adding the one's complement of the number to be subtracted.

Warning: Many students get confused by the use of the term one's complement to mean both the name of the number system and the name of the operator used to negate numbers in that system! If someone says: "Take the one's complement of x," or "one's complement x" that means to apply the operator; the number of bits in the result will be the same as the number of bits in x. If someone says: "write x as a 4-bit one's complement number," that means to use the number system.

4-bit Two's Complement Numbers

 0 0 0 0   0
 0 0 0 1  +1
 0 0 1 0  +2
 0 0 1 1  +3
 0 1 0 0  +4
 0 1 0 1  +5
 0 1 1 0  +6
 0 1 1 1  +7
 1 0 0 0  -8
 1 0 0 1  -7
 1 0 1 0  -6
 1 0 1 1  -5
 1 1 0 0  -4
 1 1 0 1  -3
 1 1 1 0  -2
 1 1 1 1  -1
The two's complement number system has emerged as the most widely used system for representing signed numbers on computers. Few new computers architectures have been introduced since 1960 that used any other system for integers, and few machines built after 1970 use any other system for integers.

Initially, the two's complement number system seems a bit odd. Negative numbers are still indicated by a sign bit, but positive numbers are not related to their negative counterparts in the trivial way that they are related with the one's complement and signed magnitude systems.

The first advantage to this number system that a typical observer might notice is that there is only one zero, but this advantage is offset by the presence of -8 in the 4-bit example shown above. The presence of a number that cannot be negated is clearly as annoying as the presence of two representations of zero. Another advantage which may appear on more detailed inspection is that all numbers that are evenly divisible by 2 end in 0, all numbers evenly divisible by 4 end in 00, and so on. This is, indeed, useful!

To negate a number in the two's complement system, we apply the two's complement operator. This is the composite of the one's complement operator and adding 1. So, to negate 0000, we make 1111 first, then add 1, giving 0000 (the carry out of the top bit was discarded).

The fundamental reason for the popularity of two's complement numbers is that arithmetic is trivial. To add two two's complement numbers, just treat all bits, even the "sign bit", as magnitude bits and add them using simple binary addition.

To subtract two two's complement numbers, one's complment the number to be subtracted, then add, but also put a carry in to the least significant bit position. Using C notation, where - is the two's complement operator and ~ is the one's complement operator, the following are equivalent:

	A - B
	A + -B
	A + ~B + 1
Note that this approach to subtraction, a carry of one into any bit position means, in essence, don't borrow from this position. This seems an odd way of handling borrows, but it works.

Warning: Many students get confused by the use of the term two's complement to mean both the name of the number system and the name of the operator used to negate numbers in that system! If someone says: "Take the two's complement of x," or "two's complement x" that means to apply the operator; the number of bits in the result will be the same as the number of bits in x. If someone says: "write x as a 4-bit two's complement number," that means to use the number system.

The two's complement number system turns out to be a strange place value system, in which the "sign bit" has a value that is negative. Thus, in addition to the obvious ways of converting two's complement numbers to decimal (if negative, write down a minus sign, then two's complement it and convert the positive number to decimal), we can do the conversion using the sum of the place values. For the 4 bit two's complement system, the place values are:

     _ _ _ _
    |_|_|_|_|
    -8 4 2 1

When adding two two's complement numbers, overflow detection is not as simple as looking for a carry out of some bit position. If the two numbers being added were of opposite sign, the sum must lie between them, and overflow is impossible. If the numbers being added were of the same sign, overflow is possible, and if it occurs, the sign of the result will differ from the sign of the two numbers being added. Alternately, this turns out to be equivalent to asking if the carry into the sign position is the same as the carry out of the sign position -- in adding negative numbers, there should always be a carry both into and out of the sign, and in adding positive numbers, there should never be a carry in or carry out of the sign.

4-bit Biased Numbers

 0 0 0 0  -8
 0 0 0 1  -7
 0 0 1 0  -6
 0 0 1 1  -5
 0 1 0 0  -4
 0 1 0 1  -3
 0 1 1 0  -2
 0 1 1 1  -1
 1 0 0 0   0
 1 0 0 1  +1
 1 0 1 0  +2
 1 0 1 1  +3
 1 1 0 0  +4
 1 1 0 1  +5
 1 1 1 0  +6
 1 1 1 1  +7
Biased number systems seem like oddities, but they are used in such places as floating point numbers, where they are commonly used to represent the exponent field. Biased numbers have the obvious advantage that the number values are in simple binary order, with 0000 representing the smallest value, and 1111 representing the largest. To convert from our signed-magnitude decimal system to the biased system, add the bias (8 for the 4-bit system) to the number to be converted, then convert that sum to simple binary.

Biased numbers are negative if the "sign bit" is 0, and positive if the sign bit is 1; they have a trivial relationship to two's complement numbers. To convert a biased number to the equivalent two's complement number, just flip the sign bit!