使用整數的二進制編碼的十進制加法

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