Aggiunta di numeri a 64 bit utilizzando l'aritmetica a 32 bit

Question

Come aggiungere due numeri a 64 bit usando l'aritmetica a 32 bit ??

Answer 1

Aggiungi prima i byte meno significativi, mantieni il carry. Aggiungi i byte più significativi considerando il carry dagli LSB:

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

Answer 2

Considera come aggiungere due numeri a 2 cifre usando l'aritmetica a 1 cifra.

 42
+39
---

Per prima cosa aggiungi la colonna di destra. (Le "unità" o "unità"). 2 + 9 è 11. 11 "traboccato" la tua aritmetica a 1 cifra, quindi devi " trasportare " il 10.

 1
 42
+39
---
  1

Ora aggiungi il "decine" a sinistra colonna, incluso il carry. 1 + 4 + 3 = 8.

 1
 42
+39
---
 81

8 è inferiore a 10, quindi non trasportare. Hai finito.

Che cosa è appena successo? Quando dici che un numero è " 42 " (nella base 10) intendi davvero

4*10+2

O, equivalentemente,

4*10^1+2*10^0

(quando dico "a ^ b", come "10 ^ 1", intendo "a elevato alla b" potenza ": a moltiplicato per se stesso b volte. 10 ^ 0 è 1. 10 ^ 1 è 10. 10 ^ 2 è 10 * 10 = 100 ...)

Quando aggiungi " 42 " e "39" stai dicendo

4*10+2+3*10+9

Che equivale a

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

Ora da " 11 " non è un numero di una cifra valido, devi portarne 10 da uno, trasformandolo in un 1 al posto delle decine.

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

che è 81.

Quindi, perché ho parlato di questo piuttosto che della tua domanda sui numeri a 64 bit e sull'aritmetica a 32 bit? Perché in realtà sono esattamente gli stessi!

Una cifra varia da 0 a 9. Un "numero a 32 bit" varia da 0 a 2 ^ 32-1. (Supponendo che non sia firmato.)

Quindi, anziché lavorare nella base 10, lavoriamo nella base 2 ^ 32. Nella base 2 ^ 32, scriviamo 2 ^ 32 come 10. Se scrivi un numero a 64 bit nella base 2 ^ 32, sarebbe

(x)*10+y

dove xey sono simboli per numeri compresi tra 0 e 2 ^ 32-1. Quei simboli sono stringhe di bit.

Se si desidera aggiungere due numeri a 64 bit, suddividerli nella base 2 ^ 32 come:

 a_1*10+a_0
+b_1*10+b_0

Ora le aggiungi in base 2 ^ 32 esattamente come le aggiungi in base 10 - solo, invece di aggiungere usando l'aritmetica delle cifre che aggiungi usando l'aritmetica a 32 bit!

Come si divide un numero a 64 bit a in due numeri a 32 bit a_1 e a_0? Dividi a per 2 ^ 32. Non in virgola mobile, ma per intero - dove si ottiene un dividendo e un resto. Il dividendo è a_1, il resto è a_0.

Sfortunatamente ciò richiede un'aritmetica a 64 bit. Tuttavia, in genere a_1 è la metà più significativa di " di a, quindi, nella sintassi in stile C:

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

dove > > è un bit-shift giusto e & amp; è bit a bit e.

In genere, se non riesci a eseguire l'aggiunta a 64 bit, un "numero a 64 bit" saranno in realtà i due numeri a 32 bit a_1 e a_0. Non avrai un uint64_t se non puoi fare l'aritmetica di uint64_t!

Tutto questo presuppone che tu stia facendo un'aritmetica senza segno, ma gestire i segni è facile da qui.

Answer 3

Il codice C precedentemente pubblicato è inutilmente dettagliato:

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

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

if (c1 < a1)
    c2++;

Anche 'a1' in 'if' può essere sostituito con 'b1'. In caso di overflow, c1 sarà inferiore sia a1 che a b1.

Answer 4

Se i numeri a 64 bit sono (a ₂ , a ₁ ) e (b ₂ , b ₁ ), dove x ₂ sono i 32 bit alti considerati come non firmati e x ₁ è il valore basso 32 bit considerati come senza segno, quindi la somma dei due numeri è riportata di seguito.

c1 = a1 + b1

c2 = a2 + b2

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

Answer 5

sembra qualcosa del genere

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

L'hardware effettivo non utilizza 32 bit per aggiungere 16 bit alla volta, per l'aggiunta è necessario solo un ulteriore bit di carry e quasi tutte le CPU hanno un flag di stato carry per quando è stata traboccata un'operazione di addizione, quindi se si stanno usando una CPU a 32 bit, è possibile aggiungere operandi a 64 bit in due operazioni a 32 bit.

Answer 6

Praticamente ogni processore ha il bit carry e l'operazione add-with-carry, che ti interessano solo se stai programmando in assembly. Se stai usando un linguaggio più alto, il compilatore scarica le stesse operazioni add-with-carry. Il mio AVR-GCC mi ha dato questo quando ho aggiunto due numeri a 16 bit - l'AVR è a 8 bit - ma gli stessi concetti si applicherebbero a processori più alti.

Dato che i numeri sono nei registri R1: R2 e 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

Il risultato è memorizzato in R1: R2.