Agregar números de 64 bits usando aritmética de 32 bits

Question

¿Cómo agregamos dos números de 64 bits usando aritmética de 32 bits?

Answer 1

Agregue los bytes menos significativos primero, mantenga el carry. Agregue los bytes más significativos considerando el acarreo de los LSB:

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

Answer 2

Considere cómo agrega dos números de 2 dígitos usando la aritmética de 1 dígito.

 42
+39
---

Primero agrega la columna derecha. (Las `` unidades '' o `` unidades ''). 2 + 9 es 11. 11 '' desbordado '' su aritmética de 1 dígito, por lo que debe "llevar" el 10.

 1
 42
+39
---
  1

Ahora sumas las decenas '' de la izquierda '' columna, incluido el carry. 1 + 4 + 3 = 8.

 1
 42
+39
---
 81

8 es menor que 10, por lo que no se lleva. Ya terminaste.

¿Qué acaba de pasar? Cuando dices que un número es " 42 " (en base 10) realmente quieres decir

4*10+2

O, equivalentemente,

4*10^1+2*10^0

(cuando digo "a ^ b", como "10 ^ 1", me refiero a "elevado a la potencia b": a multiplicado por sí mismo b veces. 10 ^ 0 es 1. 10 ^ 1 es 10. 10 ^ 2 es 10 * 10 = 100 ...)

Cuando agrega " 42 " y "39" estás diciendo

4*10+2+3*10+9

Que es igual

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

Ahora desde " 11 " no es un número válido de un dígito, debe llevar 10 de los mismos, convirtiéndolo en un 1 en el lugar de las decenas.

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

que es 81.

Entonces, ¿por qué he estado hablando de esto en lugar de su pregunta sobre números de 64 bits y aritmética de 32 bits? ¡Porque en realidad son exactamente lo mismo!

Un dígito varía de 0 a 9. A " número de 32 bits " varía de 0 a 2 ^ 32-1. (Suponiendo que no esté firmado.)

Entonces, en lugar de trabajar en la base 10, trabajemos en la base 2 ^ 32. En la base 2 ^ 32, escribimos 2 ^ 32 como 10. Si escribe un número de 64 bits en la base 2 ^ 32, sería

(x)*10+y

donde x e y son símbolos para números entre 0 y 2 ^ 32-1. Esos símbolos son cadenas de bits.

Si desea agregar dos números de 64 bits, desglosarlos en la base 2 ^ 32 como:

 a_1*10+a_0
+b_1*10+b_0

Ahora los agrega en la base 2 ^ 32 exactamente de la misma manera que los agrega en la base 10, solo que, en lugar de agregar con aritmética de dígitos, ¡agrega con aritmética de 32 bits!

¿Cómo se divide un número de 64 bits a en dos números de 32 bits a_1 y a_0? Divide a entre 2 ^ 32. No en coma flotante, sino en sentido entero, donde obtienes un dividendo y un resto. El dividendo es a_1, el resto es a_0.

Desafortunadamente, eso requiere aritmética de 64 bits. Sin embargo, típicamente a_1 es la mitad más significativa de a, entonces, en la sintaxis de estilo C:

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

donde > > es un desplazamiento de bits correcto y & amp; es bit a bit y.

Normalmente, si no puede agregar 64 bits, un " número de 64 bits " en realidad serán los dos números de 32 bits a_1 y a_0. ¡No tendrá un uint64_t si no puede hacer aritmética uint64_t!

Todo esto supone que estás haciendo aritmética sin signo, pero tratar con signos es fácil desde aquí.

Answer 3

El código C publicado anteriormente es innecesariamente detallado:

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

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

if (c1 < a1)
    c2++;

El 'a1' en 'if' también se puede reemplazar con 'b1'. En caso de desbordamiento, c1 será menor que a1 y b1.

Answer 4

Si los números de 64 bits son (a ₂ , a ₁ ) y (b ₂ , b ₁ ), donde x ₂ son los 32 bits altos tomados como sin signo, y x ₁ es el bajo 32 bits tomados como sin signo, a continuación se muestra la suma de los dos números.

c1 = a1 + b1

c2 = a2 + b2

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

Answer 5

se parece a esto

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

El hardware real no usa 32 bits para agregar 16 bits a la vez, solo se necesita un bit adicional de acarreo para agregar, y casi todas las CPU tienen un indicador de estado de acarreo para cuando una operación de adición se desborda, por lo que si están utilizando una CPU de 32 bits, puede agregar operandos de 64 bits en dos operaciones de 32 bits.

Answer 6

Casi todos los procesadores tienen la operación de bit de acarreo y add-with-carry, lo cual solo le importa si está programando en ensamblado. Si está utilizando un idioma superior, el compilador descarga exactamente las mismas operaciones de agregar con llevar. Mi AVR-GCC me dio esto al agregar dos números de 16 bits, el AVR es de 8 bits, pero los mismos conceptos se aplicarían para procesadores superiores.

Dado que los números están en los registros R1: R2 y 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

El resultado se almacena en R1: R2.