More mind-boggling math: Adding and subtracting unsigned BCD
My last column introduced the concepts underlying BCD (binary-coded-decimal) representations. In particular, we considered unsigned versus 10s-complement versions of BCD numbers. In this column we are going to consider how we go about adding and subtracting unsigned BCD values.
Just to remind ourselves, if we are using an 8-bit byte to represent two "unsigned" BCD digits, then #00 to #99 in BCD equates to 0 to +99 in decimal (we will use "#" characters to indicate BCD values).
Adding unsigned BCD
So how would we go about adding two such bytes together? One technique would be to create a special adder that can directly add two BCD digits together, along with a Cin ("carry-in") bit, and generate a single BCD digit as output along with a Cout ("carry-out") bit, as shown in .
Remembering that each BCD digit can only support values of 0000 to 1001 in binary (0 to 9 in decimal), this means a result greater than 9 will cause a carry-out. For example, 3 + 4 = 7 in decimal, so if we present BCD digits of #3 and #4 to our adder, we expect to see a result of #7 with Cout = 0. By comparison, 6 + 8 = 14 in decimal, so if we present BCD digits of #6 and #8 to our adder, we expect to see a result of #7 with Cout = 1.
Now, if we wish to work with byte-wide values, we could connect two of our adders together as shown in .
As an alternative to creating a special-purpose BCD adder unit, some microprocessors simply use their existing binary-adder functions. The problem is that the binary adder can introduce errors when working with BCD values. For example, consider the following example, where "$" characters indicate hexadecimal values:
$27 + $15 = $3C (Result from a binary addition)
#27 + #15 = #42 (Result expected from a BCD addition)
The problem in this case is that when we add the least-significant nybbles together, we end up with 7 + 5 = 12 (that's 1100 in binary). This is a perfectly legitimate value for a binary addition, but if we are wishing to perform a BCD operation, we would expect to see a result of 2 (that's 0010 in binary) with a carry-out of 1 from the first nybble. This means that, following an ADD instruction, we would have to perform a special DAA ("decimal add adjust") instruction, which corrects for any errors introduced by the binary adder.
We can envisage the way in which this DAA instruction works as follows. First, we examine the value in the least-significant nibble. If this value is greater than 9, then a value of $06 will be added to the result. Apart from anything else, this will cause a carry-out from the least-significant nybble that will be automatically added to the result in the most-significant nybble. Next, we examine the value in the most-significant nibble. If this value is greater than 9, then a value of $60 will be added to the result. Once again, apart from anything else, this will cause a carry-out from the most-significant nybble.
So if we return to the example above, using a binary ADD to add #27 and #15 will initially result in a value of $3C. But when we perform the DAA instruction, this will add $06 to the result, so we'll end up with #42. (Depending on the result, the DAA instruction will end up adding $00, $06, $60, or $66 to the result from the ADD.)
Subtracting unsigned BCD
This is where things start to get clever. In decimal, we know that a subtraction operation like +7 – +3 = +4 can also be performed by changing the sign of the subtrahend and inverting the sign of the operation: that is, +7 + (–3) = +4. In binary, we implement this type of thing using ones and twos complements. For example, suppose we wished to perform the following operation on unsigned binary values:
01001001 – 00011000 = ? (that's 73 – 24 = ? in decimal)
We can achieve the same result as follows:
01001001 + (the twos complement of 00011000)
Furthermore, the twos complement of a binary number is equal to its ones complement + 1, so we could rewrite our equation as follows:
01001001 + (the ones complement of 00011000) + 1
The way we obtain the ones complement of a binary value is to subtract it from a value of all 1s. This gives:
01001001 + (11111111 – 00011000) + 1
Furthermore, subtracting the subtrahend from all 1s is the same as simply inverting all of its bits (you'll see why we explained it as subtraction in a moment), which gives the following:
01001001 + (11100111) + 1 = 100110001
In this case, the most-significant bit (the ninth bit) of the result is a carry-out (more formally known as a borrow-out-not) from our 8-bit addition, so we would essentially discard it by storing it in the carry flag. Thus, we actually end up with:
01001001 + (11100111) + 1 = 00110001 (that's 73 – 24 = 49 in decimal)
The reason we do all of this, of course, is that it's really simple to generate the ones complement of a value by inverting all of its bits, thereby allowing us to use the binary adder to perform both additions and subtractions. The point is that we can use exactly the same process in BCD. For example, suppose we wish to perform the following operation:
#73 – #24 = ?
We can achieve the same result as follows:
#73 + (the 10s complement of #24)
Now, the 10s complement of a BCD number is equal to its nines complement + 1, so we could rewrite our equation as follows:
#73 + (the nines complement of #24) + 1
And the way we obtain the nines complement of a BCD value is to subtract it from a value of all 9s. This gives:
#73 + (#99 – #24) + 1
In turn, this results in the following:
#73 + (#75) + 1 = #149
In this case, the most-significant digit (the third digit) of the result is a carry-out from our two-digit addition, and we would essentially discard this by storing it in the carry flag. Thus, we actually end up with:
#73 + #75 + 1 = #49 (that's 73 – 24 = 49 in decimal)
What about signed BCD values?
The problem with all of the above is that, by definition, unsigned numbers can be used only to represent positive values. This means that we cannot subtract a larger value from a smaller one, because we have no way of representing a negative result. Obviously this would be somewhat limiting if we wished to perform math equations of any real interest. The solution is to use the signed (10s complement) BCD values that we introduced in the previous column, and this will be the topic of our next article.
Clive "Max" Maxfield is the co-author of "How Computers Do Math" (ISBN: 0471732788) featuring the pedagogical and phantasmagorical virtual DIY Calculator. In addition to being a hero, trendsetter, and leader of fashion, Max is widely regarded as being an expert in all aspects of computing and electronics (at least by his mother).