CODEWITHSUNDEEP
bit-manipulationadditionbcd
bingo157
bingo157

Reputation: 153

Binary coded decimal addition using integer

If I have two numbers in packed BCD format and want to add them, is it a good approach to add them like this: convert both numbers to integers, perform a normal integer addition, then convert the result back to BCD?

Upvotes: 2

Views: 1376

Answers (1)

njuffa
njuffa

Reputation: 26085

The C99 code below adds packed BCD operands with eight BCD digits stored in a uint32_t. This code can easily be extended to wider BCD operands by choosing uint64_t to process 16 BCD digits. Since this approach relies on bit-parallel processing it may not be efficient for narrow packed BCD operands.

In a packed BCD format, each BCD digit occupies one nibble (4-bit group) of an unsigned integer operand. If nibble-wise addition results in a sum > 9, we want a carry into the next higher nibble. If we use regular integer addition to add two packed BCD operands, the desired nibble carries will not occur when the nibble sum is > 9, but < 16. To remedy this, we can add an additional 6 to each nibble sum.

We can find the nibble carries as follows: The bit-wise sum of two integers x, y is x ^ y. At any bit position that has a carry-in from the next lower bit position during regular integer addition, the bits in x ^ y and x + y will differ. So we can find bits with carry-in as (x ^ y) ^ (x + y). We are interested in bits 4, 8, ..., 32 for the carry-in, which are the carry-outs from bits 3, 7, ..., 31.

There is a slight problem if there is a carry-out from bit 31 to bit 32 since the uint32_t operands only hold 32 bits. We can detect this if we find that the sum of two unsigned integers is smaller than either of the addends. The three operations handling the carry-out from bit 31 can be omitted when operating on seven-digit operands instead of eight-digit operands.

/* Add two packed BCD operands, where each uint32_t holds 8 BCD digits */
uint32_t bcd_add (uint32_t x, uint32_t y)
{
    uint32_t t0, t1;
    t0 = x + 0x66666666;         // force nibble carry when BCD digit > 9
    t1 = x ^ y;                  // bit-wise sum
    t0 = t0 + y;                 // addition with nibble carry
    t1 = t1 ^ t0;                // (x ^ y) ^ (x + y)
    t0 = t0 < y;                 // capture carry-out from bit 31
    t1 = (t1 >> 1) | (t0 << 31); // nibble carry-outs in bits 3, 7, ..., 31
    t0 = t1 & 0x88888888;        // extract nibble carry-outs 
    t1 = t0 >> 2;                // 8 - (8 >> 2) = 6
    return x + y + (t0 - t1);    // add 6 to any digit with nibble carry-out
}

Knuth, TAOCP Vol.4A Part 1, offers a superior solution (requiring fewer operations) in the answer to exercise 100 from section 7.1.3. This variant is particularly well suited to processor architectures with an instruction that can evaluate any logical function of three arguments, such as the LOP3 instruction of modern NVIDIA GPUs.

uint32_t median (uint32_t x, uint32_t y, uint32_t z)
{
     return (x & (y | z)) | (y & z);
}

uint32_t bcd_add_knuth (uint32_t x, uint32_t y)
{
    uint32_t z, u, t;
    z = y + 0x66666666;
    u = x + z;
    t = median (~x, ~z, u) & 0x88888888;
    return u - t + (t >> 2);
}

Upvotes: 5

Related Questions