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:

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.

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.

We use the following procedure to derive a negative ones complement integer, denoted , from a positive integer, denoted

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:

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,

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.

Here are some examples adding and subtracting 3 and
4:

Examples

Examples

Case

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.

Adding two positive numbers, case

Example

The end-around carry also happens in example

The last example,

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

This is exactly the situation of example

Now consider the case shown in the second example. The sum to be formed is -

After the end-around carry, the result of the sum becomes
. This is the correct form for representing -

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

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 -

Ignoring the carry-out is equivalent to subtracting
2n. Doing this to the foregoing expression yields the result

By subtracting 2n, the resulting form is exactly the
representation of the desired twos complement representation
of -

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.

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.

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.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*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.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:

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.`(`

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:`(`

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:*`(`

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:`(`

*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: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*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`(`

*M*+*N*`)`

.
### 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.
In general, overflow occurs when the carry-in and carry-out of the sign bit are different.

## No comments:

## Post a Comment