Number System and Representation

Within digital systems, all data, whether characters or numbers, are represented by strings of binary digits. This is fine as long as you never have negative numbers. Unfortunately, this is not normally the case.

Over the years, hardware designers have developed three different schemes for representing negative numbers: sign and magnitude, ones complement, and twos complement. In this section, we will examine these schemes and their implications for addition and subtraction of signed binary numbers.

5.1.1 Representation of Negative Numbers

In mathematics, there are infinitely many positive and negative integers. However, in a practical hardware system only a fixed number of integers can be represented, based on the number of bits allocated to the representation. In most modern computer systems, numbers are represented in 32 bits. This means that over 4 billion unique numbers can be represented-quite a few, but certainly not infinite! An overflow occurs when an arithmetic operation results in a number outside the range of those that can be represented.

Throughout this subsection we will assume that our system operates on 4-bit binary quantities. Thus we can represent 16 unique binary numbers. Roughly half of these will represent positive numbers and zero, while the remainder will be negative numbers. Each of the three representation schemes handles negative numbers slightly differently, as we now examine.

Sign and Magnitude In sign and magnitude systems, the most significant bit represents the number's sign, while the remaining bits represent its absolute value as an unsigned binary magnitude. If the sign bit is a 0, the number is positive. If the sign bit is a 1, the number is negative. We negate a number simply by replacing the sign bit with its complement. Figure 5.1 depicts a "number wheel" representation of our 4-bit number system. The figure shows the binary numbers and their decimal integer equivalents, assuming that the numbers are interpreted as sign and magnitude. The largest positive number we can represent in three data bits is +7 = 23 - 1. By a similar calculation, the smallest negative number is -7. Zero has two different representations, even though +0 and -0 don't make much sense mathematically.

Adding two positive or two negative numbers is straightforward. We simply perform the addition and assign the result the same sign as the original operands. When the signs of the two operands are not the same, addition becomes more complex. In this case, we should subtract the smaller magnitude from the larger. The resulting sign is the same as that of the number with the larger magnitude.

This is what makes arithmetic operations with sign and magnitude numbers so cumbersome-any adder circuit must also include a subtractor and a comparator. Because of this burdensome complexity, hardware designers have proposed other schemes for representing negative -numbers.

Ones Complement Numbers A ones complement approach represents the positive numbers just as in the sign and magnitude system. The only difference is in how it represents negative numbers.

We use the following procedure to derive a negative ones complement integer, denoted , from a positive integer, denoted N. If the word length is n bits (n = 4 in our case), then = (2n - 1) - N. For example, in a 4-bit system, +7 is represented as 0111. We compute -7 as

This rather complicated method is just one way to compute the negative of a ones complement number. A simpler method forms the ones complement by taking the number's bitwise complement. Thus, +7 = 0111 and -7 = 1000, +4 = 0100 and -4 = 1011, and so on.
The number wheel representation of the 4-bit ones complement number system is shown in Figure 5.2.
All negative numbers have a 1 in their sign bit, making it easy to distinguish between positive and negative numbers. Note that we still have two different representations of zero.
The advantage of ones complement numbers is the ease with which we can compute negative numbers. Subtraction is implemented by a combination of addition and negation: A - B = A + (-B). Thus, we don't need a separate subtractor circuit. However, addition is still complicated by the two zeros, and that leads us to twos complement numbers.
Twos Complement Numbers The twos complement scheme is similar to ones complement, except that there is only one representation for zero.
Figure 5.3 shows how the twos complement numbers are derived from the ones complement representation. We've taken the negative numbers and shifted them one position in the clockwise direction. This allows us to represent one more negative number, -8, than we were able to represent in ones complement. The negative numbers still have a 1 in their highest-order bit, the sign bit.

More formally, a twos complement negative number, denoted is derived from its positive number, N, by the equation = 2n - N, where n is the number of bits in the representation. This equation omits the ones complement step that subtracts 1 from 2n.

Let's compute the twos complement of +7, represented as 01112:

Note that the calculation works equally well in deriving the twos complement of -7:

It should come as no surprise that the same shortcut we used to find ones complement numbers also applies for the twos complement system, but with a twist. The number wheel suggests the scheme. Simply form the bitwise complement of the number and then add one to form its twos complement. For example, +7 = 01112, its bitwise complement is 10002, plus 1 is 10012. This is the same twos complement representation of -7 we derived by the last calculation. For the number -4, represented as 11002, its bitwise complement is 00112, plus 1 is 01002. This is exactly the twos complement representation of +4.

As with ones complement, twos complement allows subtraction to be implemented with addition and negation. Even though it is a little harder to compute the twos complement, this is the form used almost universally in today's digital systems. In the next subsection, we will see how easily we can compute addition and subtraction by using twos complement numbers.

5.1.2 Addition and Subtraction of Numbers

In this section, we will examine how addition and subtraction are performed in the three different number systems.

Sign and Magnitude Calculations Continuing with our 4-bit number scheme, let's look at some examples of addition and subtraction with sign and magnitude numbers. We need only consider addition, because subtraction is implemented by adding the negative of the subtracted number. Here are some examples adding and subtracting 3 and 4:

