1

パックされた BCD 形式の 2 つの数値があり、それらを加算したい場合、次のように加算するのは良い方法ですか? 両方の数値を整数に変換し、通常の整数加算を実行してから、結果を BCD に戻します

4

1 に答える 1

1

以下の C99 コードは、パックされた BCD オペランドを追加し、8 つの BCD 桁が に格納されますuint32_t。uint64_tこのコードは、16 BCD 桁の処理を選択することで、より広い BCD オペランドに簡単に拡張できます。このアプローチはビット並列処理に依存しているため、ナロー パックされた BCD オペランドには効率的ではない場合があります。

パックされた BCD 形式では、各 BCD 桁が符号なし整数オペランドの 1 つのニブル (4 ビット グループ) を占有します。ニブルごとの加算の結果が 9 を超える場合、次に高いニブルへのキャリーが必要です。通常の整数加算を使用して 2 つのパックされた BCD オペランドを加算すると、ニブルの合計が > 9 であるが < 16 の場合、目的のニブル キャリーは発生しません。これを改善するには、各ニブルの合計に 6 を追加します。

ニブル キャリーは次のように見つけることができxます。通常の整数加算中に次の下位ビット位置からのキャリーインがあるビット位置では、 と のビットが異なります。したがって、キャリーインを としてビットを見つけることができます。キャリーインのビット 4、8、...、32 に関心があります。これは、ビット 3、7、...、31 からのキャリーアウトです。yx ^ yx ^ yx + y(x ^ y) ^ (x + y)

uint32_tオペランドは 32 ビットしか保持しないため、ビット 31 からビット 32 へのキャリーアウトがある場合、わずかな問題があります。これは、2 つの符号なし整数の和がどちらの加数よりも小さい場合に検出できます。8 桁オペランドの代わりに 7 桁オペランドを操作する場合、ビット 31 からのキャリーアウトを処理する 3 つの操作を省略できます。

/* 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 Part 1は、セクション 7.1.3 の演習 100 の解答において、優れたソリューション (必要な操作が少ない) を提供しています。LOP3このバリアントは、最新の NVIDIA GPUの命令など、3 つの引数の任意の論理関数を評価できる命令を持つプロセッサ アーキテクチャに特に適しています。

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 に答える