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 NumbersIn 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
). 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.
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 NumbersIn 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.
)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.
)represent the more complex situations in which the signs of the two operands differ. In
), we have converted 4 - 3 to 4 +
). 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.
)looks at the operation
)+ 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.
), 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.
)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
). The sum of 4
)yields 1 00002. Adding in the carry gives 00012, the ones complement representation of 1.
The last example,
), 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 +
)where M > N:
). 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.
), 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
(M + N
5.1.3 Overflow ConditionsOverflow 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
), 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.