Двоичное кодированное десятичное сложение с использованием целого числа

Question

Если у меня есть два числа в упакованном формате BCD и вы хотите их добавить, это хороший подход, чтобы добавить их так: преобразовать оба числа в целые числа, выполнить нормальное целочисленное добавление, а затем преобразовать вернуться к BCD?

Answer 1

В приведенном ниже коде C99 добавлены упакованные операнды BCD с восемью цифрами BCD, хранящимися в uint32_t. Этот код можно легко расширить до более широких операндов BCD, выбрав uint64_t для обработки 16 цифр 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 
} 

---

Кнут, TAOCP Vol.4A Часть 1, предлагает превосходное решение (требующее меньшего числа операций) в ответ на осуществление 100 из раздела 7.1.3. Этот вариант особенно хорошо подходит для процессорных архитектур с инструкцией, которая может оценивать любую логическую функцию из трех аргументов, например инструкцию LOP3 современных графических процессоров NVIDIA.

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