bit-manipulation - 使用整数的二进制编码的十进制加法

Question

如果我有两个压缩 BCD 格式的数字并想要将它们相加，那么像这样添加它们是一个好方法吗:将两个数字转换为整数，执行正常的整数加法，然后将结果转换回 BCD？

Answer 1

下面的 C99 代码添加了压缩 BCD 操作数，其中八个 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 中的位将不同。因此我们可以找到带有进位的位 (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 的答案中提供了一个卓越的解决方案(需要更少的操作)。此变体特别适合具有可评估三个参数的任何逻辑函数的指令的处理器架构，例如现代 NVIDIA GPU 的 LOP3 指令。

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);
}