Addieren von 64-Bit-Zahlen mit 32-Bit-Arithmetik

Question

Wie addieren wir zwei 64-Bit-Zahlen mit 32-Bit-Arithmetik?

Answer 1

Fügen Sie die am wenigsten signifikanten Bytes zuerst, den Übertrag halten. Fügen Sie die höchstwertigen Bytes des Übertrags von LSBs Berücksichtigung

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

Answer 2

Überlegen Sie, wie Sie zwei 2-stelligen Zahlen addieren unter Verwendung von 1-stelligen Arithmetik.

 42
+39
---

Zuerst die rechte Spalte hinzufügen. (Die „Einsen“ oder „Einheiten“). + 2 9 11 11 Ihre 1 Stelle Arithmetik "überschwemmt", so haben Sie zu "tragen" die 10.

 1
 42
+39
---
  1

Nun fügen Sie die linke „Zehner“ Spalte, einschließlich der Übertrag. 1 + 4 + 3 = 8 ist.

 1
 42
+39
---
 81

8 weniger als 10, so dass keine zu tragen. Sie sind fertig.

Was ist passiert? Wenn Sie sagen, dass eine Zahl „42“ (in der Basis 10) meinen Sie wirklich

4*10+2

oder äquivalent

4*10^1+2*10^0

(wenn ich "a ^ b", wie "10 ^ 1" meine ich "a in die b'th potenziert": a. Mit sich selbst multipliziert mal b 10 ^ 0 1 ^ 10 1 10. 10 ^ 2 ist 10 * 10 = 100 ...)

Wenn Sie hinzufügen "42" und "39" Sie sagen,

4*10+2+3*10+9

Welche gleich

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

Nun, da „11“ ist keine gültige einstelligen Zahl, benötigen Sie 10 von denen zu tragen, sie in eine 1 in der Zehnerstelle drehen.

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

, die 81 ist.

Also, warum habe ich darüber gesprochen, anstatt Ihre Frage zu 64-Bit-Zahlen und 32-Bit-Arithmetik? Denn sie sind eigentlich genau das gleiche!

Eine Ziffer im Bereich von 0 bis 9 A "32-Bit-Zahl" im Bereich von 0 bis 2 ^ 32-1. (Vorausgesetzt, es ist nicht signiert.)

Also, anstatt Erfahrungen bei der Arbeit 10, lassen Sie sich in der Basis arbeitet 2 ^ 32. In Basis 2 ^ 32, schreiben wir 2 ^ 32 als 10. Wenn Sie eine 64-Bit-Zahl in der Basis 2 ^ 32 schreiben, wäre es

(x)*10+y

, wobei x und y sind Symbole für Zahlen zwischen 0 und 2 ^ 32-1. Diese Symbole sind bitstrings.

Wenn Sie zwei 64-Bit-Zahlen addieren, brechen sie in der Basis um 2 ^ 32, wie:

 a_1*10+a_0
+b_1*10+b_0

Nun fügen Sie sie in der Basis 2 ^ 32 genau das gleiche wie du sie in der Basis 10 hinzufügen - nur, anstatt das Hinzufügen einstellige Arithmetik Sie 32-Bit-Arithmetik add mit

!

Wie spalten Sie eine 64-Bit-Zahl, die eine in zwei 32-Bit-Zahlen a 1 und a_0? Unterteilen eines durch 2 ^ 32. Nicht in Punkt schwimmen, aber integerwise - wo man eine Dividende und einen Rest erhalten. Die Dividende ist a 1, der Rest ist a_0.

Leider erfordert, dass 64-Bit-Arithmetik. Allerdings, in der Regel a 1 ist die "bedeutendste Hälfte" ein, so, in C-Stil-Syntax:

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

, wo >> ist ein Recht bitshift und & ist bitweise und.

Normalerweise, wenn Sie nicht 64-Bit zusätzlich tun können, eine „64-Bit-Zahl“ tatsächlich die zwei 32-Bit-Zahlen a 1 und a_0 sein. Sie werden keine uint64_t haben, wenn Sie nicht uint64_t Arithmetik tun!

All dies setzt voraus, dass Sie nicht signierte Arithmetik tun, sondern mit Zeichen zu tun ist leicht, von hier.

Answer 3

Der C-Code zuvor geschrieben ist unnötig ausführlicher:

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

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

if (c1 < a1)
    c2++;

Die ‚a1‘ in der ‚if‘ kann mit ‚b1‘ und ersetzt werden. Bei Überlauf wird als sowohl c1 a1 und b1 weniger.

Answer 4

Wenn die 64-Bit-Zahlen sind (a ₂ a ₁ ) und (b ₂ , b ₁ ), wobei x ₂ die hohen 32 Bits als unsigned genommen und x ₁ ist die geringe 32 Bits als unsigned genommen, dann wird die Summe der zwei Zahlen wird nachstehend angegeben.

c1 = a1 + b1

c2 = a2 + b2

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

Answer 5

es sieht ungefähr so ​​aus

/* 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;
}

Tatsächliche Hardware verwendet keine 32 Bits, um jeweils 16 Bits hinzuzufügen. Für die Addition wird immer nur ein zusätzliches Übertragsbit benötigt, und fast alle CPUs verfügen über ein Übertragsstatusflag für den Fall, dass eine Additionsoperation überläuft. Wenn Sie also eine verwenden Bei einer 32-Bit-CPU können Sie 64-Bit-Operanden in zwei 32-Bit-Operationen hinzufügen.

Answer 6

So ziemlich jeder Prozessor hat das Übertragbit und Add-mit-Carry-Operation, die Sie interessieren, wenn Sie in der Montage sind zu programmieren. Wenn Sie eine höhere Sprache verwenden, Dumps der Compiler die exakt gleichen Add-mit-Carry-Operationen aus. Mein AVR-GCC gab mir dies beim Hinzufügen von zwei 16-Bit-Zahlen - der AVR 8-Bit - aber die gleichen Konzepte würden für höhere Prozessoren gelten.

Da die Zahlen in den Registern R1: R2 und 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

Das Ergebnis wird gespeichert in R1. R2