Binary Subtraction

From Digital Logic Wiki
Jump to: navigation, search

Contents

Simple Manual Subtraction

Subtracting binary numbers is similar to subtracting decimal numbers and uses the same process children learn in elementary school. The minuend and subtrahend are aligned on the radix point, and then columns are subtracted one at a time, starting with the least significant place and moving to the left. If the subtrahend is larger than the minuend for any one column, an amount is "borrowed" from the column to the immediate left. It may help to review the process with a simple example:

  54.3
26.2
  28.1

In the above problem, 6 cannot be subtracted from 4, so 10 was borrowed from the 5, making the problem more like this:

  54 14.3
 2  6.2
   2  8.1

Thus, 54.3 - 26.2 = 28.1

Binary numbers can also be subtracted in the same way, but it is important to keep in mind that binary numbers have only two possible values: 0 and 1. Consider the following problem:

  10.1
01.0
  01.1

In this problem, the least significant column is 1 - 0, and that equals 0. The middle column, though, is 0 - 1, and that cannot be done. Therefore, one is borrowed from the most significant bit column, making the problem in middle column to become 10 - 1. (Note: do not think of this as "ten minus one" - remember that this is binary so this problem is "one-zero minus one.") The middle column is 10 - 1 = 1. That makes the most significant column 0 - 0 = 0.

The radix point must be kept in alignment throughout the problem, so if one of the two operands have too few places, it should be padded on both the left and right to make both operands the same length. As an example, subtract: 101101.01 - 1110.1:

  101101.01
001110.10
   11110.11

There is no difference between decimal and binary as far as the subtraction process is concerned. In each of the problems in this section the minuend is greater than the subtrahend, leading to a positive difference; however, if the minuend is less than the subtrahend, the result is a negative number; and negative numbers are developed in the next section of this page.

Here are some subtraction problems for practice:

Subtraction Problems
Minuend Subtrahend Difference
1001011 0111010 10001
100010 010010 10000
101110110 11001010 10101100
1110101 111010 111011
11011010.1101 101101.1 10101101.0101
10101101.1 1101101.101 111111.111

Representing Negative Binary Numbers Using Sign-and-Magnitude

Binary numbers, like decimal numbers, can be both positive and negative. While there are several methods of representing negative binary numbers; one of the simplest is using "sign-and-magnitude," which is essentially the same as placing a "–" in front of a decimal number. With the sign-and-magnitude system, the circuit designer simply designates the most significant bit as the "sign bit" and all others as the magnitude of the number. When the sign bit is 1 the number is negative, and when it is 0 the number is positive. Thus, decimal -5 would be written as 1101 in binary.

Unfortunately, despite the simplicity of the sign-and-magnitude approach, it is not very practical for arithmetic purposes. For instance, negative five (1101) cannot be added to any other binary number using standard addition technique since the sign bit would interfere. Errors can easily occur when bits are used for any purpose other than standard place-weighted values; for example, 1101 could be misinterpreted as the number 13 when in fact it is meant to represent -5. To keep things straight, the circuit designer must first decide how many bits are going to be used to represent the largest numbers in the circuit, and then be sure to not exceed that bit field length in arithmetic operations. For the above example, four bits would limit arithmetic operations to the representation of numbers from negative seven (1111) to positive seven (0111), and no more.

This system also has the quaint property of having two values for zero. If using three magnitude bits, these two numbers are both zero: 0000 (positive zero) and 1000 (negative zero).

This system for representing negative numbers was used in early computers, but it required more logic gates (thus, electronic circuitry) than other systems. As a consequence, it was not widely adopted.

Representing Negative Binary Numbers Using Signed Complements

About Complementation

Before discussing negative binary numbers, it is important to understand the concept of complementation. The radix (or base) of any number system is the number of ciphers available for counting; the decimal (or base-10) number system has ten ciphers (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) while the binary (or base-two) number system has two ciphers (0, 1). By definition, a number plus its complement would equal the radix. Thus, when using decimal numbers, the complement of 8 is 2 since 8 + 2 is 10, which is the radix of the decimal system.

It turns out that the radix complement is not as useful in mathematics as the diminished radix. By definition, a number plus its diminished complement is equal to (radix - 1). As an example, the diminished radix for decimal 538, in expanded decimal notation is:

((9 - 5) X 102) + ((9 - 3) X 101) + ((9 - 8) X 100)

Or 461.

Since the radix for a binary number is 102, the diminished radix is obtained by subtracting each digit in a binary number from 1. In essence, that means the diminished radix is obtained by simply reversing (or "flipping") each bit in a binary number; so the diminished radix complement of 100101 is 011010.

The radix complement of a binary number is found by adding one to the diminished radix complement. The diminished radix complement for 1011012 is 0100102, then the radix complement is 0100102 + 12, or 0100112. In binary mathematics, the diminished radix complement is usually called the "ones complement" because it is found by subtracting each bit from 1 and the radix complement is usually called the "twos complement" because it is found by subtracting each bit from two (if there were such a number).

