How a CPU Adds Decimal Numbers

Date: 10/22/2000 at 17:31:08
From: Farina
Subject: 8-bit CPU

Hi, Dr. Math. Can you help me? How does an 8-bit CPU add up two 
four-digit numbers and why does it take four operations to do so? 
Please explain.

Date: 10/23/2000 at 14:00:01
From: Doctor TWE
Subject: Re: 8-bit CPU

Hi Farina - thanks for writing to Dr. Math.

Are you referring to 4-digit _decimal_ numbers? I'll assume that the 
numbers are stored in normal Binary Coded Decimal (BCD), and that you 
want the result in BCD as well. (Note that there are other forms of 
Binary Coded Decimal, like Excess-3 code, 2'421 code, or BCD Gray 
code, but the most commonly used form is 8421 BCD, called normal BCD 
or simply BCD.)

First, let me briefly explain BCD. In BCD, each digit of a decimal 
number is represented by a 4-bit value (similar to the way hexadecimal 
digits are represented by 4-bit groups in "pure" binary). Since 
decimal only has the digits 0 through 9, only the following values are 
valid "4-bit groups" in BCD:

     DEC  BCD      DEC  BCD
      0   0000      5   0101
      1   0001      6   0110
      2   0010      7   0111
      3   0011      8   1000
      4   0100      9   1001

The combinations 1010, 1011, 1100, 1101, 1110, and 1111 are invalid 
because they don't add up to a decimal digit.

Since each decimal digit requires 4 BCD bits, we need 16 bits to 
represent a 4-digit decimal value. Your CPU, however, can only work 
with 8 bits at a time. So we'll need to break up the numbers into two 
parts (bytes) and work with one byte at a time. Let's call the bytes 
(or the registers where the bytes are stored) A1 and A0 for the first 
number - with A1 being the more significant byte (MSB) and A0 being 
the less significant (LSB.) Let's call the bytes B1 and B0 for the 
second number - again letting B1 be the more significant byte and B0 
the less significant. For example, let's say we want to add the 
numbers:

       2483
     + 1795
      ------

The 2483 would be represented as 0010 0100 1000 0011 (I'll put spaces 
in between each group of 4 bits for readability) and so:

     A1 = 0010 0100
     A0 = 1000 0011

The 1795 would be represented as 0001 0111 1001 0101 and so:

     B1 = 0001 0111
     B0 = 1001 0101

When adding large numbers with pencil and paper, we start with the 
least significant digits (the units place) and work our way from right 
to left. Similarly, our CPU will begin with the LSBs and work over to 
the MSBs.

First we'll add the LSBs; A0 + B0:

      1      111    <- carry bits
        1000 0011
     +  1001 0101
      ------------
      1 0001 1000

Note that the CPU will do a straight binary addition. The answer is 
0001 1000 (18 decimal) with a carry-out of 1. The carry-out is stored 
as the "C-flag" in a register, usually called the Condition Code 
Register (CCR) or Status Register (SR), depending on the CPU's 
manufacturer.

Of course, this answer is wrong: 83 + 95 = 178, not 118. Why did it 
get the wrong result? Because when it added the 8 and the 9 in the 
tens digit, it got 17 and carried 16 of them into the carry-out. (This 
is because it did the addition in pure binary.) It should have only 
carried 10, not 16, into the carry out, so to compensate, we'll 
add 6 back into the tens digit (0110 0000 in BCD), like this:

      1      111
        1000 0011
     +  1001 0101
      ------------
      1 0001 1000
     +  0110 0000
      ------------
      1 0111 1000

That's better. Let's store that as S0. Now the MSBs. We'll add 
A1 + B1:

                 _____ Carry-over from the LSBs (in the C-flag)
                /
               v
            1111
       0010 0100
     + 0001 0111
      -----------
       0011 1100

This time, we got the answer 0011 1100, but that doesn't make sense in 
BCD (1100 is an invalid 4-bit group in BCD.) Why? Because again the 
CPU did the addition in pure binary. When it added 4 + 7 + 1 it got 12 
and represented it in binary as 1100. But for BCD it should have 
carried 10 of them over to the tens digit and only kept 0010 (2 in 
decimal). To "force" the half-carry (i.e. the carry from the 4th bit 
to the 5th), we'll add 6 to the units digit (0000 0110 in BCD) to make 
the group of 10 that should have been carried a group of 16 that the 
CPU will carry:

            1111
       0010 0100
     + 0001 0111
      -----------
       0011 1100
     + 0000 0110
      -----------
       0100 0010

Let's store that as S1. Now we have our answer in S1 and S0: 
0100 0010 0111 1000, or 4278 decimal.

How do we know if and when to use "fudge factors" like the 0110 0000 
and 0000 0110 that we used here? Most CPUs have either a "BCD Mode" 
that will automatically determine the proper fudge factor and add it 
after every ADD (or ADC - Add with Carry) operation, or they have a 
special instruction like DAA (Decimal Adjust Accumulator). Here are 
the rules the CPU uses when determining what "fudge factor" to add: 
(The H is the half-carry flag and the C is the carry-out flag.)

     1. If H = 1 or the  last 4 bits > 1001, add 0000 0110
     2. If C = 1 of the first 4 bits > 1001, add 0110 0000

Note that both can occur (thus adding 0110 0110), and the first step 
can cause the second to occur - that's why they must be tested 
sequentially. Sometimes no adjustment is necessary.

Here's a bit of pseudocode that adds two 4-digit BCD values. A1, A0, 
B1 and B0 are registers that are storing the inputs as defined above, 
and S1 and S0 are registers that are storing the outputs also as 
defined above:

      :
     LDA A0     ; Load accumulator with LSB of addend
     ADD B0     ; Add LSB of augend to accumulator
     DAA        ; Add "fudge factor" to adjust result to BCD
     STA S0     ; Store LSB of sum
     LDA A1     ; Load accumulator with MSB of addend
     ADC B1     ; Add MSB of augend to accumulator with carry from LSB
     DAA        ; Add "fudge factor" to adjust result to BCD
     STA S1     ; Store MSB of sum
      :

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/