Hinzufügen von 64-Bit-Zahlen mit 32-Bit-Arithmetik

Question

Wie fügen wir zwei 64-Bit-Zahlen mit 32-Bit-Arithmetik?

Answer 1

Fügen Sie zuerst die niedrigstwertigen Bytes hinzu, behalten Sie den Übertrag. 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

Sie jedes 32-Bit-Teil manuell manuell hinzufügen könnte und kümmern sich um die Durchführung.

Answer 3

Wenn die 64-Bit-Zahlen (a , ein) und (b , b), wobei x die hohen 32 Bits als unsigned genommen ist und x sind die niedrigen 32 Bits, die als vorzeichenlos angenommen werden, dann ist die Summe der beiden Zahlen unten angegeben.

c1 = a1 + b1 

c2 = a2 + b2 

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

Answer 4

Überlegen Sie, wie Sie zwei zweistellige Zahlen mit 1-stelliger Arithmetik hinzufügen.

42 
+39 
--- 

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

1 
42 
+39 
--- 
    1 

Jetzt die linke „Zehner“ Spalte addieren, einschließlich des Übertrags. 1 + 4 + 3 = 8.

1 
42 
+39 
--- 
81 

8 ist weniger als 10, also kein tragen. Sie sind fertig.

Was ist gerade passiert? Wenn Sie sagen, dass eine Zahl "42" (in der Basis 10), die Sie wirklich bedeuten

4*10+2 

oder äquivalent

4*10^1+2*10^0 

(wenn ich sage "a^b", wie „10^1 ", meine ich" a zur b-ten Macht erhoben ": a multipliziert mit sich selbst b mal. 10^0 ist 1. 10^1 ist 10. 10^2 ist 10 * 10 = 100 ...)

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

4*10+2+3*10+9 

Welche

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

jetzt gleich da „11“ nicht eine gültige stellige Zahl ist, müssen Sie 10 von denen 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.

so ist, warum habe ich darüber gesprochen, anstatt Ihre Frage zu 64-Bit-Zahlen und 32-Bit-Arithmetik? Weil sie eigentlich genau gleich sind!

Eine Ziffer reicht von 0 bis 9. Eine "32-Bit-Nummer" reicht von 0 bis 2^32-1. (Angenommen, es ist nicht signiert.)

Also, anstatt in Base 10 zu arbeiten, arbeiten wir in Base 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 sein^32-1. Diese Symbole sind Bitstrings.

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

a_1*10+a_0 
+b_1*10+b_0 

Sie sie in der Basis Nun fügen Sie 2^32 genau die gleiche wie ich sie in der Basis 10 hinzufügen - Einfach, anstatt mit Ziffern-Arithmetik hinzuzufügen, fügen Sie 32-Bit-Arithmetik hinzu!

Wie teilen Sie eine 64-Bit-Zahl a in zwei 32-Bit-Zahlen a_1 und a_0 auf? Teile a durch 2^32. Nicht im Gleitkomma, sondern ganzzahlig - wo Sie eine Dividende und einen Rest erhalten. Die Dividende ist a_1, der Rest ist a_0.

Leider erfordert das 64-Bit-Arithmetik. Allerdings, in der Regel ist A_1 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.

In der Regel, wenn Sie keine 64-Bit-Addition durchführen können, wird eine "64-Bit-Nummer" tatsächlich die beiden 32-Bit-Zahlen a_1 und a_0 sein. Sie haben kein Uint64_t, wenn Sie nicht Uint64_t Arithmetik tun können!

All dies setzt voraus, dass Sie nicht signierte Arithmetik ausführen, aber von hier aus ist es einfach, mit Zeichen umzugehen.

Answer 5

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

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

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

if (c1 < a1) 
    c2++; 

Die 'a1' in der 'if' mit 'B1' als auch ersetzt werden. Bei Überlauf ist c1 kleiner als a1 und b1.

Answer 6

es sieht so etwas wie diese

/* 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 nicht 32 Bits nicht verwendet 16 Bits gleichzeitig hinzuzufügen, nur ein zusätzliches Bit von Carry wird immer für die Zugabe erforderlich, und fast alle CPUs haben eine Wenn Sie eine 32-Bit-CPU verwenden, können Sie 64-Bit-Operanden in zwei 32-Bit-Operationen hinzufügen.

Answer 7

Fast jeder Prozessor hat das Carry-Bit und den Add-mit-Carry-Betrieb, was Ihnen nur dann wichtig ist, wenn Sie in der Baugruppe programmieren. Wenn Sie eine höhere Sprache verwenden, speichert der Compiler exakt die gleichen Add-with-carry-Operationen. Mein AVR-GCC gab mir das, wenn ich zwei 16-Bit-Nummern hinzufügte - der AVR ist 8-Bit - aber die gleichen Konzepte würden für höhere Prozessoren gelten.

Gegeben sind 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 in R1 gespeichert ist: R2.