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

Question

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

Answer 1

Agregue primero los bytes menos significativos, mantenga el acarreo. Añadir los bytes más significativos teniendo en cuenta el acarreo del LSB:

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

Answer 2

Se podría añadir manualmente cada parte de 32 bits y cuidar el equipaje de mano.

Answer 3

Si los números de 64 bits son (a , un) y (b , b), donde x es el alto 32 bits tomados como unsigned y x son los 32 bits más bajos tomados como sin signo, a continuación se proporciona la suma de los dos números a continuación.

c1 = a1 + b1 

c2 = a2 + b2 

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

Answer 4

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

42 
+39 
--- 

Primero añada la columna de la derecha. (Los "unos" o "unidades"). 2 + 9 es 11. 11 "desbordados" de su aritmética 1 dígito, lo que tiene que "llevar" el 10.

1 
42 
+39 
--- 
    1 

Ahora se suman la columna izquierda "decenas", incluyendo el acarreo. 1 + 4 + 3 = 8.

1 
42 
+39 
--- 
81 

8 es menos de 10, por lo que no se puede llevar. Ya terminaste

¿Qué acaba de pasar? Cuando se dice que un número es "42" (en base 10) que realmente significa

4*10+2 

o, equivalentemente,

4*10^1+2*10^0 

(cuando digo "a^b", así como "10^1 ", me refiero a" un elevado al poder b'th ": a multiplicado por sí mismo b veces. 10^0 es 1. 10^1 es 10. 10^2 es 10 * 10 = 100 ...)

Cuando se agrega "42" y "39" que está diciendo

4*10+2+3*10+9 

lo que equivale a

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

Ahora bien, como "11" no es un número válido de un dígito, es necesario llevar a 10 de las que, 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.

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

Un dígito oscila entre 0 y 9. Un "número de 32 bits" va 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 base 2^32, escribimos 2^32 como 10. Si se 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 los números entre 0 y 2^32-1. Esos símbolos son bitstrings.

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

a_1*10+a_0 
+b_1*10+b_0 

Ahora añadirlos en base 2^32 de la misma manera que añadirlos en base 10 - ¡Simplemente, en lugar de agregar usando la aritmética de dígitos, agregue usando 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 por 2^32. No en coma flotante, sino de forma intergeneracional, donde obtienes un dividendo y un resto. El dividendo es a_1, el resto es a_0.

Desafortunadamente eso requiere una aritmética de 64 bit. Sin embargo, por lo general a_1 es el "medio más significativo" de una, por lo que, en la sintaxis de estilo C:

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

donde >> es una BitShift derecha y & 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 uint64_t arithmetic!

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

Answer 5

El código C previamente publicada es innecesariamente detallado:

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

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

if (c1 < a1) 
    c2++; 

El 'a1' en el 'si' puede ser sustituido con 'b1' también. En desbordamiento, c1 será menor que a1 y b1.

Answer 6

se ve algo como esto hardware real

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

no utiliza 32 bits para agregar 16 bits a la vez, sólo un poco más de acarreo está siempre necesaria para la adición, y casi todos los de la CPU tienen una indicador de estado de portador para cuando una operación de suma se desborda, por lo que si está utilizando una CPU de 32 bits, puede agregar operandos de 64 bits en dos operaciones de 32 bits.

Answer 7

Casi todos los procesadores tienen la operación de acarreo y complemento con carga, que solo se preocupan si está programando en ensamblaje. Si está utilizando un lenguaje más alto, el compilador volca exactamente las mismas operaciones add-with-carry. 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 a los procesadores superiores.

Dados los números están en 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.