Ajout de nombres 64 bits en utilisant l'arithmétique 32 bits

Question

Comment pouvons-nous ajouter deux nombres de 64 bits en utilisant l’arithmétique en 32 bits?

Answer 1

Ajoutez d'abord les octets les moins significatifs, conservez le report. Ajoutez les octets les plus significatifs en considérant le report des LSB:

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

Answer 2

Considérez comment vous ajoutez deux nombres à 2 chiffres en utilisant une arithmétique à 1 chiffre.

 42
+39
---

Vous ajoutez d’abord la colonne de droite. (Les "unités" ou "unités"). 2 + 9 est égal à 11. 11 "débordé" votre arithmétique à 1 chiffre, vous devez donc "transporter" les 10.

 1
 42
+39
---
  1

Maintenant, vous ajoutez la gauche "& dizaines; dizaines". colonne, y compris le carry. 1 + 4 + 3 = 8.

 1
 42
+39
---
 81

8 est inférieur à 10, donc pas de report. Vous avez terminé.

Qu'est-ce qui vient de se passer? Lorsque vous dites qu'un nombre est "42" (en base 10) vous voulez vraiment dire

4*10+2

Ou, de manière équivalente,

4*10^1+2*10^0

(quand je dis "a ^ b", comme "10 ^ 1", je veux dire "un surélevé au pouvoir": un multiplié par lui-même b fois. 10 ^ 0 est égal à 1. 10 ^ 1 vaut 10. 10 ^ 2 vaut 10 * 10 = 100 ...)

Lorsque vous ajoutez " 42 " et " 39 " vous dites

4*10+2+3*10+9

Qui est égal à

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

Maintenant depuis " 11 " n’est pas un nombre valide à un chiffre, vous devez en avoir 10, en le transformant en 1 à la place des dizaines.

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

qui est 81.

Alors, pourquoi ai-je parlé de cela plutôt que de votre question sur les nombres 64 bits et l’arithmétique 32 bits? Parce qu’ils sont en réalité exactement les mêmes!

Un chiffre va de 0 à 9. Un "nombre de 32 bits" varie de 0 à 2 ^ 32-1. (En supposant qu'il ne soit pas signé.)

Donc, plutôt que de travailler en base 10, travaillons en base 2 ^ 32. En base 2 ^ 32, nous écrivons 2 ^ 32 comme 10. Si vous écrivez un nombre de 64 bits en base 2 ^ 32, ce serait

(x)*10+y

où x et y sont des symboles pour des nombres compris entre 0 et 2 ^ 32-1. Ces symboles sont des chaînes de bits.

Si vous souhaitez ajouter deux nombres 64 bits, décomposez-les en base 2 ^ 32 comme suit:

 a_1*10+a_0
+b_1*10+b_0

Maintenant, vous les ajoutez en base 2 ^ 32 exactement de la même manière que vous les ajoutez en base 10 - plutôt que d’ajouter en utilisant l’arithmétique de chiffres que vous ajoutez en utilisant l’arithmétique de 32 bits!

Comment diviser un nombre 64 bits a en deux nombres 32 bits a_1 et a_0? Diviser a par 2 ^ 32. Pas en virgule flottante, mais dans le sens entier - où vous obtenez un dividende et un reste. Le dividende est a_1, le reste est a_0.

Malheureusement, cela nécessite une arithmétique 64 bits. Cependant, typiquement a_1 est la "moitié la plus significative". d'une syntaxe de style C:

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

où > > est un droit bitshift et & amp; est au niveau des bits et.

Généralement, si vous ne pouvez pas ajouter d’addition 64 bits, un "nombre 64 bits". seront en fait les deux nombres 32 bits a_1 et a_0. Vous n'aurez pas de uint64_t si vous ne pouvez pas utiliser l'arithmétique uint64_t!

Tout cela suppose que vous faites de l'arithmétique non signée, mais il est facile de gérer les signes à partir d'ici.

Answer 3

Le code C précédemment publié est inutilement commenté:

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

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

if (c1 < a1)
    c2++;

Le "a1" dans le "si" peut également être remplacé par "b1". En cas de débordement, c1 sera inférieur à a1 et à b1.

Answer 4

Si les nombres de 64 bits sont (a ₂ , a ₁ ) et (b ₂ , b ₁ ), où x ₂ est la valeur haute 32 bits considérés comme non signés et x ₁ est la valeur basse 32 bits considérés comme non signés, la somme des deux nombres est donnée ci-dessous.

c1 = a1 + b1

c2 = a2 + b2

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

Answer 5

ça ressemble à quelque chose comme ça

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

Le matériel actuel n'utilise pas 32 bits pour ajouter 16 bits à la fois, un seul bit supplémentaire de retenue est jamais nécessaire pour l'addition, et presque tous les processeurs ont un indicateur d'état de transport pour les cas de dépassement d'une opération d'ajout. utilisent un processeur 32 bits, vous pouvez ajouter des opérandes 64 bits en deux opérations 32 bits.

Answer 6

Pratiquement tous les processeurs disposent des fonctions de transfert et d’ajout-avec-transfert, qui ne vous intéressent que si vous programmez en assembleur. Si vous utilisez un langage plus élevé, le compilateur supprime exactement les mêmes opérations d'ajout avec transfert. Mon AVR-GCC me l'a dit lors de l'ajout de deux nombres de 16 bits - l'AVR est de 8 bits - mais les mêmes concepts s'appliqueraient aux processeurs supérieurs.

Étant donné que les nombres sont dans les registres R1: R2 et 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

Le résultat est stocké dans R1: R2.