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

Question

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

Answer 1

下面的C99代码将打包的BCD操作数与存储在uint32_t中的八个BCD数字相加。通过选择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位是有意义的。

如果存在一个小问题因为uint32_t操作数仅保存32位，所以从位31到位32执行。如果我们发现两个无符号整数的和小于任何一个加数，我们可以检测到这一点。操作7位操作数而不是8位操作数时，可以省略处理从位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); 
}