Computer Architecture # 03 : Arithmetic: TWO’S COMPLEMENT ADDITION AND SUBTRACTION (3)

3.2.1 TWO’S COMPLEMENT ADDITION AND SUBTRACTION

In this section, we look at the addition of signed two’s complement numbers. As we explore the addition of signed numbers, we also implicitly cover subtraction as well, as a result of the arithmetic principle:

a - b = a + (−b).

We can negate a number by complementing it (and adding 1, for two’s complement), and so we can perform subtraction by complementing and adding. This results in a savings of hardware because it avoids the need for a hardware subtractor. We will cover this topic in more detail later.  We will need to modify the interpretation that we place on the results of addition when we add two’s complement numbers.

To see why this is the case, consider Figure 3-1. With addition on the real number line, numbers can be as large or as small as desired—the number line goes to ±∞ , so the real number line can accommodate numbers of any size. On the other hand, as discussed in Chapter 2, computers represent data using a finite number of bits, and as a result can only store numbers within a certain range. For example, an examination of Table 2.1 shows that if we restrict the size of a number to, for example, 3 bits, there will only be eight possible two’s complement values that the number can assume. 

In Figure 3-1 these values are arranged in a circle beginning with 000 and proceeding around the circle to 111 and then back to 000. 

 Figure 3-1    Number circle for 3-bit two’s complement numbers.

The figure also shows the decimal equivalents of these same numbers. Some experimentation with the number circle shows that numbers can be added or subtracted by traversing the number circle clockwise for addition and counter clockwise for subtraction. Numbers can also be subtracted by two’s complementing the subtrahend and adding. Notice that overflow can only occur for addition when the operands (“addend” and “augend”) are of the same sign. Furthermore, overflow occurs if a transition is made from +3 to −4 while proceeding around the number circle when adding, or from −4 to +3 while subtracting. (Two’s complement overflow is discussed in more detail later in the chapter.)

Here are two examples of 8-bit two’s complement addition, first using two positive numbers:

A positive and a negative number can be added in a similar manner:

The carry produced by addition at the highest (leftmost) bit position is discarded in two’s complement addition. A similar situation arises with a carry out of the highest bit position when adding two negative numbers:

  

The carry out of the leftmost bit is discarded because the number system is modular —it “wraps around” from the largest positive number to the largest negative number as Figure 3-1 shows. 

Although an addition operation may have a (discarded) carry-out from the MSB, this does not mean that the result is erroneous. The two examples above yield  correct results in spite of the fact that there is a carry-out of the MSB. The next section discusses overflow in two’s complement addition in more detail.

Overflow

When two numbers are added that have large magnitudes and the same sign, an overflow will occur if the result is too large to fit in the number of bits used in the representation. Consider adding (+80)10  and (+50)10  using an eight bit format. The result should be (+130)10, however, as shown below, the result is (−126)10:

This should come as no surprise, since we know that the largest positive 8-bit two’s complement number is +(127)10, and it is therefore impossible to represent (+130)10. Although the result 100000102 “looks” like 13010  if we think of it in unsigned form, the sign bit indicates a negative number in the signed form, which is clearly wrong.

In general, if two numbers of opposite signs are added, then an overflow cannot occur. Intuitively, this is because the magnitude of the result can be no larger than the magnitude of the larger operand. This leads us to the definition of two’s complement overflow: 

If the numbers being added are of the same sign and the result is of the opposite sign, then an overflow occurs and the result is incorrect. If the numbers being added are of opposite signs, then an overflow will never occur. As an alternative method of detecting overflow for addition, an

overflow occurs if and only if the carry into the sign bit differs from the carry out of the sign bit. 

If a positive number is subtracted from a negative number and the result is positive, or if a negative number is subtracted from a positive number and the result is negative, then an overflow occurs. If the numbers being subtracted are of the same sign, then an overflow will never occur.