Negative Binary Numbers

In circuits that use binary mathematics, a circuit designer can opt to use ones complement for negative numbers and designate the most significant bit as the sign bit; and, if so, the other bits are the magnitude of the number. With ones complement negative numbers, if the most significant bit is 0, then the number is positive and the magnitude of the number is determined by the remaining bits; but if the most significant bit is 1, then the number is negative and the magnitude of the number is determined by taking the ones complement of the number. Thus: 0111 = +7, and 1000 = -7 (ones complement for 1000 is 0111). The following table may help to clarify this concept:

Ones Complement
Decimal Positive Negative
0 0000 1111
1 0001 1110
2 0010 1101
3 0011 1100
4 0100 1011
5 0101 1010
6 0110 1001
7 0111 1000

In a four-bit binary number, any decimal number from -7 to +7 can be represented; but, notice that, like the sign-and-magnitude system, there are two values for 0, one positive and one negative. This requires extra circuitry to test for both values of zero after operations like subtraction.

A circuit designer can also opt to use twos complement negative numbers and designate the most significant bit as the sign bit; and, if so, the other bits are the magnitude of the number. To use twos complement numbers, if the most significant bit is 0, then the number is positive and the magnitude of the number is determined by the remaining bits; but if the most significant bit is 1, then the number is negative and the magnitude of the number is determined by taking the ones complement of each of the bits and then adding one. Thus: 0111 = 7, and 1001 = -7 (ones complement of 1001 is 0110, and 0110 + 1 is 0111). The following table may help to clarify this concept:

Twos Complement
Decimal Positive Negative
0 0000 10000
1 0001 1111
2 0010 1110
3 0011 1101
4 0100 1100
5 0101 1011
6 0110 1010
7 0111 1001

The twos complement removes that quirk of having two values for zero. The table above shows that zero is either 0000 or 10000; but since this is assumed to be a 4-bit circuit, that initial "1" is discarded, leaving 0000 for zero whether the number is positive or negative.

Since A - B is the same as A + (-B) it is easy to design a circuit that subtracts by adding. Doing that saves the designer a lot of effort and makes the final circuit simpler since binary adders are very common and easy to built. In modern electronic circuits, subtracting is normally done by finding the complement of the subtrahend and then adding that number to the minuend.

About Calculating the Twos Complement

In the above section, the twos (or radix) complement is calculated by finding the ones complement of a number and then adding one. For machines, this is the most efficient method of calculating the twos complement; but there is a method that is much easier for humans to use to calculate the twos complement of a number.

For a human to find the twos complement of a number, start with the least significant bit (the right-most bit) and then read the number from right to left. Look for the first “1,” and then invert every bit to the left of that “1.” As an example, the twos-complement for 101010 is formed by starting with the least significant bit (the 0 on the right), and working to the left, looking for the first 1, which is in the second place from the right. Then, every bit to the left is inverted, ending with: 010110.

Here are some examples:

Twos Complement Numbers
Number Twos Complement
0110100 1001100
11010 00110
001010 110110
1001011 0110101
111010111 000101001

Subtracting Using the Diminished Radix Complement

The diminished radix complement of a decimal number is that number subtracted from nine. Thus, the diminished radix of 6 is 3 since 9 - 6 = 3. For this reason, the diminished radix complement of a decimal number is often called the "9s complement." It is possible to subtract two decimal numbers using the 9s complement, as in the following example:

 735
-142

Calculate the 9s complement of the subtrahend: 857 (that is 9-1, 9-4, and 9-2). Then, add that 9s complement number to the original minuend:

 735
+857
1592

