1

如果我有两个打包 BCD 格式的数字并且想要添加它们，像这样添加它们是否是一个好方法：将两个数字都转换为整数，执行正常的整数加法，然后将结果转换回 BCD？

4

1 回答 1

1

下面的 C99 代码添加了压缩 BCD 操作数，其中 8 个 BCD 数字存储在uint32_t. uint64_t通过选择处理 16 个 BCD 数字，此代码可以轻松扩展到更宽的 BCD 操作数。由于这种方法依赖于位并行处理，因此对于窄压缩 BCD 操作数可能效率不高。

在压缩 BCD 格式中，每个 BCD 数字占用一个无符号整数操作数的一个半字节（4 位组）。如果半字节加法的结果是总和 > 9，我们希望进位到下一个更高的半字节。如果我们使用常规整数加法来添加两个压缩 BCD 操作数，当半字节总和 > 9 但 < 16 时，将不会出现所需的半字节进位。为了解决这个问题，我们可以在每个半字节总和上再加 6。

我们可以找到半字节进位如下：两个整数的按位和x，y是x ^ y。在常规整数加法期间，在从下一个低位位置进位的任何位位置，和中的位x ^ y将x + y不同。所以我们可以找到带进位的位 as (x ^ y) ^ (x + y)。我们对进位的第 4、8、...、32 位感兴趣，它们是第 3、7、...、31 位的进位。

如果从第 31 位进位到第 32 位，则存在一个小问题，因为uint32_t操作数仅包含 32 位。如果我们发现两个无符号整数的和小于任何一个加数，我们就可以检测到这一点。当对七位操作数而不是八位操作数进行操作时，可以省略处理第 31 位进位的三个操作。

/* 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 第 1 部分，在第 7.1.3 节的练习 100 的答案中提供了一个出色的解决方案（需要更少的操作）。这种变体特别适合具有可以评估三个参数的任何逻辑函数的指令的处理器架构，例如LOP3现代 NVIDIA GPU 的指令。

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);
}
于 2015-04-26T10:33:36.720 回答