32ビット演算を使用して64ビット数を追加する

Question

32ビット演算を使用して2つの64ビット数を追加するにはどうすればよいですか？

Answer 1

最初に最下位バイトを追加し、キャリーを保持します。 LSBからのキャリーを考慮して、最上位バイトを追加します。

; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx

Answer 2

1桁の算術演算を使用して2つの2桁の数値を追加する方法を検討します。

 42
+39
---

最初に正しい列を追加します。 （「1」または「ユニット」）。 2 + 9は11です。11「オーバーフロー」 1桁の算術演算なので、「キャリー」する必要があります。 10。

 1
 42
+39
---
  1

ここで、左側の「10」を合計します。キャリーを含む列。 1 + 4 + 3 = 8。

 1
 42
+39
---
 81

8は10未満なので、キャリーはありません。完了です。

今何が起こったのですか？数字が「42」だと言うと（10進数で）本当に意味する

4*10+2

または、同等に、

4*10^1+2*10^0

（「10 ^ 1」のように「a ^ b」と言うとき、「aのb乗」を意味します：aにbを掛けます。10^ 0は1です。10 ^ 1は10です。10^ 2は10 * 10 = 100 ...）

＆quot; 42＆quot;を追加すると、および「39」あなたは言っている

4*10+2+3*10+9

等しい

(4+3)*10+(2+9)*1
(4+3)*10+(11)*1
(4+3)*10+(1*10+1)*1

「11」以降、有効な1桁の数字ではありません。1から10を運び、10の位で1に変換する必要があります。

(4+3)*10+(1)*10+(1)*1
(4+3+1)*10+(1)*1
(8)*10+(1)*1

81です。

では、64ビット数と32ビット演算についての質問ではなく、なぜこれについて話しているのですか？実際にはまったく同じだからです！

数字の範囲は0〜9です。「32ビット数」範囲は0〜2 ^ 32-1です。 （署名されていないと仮定します。）

したがって、ベース10で作業するのではなく、ベース2 ^ 32で作業しましょう。ベース2 ^ 32では、2 ^ 32を10として書き込みます。ベース2 ^ 32に64ビットの数値を書き込むと、

(x)*10+y

xとyは、0〜2 ^ 32-1の数字の記号です。これらのシンボルはビット文字列です。

2つの64ビット数を追加する場合は、次のように2 ^ 32のベースで分割します。

 a_1*10+a_0
+b_1*10+b_0

今、ベース10に追加するのとまったく同じ方法で、ベース2 ^ 32に追加します-ちょうど、32ビット演算を使用して追加する数字演算を使用して追加するのではなく！

64ビットの数値aを2つの32ビットの数値a_1とa_0に分割するにはどうすればよいですか？ aを2 ^ 32で除算します。浮動小数点ではなく、整数型-配当と剰余を取得します。配当はa_1、残りはa_0です。

残念ながら、64ビット演算が必要です。ただし、通常、a_1は「最上位の半分」です。ので、Cスタイルの構文で：

a_1=(a >> 32)
a_0=(a & 0xFFFFFFFF)

where＆gt;＆gt;は右ビットシフトであり＆amp;ビット単位です。

通常、64ビット加算ができない場合は、「64ビット数」実際には、2つの32ビット数a_1とa_0になります。 uint64_t算術演算ができない場合、uint64_tはありません！

これはすべて、符号なし算術を行うことを前提としていますが、ここから符号の処理は簡単です。

Answer 3

以前に投稿されたCコードは不必要に冗長です：

unsigned a1, b1, a2, b2, c1, c2;

c1 = a1 + b1;
c2 = a2 + b2;

if (c1 < a1)
    c2++;

「if」の「a1」も「b1」に置き換えることができます。 オーバーフロー時には、c1はa1とb1の両方よりも小さくなります。

Answer 4

64ビットの数値が（a ₂ 、a ₁ ）および（b ₂ 、b _{1 ）、ここで x 2 は符号なしとみなされる上位32ビット、 x 1 は下位32ビットを符号なしと見なし、2つの数値の合計を以下に示します。}

c1 = a1 + b1

c2 = a2 + b2

if (c1 < a1 || c1 < b1)
   c2 += 1

Answer 5

このように見えます

/* break up the 64bit number into smaller, 16bit chunks */
struct longint { 
    uint16 word0; 
    uint16 word1;
    uint16 word2;
    uint16 word3;
};

uint16 add(longint *result, longint *a, longint *b)
{
    /* use an intermediate large enough to hold the result
       of adding two 16 bit numbers together. */
    uint32 partial;

    /* add the chunks together, least significant bit first */
    partial = a->word0 + b->word0;

    /* extract thie low 16 bits of the sum and store it */
    result->word0 = partial & 0x0000FFFF;

    /* add the overflow to the next chunk of 16 */
    partial = partial >> 16 + a->word1 + b->word1;
    /* keep doing this for the remaining bits */
    result->word1 = partial & 0x0000FFFF;
    partial = partial >> 16 + a->word2 + b->word2;
    result->word2 = partial & 0x0000FFFF;
    partial = partial >> 16 + a->word3 + b->word3;
    result->word3 = partial & 0x0000FFFF;
    /* if the result overflowed, return nonzero */
    return partial >> 16;
}

実際のハードウェアは32ビットを使用して一度に16ビットを追加することはできません。追加に必要なキャリーの追加ビットは1つだけです。 32ビットCPUを使用している場合、2つの32ビット操作で64ビットオペランドを追加できます。

Answer 6

ほとんどすべてのプロセッサにはキャリービットとキャリー付き加算演算があり、これらはアセンブリでプログラミングしている場合にのみ重要です。より高い言語を使用している場合、コンパイラーはまったく同じadd-with-carry操作をダンプします。私のAVR-GCCは、2つの16ビット数（AVRは8ビット）を追加するときにこれを教えてくれましたが、同じ概念がより高いプロセッサにも適用されます。

数値がレジスタR1：R2およびR3：R4：にある場合

ADD R2,R4 ; first add the two low-bytes, result stored into R2
ADC R1,R3 ; then the two high-bytes and the carry bit, into R1

結果はR1：R2に保存されます。