The initial "1" in the answer (the 1000s place) is dropped so the number of places in the answer is the same as for the two addends, leaving 592. Because the diminished radix is one less than the radix, one must be added to the answer; giving 593, which is the correct answer for 735-142. (For what it's worth, this is the method used by magicians who can subtract large numbers in their heads. While the explanation for complement subtraction is somewhat convoluted, the actual practice is fairly easy to master.)

The diminished radix complement (or ones complement) of a binary number is found by simply reversing each bit. Thus, the ones complement of 11010 is 00101. Just as in decimal, a binary number can be subtracted from another by adding the diminished radix complement of the subtrahend to the minuend, and then adding one to the answer. Here's an example:

 101001
-011011

Add the ones complement of the subtrahend:

 101001
+100100
1001101

The most significant bit is discarded so the solution has the same number of bits as for the two addends. This leaves 001101. Adding one to that number leaves 1110. In decimal, the problem becomes 41-27=14.

Subtracting by adding the diminished radix of the subtrahend and then adding one may seem awkward for humans, but complementing and adding is a snap for digital circuits. In fact, many early mechanical calculators used a system of adding complements rather than having to turn gears backwards for subtraction.

Because the diminished radix (or ones) complement of a binary number includes that awkward problem of having two representations for zero, this form of subtraction is not used in digital circuits; instead, the radix (or twos) complement is used.

Subtracting Using the Radix Complement

The radix complement of a number is the diminished radix plus one. As an example, the radix complement of a decimal number is the 9s complement plus one; and it is often called the 10s complement. Thus, the 10s complement of 7 is 3; or (9-7+1). It is possible to subtract two decimal numbers using the 10s complement, as in the following example:

 735
-142

Calculate the 10s complement of the subtrahend by finding the 9s complement and adding 1: 858 (that is 9-1, 9-4, and 9-2+1). Then, add that 10s complement number to the original minuend:

 735
+858
1593

The initial "1" in the answer (the 1000s place) is dropped so the answer has the same number of decimal places as the addends, leaving 593, which is the correct answer for 735-142.

To find the radix complement (or twos complement) of a binary number, each bit in the number is "flipped" (the ones complement) and then 1 is added to the result. Thus, the twos complement of 11010 is 00110 (or 00101+1). Just as in decimal, a binary number can be subtracted from another by adding the radix complement of the subtrahend to the minuend. Here's an example:

 101001
-011011

Add the twos complement of the subtrahend:

 101001
+100101
1001110

The most significant bit is discarded so the solution has the same number of bits as for the two addends. This leaves 001110 (or decimal 14). Converting all of this to decimal, the original problem is 41-27=14.

Overflow

One caveat with signed binary numbers is that of overflow, where the answer to an addition or subtraction problem exceeds the magnitude which can be represented with the allotted number of bits. Remember that the sign bit is defined as the most significant bit in the number. For example, with a six-bit number, five bits are used for magnitude, so there is a range from 00000 to 11111, or 0 to 31. If a sign bit is included, and using twos complement, numbers as high as 011111 (+31) or as low as 100000 (-32) are possible. However, an addition problem with two signed six-bit numbers that results in a sum greater than +31 or less than -32 will yield an incorrect answer. As an example, add 17 and 19 with signed six-bit numbers:

17 = 010001
19 = 010011

  010001
+ 010011
  100100

The answer (100100), interpreted with the most significant bit as a sign, is equal to -28, not +36 as expected. Obviously, this is not correct. The problem lies in the restrictions of a six-bit number field. Since the true sum (36) exceeds the allowable limit for our designated bit field (five magnitude bits, or +31), it produces what is called an overflow error. Simply put, six places is not enough bits to represent the correct sum, so whatever sum is obtained will be incorrect.

A similar error will occur if two negative numbers are added together to produce a sum that is too low for a six-bit binary field. As an example, add -17 and -19:

-17 = 101111
-19 = 101101

  101111
+ 101101
 1011100

Solution as shown: 011100 = +28. (Remember that the most significant bit is dropped in order for the answer to have the same number of places as the two addends.)

The (incorrect) answer for this calculation is 28. The fact that the true sum of -17 + -19 was too large to be properly represented with a five bit magnitude field is the cause of this difficulty.

Here is the same overflow problem again, but expanding the bit field to six magnitude bits plus a seventh sign bit. In the following example, both 17+19 and (-17)+(-19) are calculated to show that both can be solved using a seven-bit magnitude field rather than six-bits.

Add 17 + 19

  0010001
+ 0010011
  0100100

Solution: 0100100 = +36


Add (-17) + (-19)

  1101111
+ 1101101
 11011100

Solution: 1011100 = -36

The correct answer is only found by using bit fields sufficiently large to handle the magnitude of the sums.

Error Detection

Overflow errors in the above problems were detected by checking the problem in decimal form and then comparing the results with the binary answers calculated. For example, when adding +17 and +19, the answer was supposed to be +36, so when the binary sum checked out to be -28, something had to be wrong. Although this is a valid way of detecting overflow errors, it is not very efficient, especially for computers. After all, the whole idea is to be able to reliably add binary numbers together and not have to double-check the result by adding the same numbers together in decimal form! This is especially true when building logic circuits to add binary quantities: the circuit has to be able to detect an overflow error without the supervision of a human who already knows the correct answer.

The simplest way to detect overflow errors is to check the sign of the sum and compare it against the signs of the numbers added. Obviously, two positive numbers added together will give a positive sum, and two negative numbers added together will give a negative sum. With an overflow error, however, the sign of the sum is always opposite that of the two added numbers: +17 plus +19 gave -28, while -17 plus -19 gave +28. By checking the sign bits alone it becomes evident that something is wrong and an overflow error is detected.

In cases where the two addends have opposite signs, it is not possible to generate an overflow error. The reason for this is apparent when the nature of overflow is considered. Overflow occurs when the magnitude of a number exceeds the range allowed by the size of the bit field. If a positive number is added to a negative number, the sum will always be closer to zero than either of the two added numbers; or, its magnitude must be less than the magnitude of either original number, and so overflow is impossible.

Personal tools