Dodawanie liczb 64-bitowych za pomocą arytmetyki 32-bitowej

Zastanów się, jak dodać dwie liczby dwucyfrowe za pomocą arytmetyki 1-cyfrowej.

 42
+39
---

Najpierw dodajesz prawą kolumnę. ("Jedynki" lub "jednostki"). 2+9 to 11. 11 "przepełniony" Twój 1 Cyfrowy arytmetyka, więc trzeba "nosić" 10.

 1
 42
+39
---
  1

Teraz dodajesz lewą kolumnę "dziesiątki", łącznie z dźwignią. 1+4+3=8.

 1
 42
+39
---
 81

8 jest mniejsza niż 10, więc nie ma przenoszenia. Jesteś skończony.

4*10+2

Lub, równoważnie,

4*10^1+2*10^0

(Kiedy mówię "a^b", jak "10^1", mam na myśli "a podniesiony do potęgi b '- tej": pomnożony przez siebie b razy. 10^0 to 1. 10^1 to 10. 10^2 to 10*10=100...)

Kiedy dodasz "42" i " 39 " mówisz

4*10+2+3*10+9

Co równa się

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

Teraz, ponieważ " 11 " nie jest poprawną liczbą jednocyfrową, musisz nosić 10 z jedynek, zmieniając ją w 1 w miejscu dziesiątek.

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

Czyli 81.

Więc dlaczego Mówiłem o tym, a nie o twoim pytaniu o liczby 64-bitowe i arytmetykę 32-bitową? Ponieważ są one rzeczywiście dokładnie takie same!

Cyfra waha się od 0 do 9. "Liczba 32 bitowa" waha się od 0 do 2^32-1. (Zakładając, że jest niepodpisany.)

Więc zamiast pracować w bazie 10, pracujmy w bazie 2^32. W bazie 2^32 zapisujemy 2^32 jako 10. Jeśli napiszesz 64-bitową liczbę w bazie 2^32, będzie to

(x)*10+y

Gdzie X i y są symbolami liczb od 0 do 2^32-1. Te symbole to bitstrings.

Jeśli chcesz dodać dwie liczby 64-bitowe, podziel je w bazie 2^32 jako:

 a_1*10+a_0
+b_1*10+b_0

Teraz dodajesz je w bazie 2^32 dokładnie tak samo jak dodajesz je w bazie 10 -- po prostu, zamiast dodawać używając arytmetyki cyfr, dodajesz używając arytmetyki 32 bitowej!

Jak podzielić 64-bitową liczbę a na dwie 32-bitowe liczby a_1 i a_0? Podziel a przez 2^32. Nie w postaci zmiennoprzecinkowej, ale całkowitej, gdzie otrzymujemy dywidendę i resztę. Dywidenda jest a_1, reszta to a_0.

Niestety wymaga to arytmetyki 64 bitowej. Jednak typowo a_1 jest "najważniejszą połową" a, więc w składni stylu C:

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

Gdzie > > jest Prawym bitshift i & jest bitowe i.

Zazwyczaj, jeśli nie można wykonać 64-bitowego dodawania," 64-bitowa liczba " będzie w rzeczywistości dwiema 32-bitowymi liczbami a_1 i a_0. Nie będziesz miał uint64_t, jeśli nie możesz wykonać arytmetyki uint64_t!

Wszystko to zakłada, że robisz unsigned arytmetyka, ale radzenie sobie ze znakami jest łatwe.

Wcześniej zamieszczony kod C jest zbędny:

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

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

if (c1 < a1)
    c2++;

"A1" w " if " można również zastąpić "b1". Przy przepełnieniu c1 będzie mniejszy niż zarówno a1, jak i b1.

Jeśli liczby 64-bitowe są (a₂,a₁) oraz (b₂,b₁), Gdzie x₂ czy wysokie 32 bity są brane jako niepodpisane i x₁ jest niskie 32 bity wzięte jako niepodpisane, to suma dwóch liczb jest podana poniżej.

c1 = a1 + b1

c2 = a2 + b2

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

Wygląda to tak

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

Rzeczywisty sprzęt nie używa 32 bitów, aby dodać 16 bitów na raz, tylko jeden dodatkowy bit przenoszenia jest kiedykolwiek potrzebny do dodania, a prawie wszystkie procesory mają flagę stanu przenoszenia, gdy operacja dodawania jest przepełniona, więc jeśli używasz 32-bitowego procesora, możesz dodać 64-bitowe operandy w dwóch, 32-bitowych operacjach.

Prawie każdy procesor ma operację carry bit I add-with-carry, na której zależy Ci tylko wtedy, gdy programujesz w assembly. Jeśli używasz wyższego języka, kompilator wyrzuca dokładnie te same operacje add-with-carry. Mój AVR-GCC dał mi to przy dodawaniu dwóch 16-bitowych numerów -- AVR jest 8-bitowy -- ale te same pojęcia dotyczą wyższych procesorów.

Podane liczby są w rejestrach R1: R2 i 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

Wynik jest zapisywany w R1: R2.