BCD Arithmetic

Now we come to the difficult topic of how to perform BCD arithmetic. If you have a lot of arithmetic to do then the best solution is to convert to binary, do the arithmetic and then convert back. This has the advantage that you know how to work with binary and the disadvantage that, if it involves division, you might not get the same answer as a human.

In many cases, however, the arithmetic that you want to do is very simple. One way of doing BCD arithmetic is to unpack the nibbles into an array and then add nibbles one by one. The problem with this is that you have to take care of the decimal carries. For example, 9+1 gives you a nibble that isn't a decimal digit i.e. 10 or 1010 in binary or A in hex. To correct this you have to subtract 10 from this nibble and add one to the next nibble so performing a carry. That is, if you add the nibbles together you have to scan for values that are greater than 9 and from each you subtract 10 and add a carry to the next nibble. Notice that as 9+9 is 18 decimal or 0001 0010 you can even overflow 4 bits and so each nibble should be stored in its own byte.

Consider for a moment addition of just two BCD digits each one stored in a byte. For example:

   9  +     9  =   18
0x09  +  0x09  = 0x12

At this point you need to subtract 10 and carry 1 onto the next nibble. However, if you look, the addition has already put a 1 into the next nibble, it is only the original nibble that is wrong. The reason is that the carry 1 into the next highest nibble has actually carried 16 not 10 from the lower nibble - remember this is implemented as binary. To get the correct BCD we have to return 6 to the lower nibble.

   9  +     9  =   18
0x09  +  0x09  = 0x12 + 0x06 = 0x18

If you have implemented BCD arithmetic before, you might have wondered where the mysterious "6" comes from.

int result = myBCD1 + myBCD2;
if(result>9)result=result+6;

You can extend this method so that you can add multiple digits and then correct the result to BCD, but it isn't straightforward as you have to detect the binary carry between the nibbles and add 6 to the lower nibble whenever it has occurred.

If we have two packed BCD values in four byte unsigned ints then we can simply add them together:

unsigned int myBCD1 = 0x90000;
unsigned int myBCD2 = 0x90000;
int result = myBCD1 + myBCD2;

but the result will be incorrect in any nibble that generated a carry to the next nibble. We need to find out where the carries occur. This we can do because we already know that exclusive or (XOR) is addition without taking the carries into account. So:

(myBCD1 ^ myBCD2)

is the addition without carry. If we XOR this with the sum that did include a carry there will only be bits set where they differ, i.e bits that result from a carry:

(myBCD1 ^ myBCD2)^result

This gives a one at every bit that was generated by a carry, but we are only interested in carries from one nibble to the next and these can only be positioned at the first bit of the nibble. To pick just these out we have to use a mask:

int carry = (myBCD1 ^ myBCD2)^result & 0x011111110;

notice that the first nibble cannot have received a carry.

Now we have a carry which has a one in the first bit of any nibble that received a carry from the adjacent nibble. We need to create a mask with a 6 in each position that generated a carry and this we can do using a shift and OR:

int sixmask = (carry >> 2) | (carry >> 3);

Finally we can add the sixes into the result to correct it:

result += sixmask;

Notice that you cannot allow a carry in the final nibble - the result is an overflow.

You can extend this bit manipulation technique to long long types if you need more digits. You can also make it work for subtraction by using ten’s complement, see the next section.

In chapter but not in this extract

• Negative Numbers
• Overflow and Undefined Behavior
• GCC Overflow Detection
• DIY Overflow Detection Before it Happens
• Using Unsigned Arithmetic to Detect Overflow
• Avoiding Overflow by Increased Precision
• Trapping Signed Overflow
• Detecting Unsigned Rollover
• Modular Arithmetic
• Division by Zero
• Trapping Division by Zero

Summary

• Integer arithmetic is achieved using a full adder. When implemented in software, integer addition is iterative.

• Binary is not the only possible representation - Binary Coded Decimal is also common.

• Implementing BCD arithmetic is surprising difficult to do efficiently.

• There are different ways of representing negative numbers. Sign magnitude is common, but two’s-complement is preferable as it takes care of the sign automatically.

• What happens when arithmetic results in a value that cannot be represented is a difficult topic. For unsigned arithmetic the standard defines that it should result in a rollover. For signed arithmetic overflow is undefined behavior.

• Detecting overflow before it happens is an important task and there are many ways of doing the job. There are built-in functions in GCC, but if you don’t want to, or can’t, use them it is possible to test for overflow using conditionals.

• To avoid problems with undefined behavior, you can always implement signed arithmetic using unsigned operators, or you can increase the precision so that overflow cannot occur.

• In many cases the operating system will provide a software interrupt, or trap, that you can use to detect and handle signed overflow. In most cases you will also need to use some advanced C to implement a try-catch construct.

• Although most of the problems are centered on signed overflow, it can be important to detect unsigned overflow.

• Modular arithmetic is, in fact, what all integer arithmetic is. Integer division and the mod or remainder operator are very useful in general programming.

• Detecting division by zero should be easy, but it is often difficult to detect it in a way that allows you to handle it in software.

Now available as a paperback or ebook from Amazon.

Applying C For The IoT With Linux

1. C,IoT, POSIX & LINUX
2. Kernel Mode, User Mode & Syscall
   
3. Execution, Permissions & Systemd
   Extract Running Programs With Systemd
4. Signals & Exceptions
   Extract  Signals
5. Integer Arithmetic
   Extract: Basic Arithmetic As Bit Operations
   Extract: BCD Arithmetic  ***NEW
6. Fixed Point
   Extract: Simple Fixed Point Arithmetic
7. Floating Point 
8. File Descriptors
   Extract: Simple File Descriptors 
   Extract: Pipes 
9. The Pseudo-File System
   Extract: The Pseudo File System
   Extract: Memory Mapped Files 
10. Graphics
    Extract: framebuffer
11. Sockets
    Extract: Sockets The Client
    Extract: Socket Server
12. Threading
    Extract:  Pthreads
    Extract:  Condition Variables
    Extract:  Deadline Scheduling
13. Cores Atomics & Memory Management
    Extract: Applying C - Cores 
14. Interupts & Polling
    Extract: Interrupts & Polling 
15. Assembler
    Extract: Assembler

Also see the companion book: Fundamental C

<ASIN:1871962609>

<ASIN:1871962617>

Related Articles

Remote C/C++ Development With NetBeans

Raspberry Pi And The IoT In C

Getting Started With C/C++ On The Micro:bit

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info