Examples (a) and (b) are cases in which the signs are the same. The result is simply the sum of the magnitudes, and the sign of the result is the same as the signs of the operands.

Examples (c) and (d) represent the more complex situations in which the signs of the two operands differ. In (c), we have converted 4 - 3 to 4 + (-3). The smaller magnitude, 3, is subtracted from the larger magnitude, 4, to obtain the magnitude of the result, 1. Since 4 is greater than 3, its sign is given to the result. This makes the result +1.

Case (d) looks at the operation (-4) + 3. The subtraction of the smaller magnitude from the larger yields a result of 1. The larger magnitude is negative, so the result must also be negative.

Sign and magnitude calculations are complicated because we need both an adder and a subtractor even to implement addition. The adder is used when the signs are the same, the subtractor when they differ. Subtraction is just as complicated.
Ones Complement Calculations Let's repeat the examples with ones complement arithmetic:

Adding two positive numbers, case (e), gives the same result as before. This should not be too surprising, since positive numbers are represented in the same fashion in all three systems.

Example (f) introduces one considerable difference between sign and magnitude addition and ones complement addition: the concept of end-around carry. In ones complement, -4 is represented as 10112 and -3 as 11002. When we add these two numbers, we get a carry-out of the high-order bit position. Whenever this occurs, we must add the carry bit to the result of the sum. 10112 + 11002 yields 1 01112. When the carry-out is added to the 4-bit result, we get 01112 + 1 = 10002. This is the representation of -7 in ones complement.

The end-around carry also happens in example (g). The sum of 4 (01002) and -3 (11002) yields 1 00002. Adding in the carry gives 00012, the ones complement representation of 1.

The last example, (h), obtains the sum 11102. This is precisely the ones complement representation of -1.

Why does the end-around carry scheme work? Intuitively, the carry-out of 1 means that the resulting addition advances through the origin of the number wheel. In effect, we need to advance the result by 1 to avoid counting zero twice.

More formally, the operation of the end-around carry is the equivalent of subtracting 2n and adding 1. Consider the case in which we compute the sum M + (-N) where M > N:

This is exactly the situation of example (g). The end-around carry subtracts off 2n and adds 1, yielding the desired result of M - N.

Now consider the case shown in the second example. The sum to be formed is -M + -N, where M + N is less than 2n - 1. This results in the following sequence of equations:

After the end-around carry, the result of the sum becomes . This is the correct form for representing -(M + N) in ones complement form.
Twos Complement Calculations Twos complement calculations behave very much like the ones complement method, but without the end-around carry. Let's revisit the four examples:

Subtraction is handled as before: we negate the operand and perform addition. Carry-outs can still occur, but in twos complement arithmetic we ignore them.

Example (i), summing two positive numbers, is identical to the two previous representation schemes. Summing two negative numbers is also straightforward. We simply perform binary addition, ignoring any carry-outs. Since we no longer have two representations for zero, there is no need to worry about correcting the summation. Mixed addition of positive and negative numbers is handled exactly like the other cases.

Why is it all right to ignore the carry-out? The same kind of analysis we used in the ones complement case can be applied here. Consider the sum -M + N when N > M. This can be rewritten as
Ignoring the carry-out is equivalent to subtracting 2n. Doing this to the foregoing expression yields the result N - M, which is exactly what we desire. Consider another case: -M + -N where M + N is less than or equal to 2n - 1. This can be rewritten as

By subtracting 2n, the resulting form is exactly the representation of the desired twos complement representation of -(M + N).
The trade-off between twos complement and ones complement arithmetic should now be a little clearer. In the twos complement case, addition is simple but negation is more complex. For the ones complement system, it is easy to perform negation but addition becomes more complicated. Because twos complement only has one representation for zero, it is preferred for most digital systems.

5.1.3 Overflow Conditions

Overflow occurs whenever the sum of two positive numbers yields a negative result or when two negative numbers are summed and the result is positive. We can use the number wheel to illustrate overflow. Think of addition as moving clockwise around the number wheel. Subtraction moves counterclockwise. Using the twos complement number representation, we can divide the number wheel into two halves, one representing positive numbers (and zero), the other representing the negative numbers. Whenever addition or subtraction crosses the positive/negative line, an overflow has occurred. This concept is illustrated in Figure 5.4, with the two example calculations 5 + 3 and -7 - 2. On the number wheel, starting with the representation for +5, we advance three numbers in the clockwise direction. This yields -8; an overflow has occurred. Similarly for subtraction. Starting with the representation for -7, we move two numbers in the counterclockwise direction, obtaining the representation for +7. Once again, we have an overflow.
There is another way to detect when overflow has taken place. Let's look at the detailed calculations:

The carry-ins are shown at the top of each column of bits. In the first calculation, 5 + 3, the carry-in to the high-order bit is 1 while the carry-out is 0. In the second calculation, -7 + -2, once again the carry-in to the final bit is different from the carry-out. In two cases in which overflow does not occur, 5 + 2 and -3 + -5, the carry-in and the carry-out of the final stage are identical.

In general, overflow occurs when the carry-in and carry-out of the sign bit are different.