A adição de 64 bits números usando a versão de 32 bits aritmética

Question

Como podemos adicionar dois de 64 bits números usando a versão de 32 bits aritmética??

Answer 1

Adicione os bytes menos significativos primeiro, mantenha o transporte. Adicione os bytes mais significativos, considerando o transporte dos LSBs:

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

Answer 2

Considere como você adiciona dois números de 2 dígitos usando aritmética de 1 dígito.

 42
+39
---

Primeiro, você adiciona a coluna certa. (Os "outros" ou "unidades"). 2+9 é 11. 11 "transbordou" sua aritmética de 1 dígito, então você precisa "carregar" o 10.

 1
 42
+39
---
  1

Agora você adiciona a coluna "TENS" esquerda, incluindo o transporte. 1+4+3 = 8.

 1
 42
+39
---
 81

8 é menor que 10, então não carrega. Você Terminou.

O que acabou de acontecer? Quando você diz que um número é "42" (na base 10), você realmente quer dizer

4*10+2

Ou equivalente,

4*10^1+2*10^0

(Quando digo "a^b", como "10^1", quero dizer "um elevado ao b'th poder": um multiplicado por si mesmo B vezes. 10^0 é 1. 10^1 é 10. 10 ^2 é 10*10 = 100 ...)

Quando você adiciona "42" e "39", você está dizendo

4*10+2+3*10+9

Que é igual a

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

Agora, como o "11" não é um número válido de um dígito, você precisa transportar 10 a partir dos, transformando -o em 1 no Place Tens.

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

que é 81.

Então, por que tenho falado sobre isso em vez de sua pergunta sobre números de 64 bits e aritmética de 32 bits? Porque eles são realmente exatamente iguais!

Um dígito varia de 0 a 9. Um "número de 32 bits" varia de 0 a 2^32-1. (Supondo que não seja assinado.)

Então, em vez de trabalhar na base 10, vamos trabalhar na base 2^32. Na base 2^32, escrevemos 2^32 como 10. Se você escrever um número de 64 bits na base 2^32, seria

(x)*10+y

onde x e y são símbolos para números entre 0 e 2^32-1. Esses símbolos são bitsstrings.

Se você quiser adicionar dois números de 64 bits, divida -os na base 2^32 como:

 a_1*10+a_0
+b_1*10+b_0

Agora você os adiciona na base 2^32 exatamente da mesma maneira que você os adiciona na base 10 - apenas, em vez de adicionar o uso de aritmética de dígitos que você adiciona usando aritmética de 32 bits!

Como você divide um número de 64 bits em dois números de 32 bits A_1 e A_0? Divida A por 2^32. Não em ponto flutuante, mas inteiro - onde você obtém um dividendo e um restante. O dividendo é A_1, o restante é A_0.

Infelizmente, isso requer aritmético de 64 bits. No entanto, normalmente A_1 é a "metade mais significativa" de A, então, na sintaxe do estilo C:

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

onde >> é um desvio de bits certo e é bit -netwise e.

Normalmente, se você não pode fazer adição de 64 bits, um "número de 64 bits" será na verdade os dois números de 32 bits A_1 e A_0. Você não terá um UINT64_T se não pode fazer UINT64_T aritmética!

Tudo isso pressupõe que você está fazendo aritmética não assinada, mas lidar com sinais é fácil a partir daqui.

Answer 3

O código C publicado anteriormente é desnecessariamente detalhado:

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

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

if (c1 < a1)
    c2++;

O 'A1' no 'If' também pode ser substituído por 'B1'. No transbordamento, o C1 será menor que o A1 e o B1.

Answer 4

Se os números de 64 bits são (a₂,uma₁) e B₂, b₁), Onde x₂ são os 32 bits altos tomados como não assinados, e x₁ são os 32 bits baixos tomados como não assinados, então a soma dos dois números é dada abaixo.

c1 = a1 + b1

c2 = a2 + b2

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

Answer 5

parece algo assim

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

O hardware real não usa 32 bits para adicionar 16 bits por vez, apenas um pedaço extra de transporte é necessário para adição, e quase todos os CPUs têm um sinalizador de status de transporte para quando uma operação de adição transbordada; portanto, se você estiver usando um CPU de 32 bits, você pode adicionar operando de 64 bits em duas operações de 32 bits.

Answer 6

Praticamente cada processador tem o bit de transporte e o suplemento de com-operação de transporte, que você só se preocupam se você está programando em assembly.Se você estiver usando uma maior língua, o compilador despeja o exato mesmo adicionar-com-realizar operações.Meu AVR-GCC me deu isso quando a adição de dois de 16 bits números: o AVR 8-bit--mas os mesmos conceitos, seria aplicável para processadores superiores.

Tendo em conta os números estão em registradores 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

O resultado é armazenado em R1:R2.