 Home www.play-hookey.com Sat, 05-15-2021

Negative Numbers and Binary Subtraction

We have seen how simple logic gates can perform the process of binary addition. It is only logical to assume that a similar circuit could perform binary subtraction.

If we look at the possibilites involved in subtracting one 1-bit number from another, we can quickly see that three of the four possible combinations are easy and straight-forward. The fourth one involves a bit more:

```    0 - 0 = 0
1 - 0 = 1
1 - 1 = 0
0 - 1 = 1, with a borrow bit.
```

That borrow bit is just like a borrow in decimal subtraction: it subtracts from the next higher order of magnitude in the overall number. Let's see what the truth table looks like.

INPUTS OUTPUTS A B This is an interesting result. The difference, A-B, is still an Exclusive-OR function, just as the sum was for addition. The borrow is still an AND function, but is A'B instead of AB. What we'd like to do, now, is find an easy way to use the binary adder to perform subtraction as well. We already have half of it working: the difference output. Can we simply invert the A input so the AND gate will have the right signals? No, we can't, because that would invert the sense of the Exclusive-OR function. What would be really nice is to convert B to the negative equivalent of its value, and then use the basic adder just as it stands. To see if we can do that, let's consider negative binary numbers below. 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0

 Binary Unsigned Signed Decimal Decimal As we can see if we look at binary counters, once a full count is obtained, the next clock pulse will cause the counter to read zero again. Likewise if we set up a counter to count backwards, the first clock pulse will cause the count to go from all zeroes to all ones. Thinking along these lines, we can see that the binary number 1111 might represent the decimal number 15, or it could represent the number -1. On the right is the counting sequence for a 4-bit binary number, with decimal equivalents expressed in two ways. First we have the unsigned counting sequence, where all numbers are assumed to be positive. Then we see the signed sequence, which includes both positive and negative numbers. Looking at the two decimal counting sequences, we note two factors right away: The positive signed numbers are the same as their unsigned counterparts. Negative signed numbers all correspond to the most significant bit of the binary number being a logic 1. Because positive numbers are the same in both sequences, they can be used together without difficulty. We only need to keep track of how we want to define the system. And the fact that negative numbers all have the binary MSB = 1 is helpful because the MSB can immediately be used to identify the sign of the number. Indeed, the binary MSB is commonly known as the sign bit. The use of this bit to distinguish between positive and negative numbers also allows us to divide the counting sequence evenly between positive and negative numbers. Now we need to look at the relationship between the binary numbers for positive and negative versions of the same magnitude. Suppose we invert each bit of 0001 (+1) to get 1110 (-2). If we then increment the result, we get 1111 (-1), which is what we wanted. Will this relationship hold for all negative numbers? In fact, it does work, as you can determine for yourself. To form the negative of any number, first complement all bits of the number. The result is the one's complement of the original number. Then, add 1 to the result, thus forming the two's complement of the original number. Arithmetic involving such signed numbers is known generally as two's complement arithmetic. To check the validity of this process, let's take the two's complement of 0. We should logically get a result of 0. So, we start with 0000, and form the one's complement (1111). Now add 1 to the result (10000). But this won't fit in a 4-bit number, so the extra 1-bit is lost, leaving a result of (0000). Sure enough, -0 = 0, as it should. Remember to discard the carry from the highest-order bit. Two's complement arithmetic always works this way. Note: It is not possible to represent +8 as a 4-bit signed number. Therefore it is not possible to correctly take the two's complement of -8. It will come back again as -8. 0000 0 0 0001 1 1 0010 2 2 0011 3 3 0100 4 4 0101 5 5 0110 6 6 0111 7 7 1000 8 -8 1001 9 -7 1010 10 -6 1011 11 -5 1100 12 -4 1101 13 -3 1110 14 -2 1111 15 -1 Now that we have an easy way to obtain the negative of any number, we can convert our original 4-bit adder circuit to an adder/subtractor. By leaving the inputs unchanged, we get the result of A + B. But if we invert B and add 1 with the low-order Cin, we get the result of A - B.

We can use Exclusive-OR gates, as shown to the right, to control whether we will add or subtract on any given occasion. With a control input of 0, the XOR gates will leave the B input number unchanged, and will also apply a logic 0 as the initial input carry. This is exactly what we want in order to add the two numbers. However, if we apply a logic 1 to the control input, the XOR gates will invert the B input number to form its one's complement, and will also add 1 through the initial input carry. This changes B to its two's complement. Thus, the output result will actually be A - B. (Note that in two's complement addition, the output carry is ignored. You can also think of it as an inverted "borrow" bit rather than as a carry, so that a carry of 1 corresponds to a borrow of 0. That logic also holds for the input carry, which also represents an input borrow bit of 0.)

When we add or subtract signed numbers, we need to introduce a new concept: overflow. Overflow occurs when the result has the wrong sign bit for the operation that was performed. For example, if we add two positive numbers (7 and 6), we should get a positive result (13). However, using 4-bit binary numbers, we would add 0111 to 0110 and get 1101 as the result. In signed notation, this is a result of -3, not +13. Therefore, an overflow has occurred, where the result would have to have more bits than the original two numbers.

This is not as much of a problem as you might think. An 8-bit number can have signed values in the range -128 to +127. A 16-bit signed number may hold any value from -32,768 to +32,767. These ranges are sufficient for most practical applications. Where they are not, modern computers can easily use 32-bit numbers (±2.14 × 109) or 64-bit numbers (±9.22 × 1018) for the purpose.

If we add a positive number to a negative number, overflow cannot occur. Likewise, if we are subtracting two numbers of the same sign, overflow is impossible. But if we add like-signed numbers or subtract unlike-signed numbers, we must be aware of the possibility of overflow, and recognize when it occurs.

Modern microprocessors are designed to recognize and report when overflow occurs in any arithmetic operation.

 Prev: Binary Addition Next: Two-Input Multiplexer 