Jak działa arytmetyka dwójkowa: liczby całkowite w uzupełnieniu do dwóch i liczby IEEE-754

Każda operacja liczbowa, którą wykonuje Twój program — a + b, x * y, count / 2 — ostatecznie staje się ciągiem operacji bitowych na układach bitów. A to, jak te operacje bitowe zamieniają się w poprawny wynik arytmetyczny, zależy całkowicie od tego, jakiego kodowania używają bity.

Dla liczb całkowitych komputery używają uzupełnienia do dwóch — pięknie prostego schematu, w którym dodawanie ze znakiem korzysta z dokładnie tego samego układu sprzętowego co dodawanie bez znaku: bity nie wiedzą ani nie dbają o to, czy miałeś je na myśli jako liczby ze znakiem. Dla ułamków komputery używają zmiennego przecinka IEEE-754 — znacznie bardziej wymyślnej maszynerii z osobnymi polami znaku, wykładnika i mantysy, które trzeba wyrównywać i zaokrąglać przy każdej operacji.

Ten artykuł przechodzi przez arytmetykę obu — co faktycznie dzieje się z bitami przy dodawaniu, odejmowaniu, mnożeniu i dzieleniu w każdym formacie, gdzie operacje się załamują i jak te dwa systemy się porównują. Sama strona kodowania każdego formatu opisana jest w artykułach siostrzanych:

• Kod z przesunięciem kontra uzupełnienie do dwóch: dwa sposoby reprezentowania liczb ze znakiem — jak uzupełnienie do dwóch (i jego kuzyn, kod z przesunięciem) kodują wartości ze znakiem.
• Jak Number w JavaScripcie i float w Pythonie przechowują liczby — jak IEEE-754 upakowuje znak, wykładnik i mantysę w 64 bity.

Tutaj skupiamy się wyłącznie na samych operacjach arytmetycznych, z krótkimi przypomnieniami kodowania tam, gdzie to potrzebne.

Arytmetyka liczb całkowitych w uzupełnieniu do dwóch

Założymy, że podstawy kodowania już znasz — najbardziej znaczący bit (MSB) nosi wagę ujemną, aby zmienić znak liczby, odwracasz jej bity i dodajesz 1, a zakres jest asymetryczny o jeden (od -8 do +7 na 4 bitach albo od -2 147 483 648 do +2 147 483 647 na 32 bitach). Jeśli coś z tego jest nieznane, pełne omówienie znajduje się w artykule o kodzie z przesunięciem kontra uzupełnieniu do dwóch. Przykłady 4-bitowe użyte poniżej są tylko zastępnikiem dla dowolnej szerokości n bitów.

Dodawanie i odejmowanie: tak samo jak bez znaku

Pierwsza piękna własność uzupełnienia do dwóch: dodawanie ze znakiem korzysta z tego samego fizycznego układu co dodawanie bez znaku. Uzupełnienie do dwóch przechowuje każdą liczbę ujemną $x$ przy użyciu takiego układu bitów, który — czytany bez znaku — równa się $x + 2^n$; na przykład na 4 bitach ($n = 4$) liczba $-3$ przechowywana jest jako układ dla 13: $x + 2^n = -3 + 2^4 = -3 + 16 = 13$, czyli 1101 dwójkowo. Z tego powodu dodanie liczby ujemnej do dodatniej często przepełnia $n$-bitowy rejestr, ale sprzęt po prostu odrzuca przeniesienie wyjściowe — a odpowiedź ze znakiem wypada sama.

Zobaczmy dodawanie liczby ujemnej w działaniu. Prześledźmy -3 + 5 na 4 bitach — -3 jest zakodowane jako 1101 (= 13), 5 to 0101:

    1 1 0 1     (-3, przechowywane jako 13)
  + 0 1 0 1     (+5)
  ─────────
  1 0 0 1 0     (= 18; nie mieści się na 4 bitach — wiodąca 1 to przeniesienie, waga 2^4 = 16)
    0 0 1 0     (zostaje w 4-bitowym rejestrze: 2)  ✓ zgadza się z -3 + 5 = 2

Sprzęt po prostu dodał układy bitów bez znaku 13 + 5 = 18. Bit przeniesienia na 5. pozycji (waga $2^4 = 16$) nie zmieścił się w 4-bitowym rejestrze i został odrzucony. Te odrzucone 16 to dokładnie część $+2^n$ ze wzoru $x + 2^n$, który widzieliśmy wyżej — przesunięcie kodowania i przepełnienie znoszą się, a odpowiedź ze znakiem wychodzi za darmo. Teraz po prostu interpretujemy te bity jako liczbę ze znakiem, podczas gdy maszyneria sprzętowa nie robi tu żadnego rozróżnienia. Ta sama logika obejmuje przypadki bez przepełnienia: -7 + 4 to 1001 + 0100 = 1101, co dekoduje się jako -3 (ze znakiem) albo 13 (bez znaku).

Ponieważ odejmowanie to po prostu dodanie liczby przeciwnej, nie potrzebuje ono osobnego układu: a - b = a + (-b), gdzie zmiana znaku to przepis „odwróć bity i dodaj 1”. Dla 5 - 3: -3 to 1101, więc 0101 + 1101 = 10010. Wiodący bit na 4 bitach odpada, zostaje 0010 = 2 — a ten odrzucony bit to modularne przewinięcie. Pełne ujęcie ($n$-bitowa arytmetyka jako okrąg z $2^n$ pozycjami) omówione jest w sekcji o arytmetyce modularnej w artykule o kodowaniu.

Mechanizm modulo $2^n$ prowadzi do następującej obsługi przepełnień: INT_MAX + 1 = INT_MIN, a INT_MIN - 1 = INT_MAX — to nie błąd, tylko modularny krok przecinający szew między połową dodatnią i ujemną. Zauważ, że INT_MAX i INT_MIN to nazwy z C/C++ dla skrajnych wartości 32-bitowych ze znakiem, $2^{31} - 1$ i $-2^{31}$; Java ma Integer.MAX_VALUE/MIN_VALUE, Rust ma i32::MAX/MIN. Python i JavaScript ich nie mają, bo ich typy całkowite mają dowolną precyzję.

Porównywanie: gdzie same bity nie wystarczą

W przeciwieństwie do dodawania porównywanie już zależy od interpretacji. Układ bitów 1111 to 15 bez znaku, więc naturalnie 1111 > 0001 (15 > 1). Jednak jeśli te same bity mają być liczbą ze znakiem -1, poprawną odpowiedzią jest -1 < 1 — a porównanie na poziomie bitów nadal daje 1111 > 0001. Te same bity, przeciwne odpowiedzi.

Na poziomie sprzętu porównywanie często zrealizowane jest jako odejmowanie: procesor oblicza a - b i ustawia flagi (znak, zero, przepełnienie, przeniesienie); instrukcje skoku czytają potem te flagi, by zdecydować o wyniku skoku. Samo odejmowanie korzysta z tego samego mechanizmu a + (-b) z góry — procesor po prostu odrzuca wynik i zachowuje tylko flagi. Kilka 4-bitowych przykładów, by zobaczyć każdą flagę w działaniu:

 5 - 3:   0101 - 0011 = 0010    carry=0, sign=0, zero=0, overflow=0
 3 - 5:   0011 - 0101 = 1110    carry=1, sign=1, zero=0, overflow=0    (= -2 ze znakiem)
 5 - 5:   0101 - 0101 = 0000    carry=0, sign=0, zero=1, overflow=0
-8 - 1:   1000 - 0001 = 0111    carry=0, sign=0, zero=0, overflow=1    (= -9, nie mieści się)

Weź pierwszy wiersz, 5 - 3 = 2, gdzie każda flaga jest 0: carry = 0, bo odejmowanie bez znaku zostaje w zakresie (5 ≥ 3); sign = 0, bo MSB wyniku (0010) to 0; zero = 0, bo wynik jest niezerowy; overflow = 0, bo +2 mieści się bez trudu w 4-bitowym zakresie ze znakiem. Pozostałe wiersze przełączają po jednej fladze: carry zapala się, gdy odejmowanie bez znaku przewija się poniżej zera (wiersz 2: 3 < 5, więc wynik jest zapisem liczby ujemnej w uzupełnieniu do dwóch); sign zapala się, gdy MSB wyniku to 1 (1110 z wiersza 2); zero zapala się, gdy operandy były równe (wiersz 3); overflow zapala się, gdy wynik ze znakiem wypada spoza 4-bitowego zakresu ze znakiem (wiersz 4: -8 - 1 = -9 schodzi poniżej minimum -8).

Ponieważ te same bity mogą znaczyć coś innego ze znakiem i bez znaku, procesory udostępniają dwie rodziny instrukcji skoku — ze znakiem (JL, JG na x86 — „skocz, jeśli mniejsze/większe”) i bez znaku (JB, JA — „skocz, jeśli poniżej/powyżej”) — z których każda czyta inną kombinację flag:

W tych warunkach ⊕ to logiczne XOR (dokładnie jedno wejście jest 1), ∧ to logiczne AND (oba wejścia są 1), a ∨ to logiczne OR (co najmniej jedno wejście jest 1). Kompilator wybiera właściwy wariant na podstawie zadeklarowanego typu.

W działaniu, znowu na 4 bitach (warunek flagowy każdego wiersza jest spełniony, więc skok następuje):

  JB  (1 < 2  bez zn.):    0001 - 0010 = 1111    carry = 1
  JA  (3 > 2  bez zn.):    0011 - 0010 = 0001    carry = 0, zero = 0
  JL  (-1 < 1 ze zn.):     1111 - 0001 = 1110    sign ⊕ overflow = 1 ⊕ 0 = 1
  JG  (3 > 2  ze zn.):     0011 - 0010 = 0001    sign ⊕ overflow = 0 ⊕ 0 = 0, zero = 0

Prawa strona każdego wiersza czyta się jako wzór → podstawione wartości flag → wynik logiczny. Weź wiersz JL: odejmowanie 1111 - 0001 = 1110 ma sign = 1 (MSB wyniku) i overflow = 0 (wartość ze znakiem -2 nadal mieści się na 4 bitach), więc sign ⊕ overflow staje się 1 ⊕ 0, co daje 1 — warunek zapłonu JL. Wiersz JG działa tak samo z sign = 0 i overflow = 0, dając 0 ⊕ 0 = 0 (plus zero = 0), co jest warunkiem zapłonu JG.

Równość (a == b, instrukcja JE) i jej negacja (JNE) czytają tylko flagę zera i są identyczne dla liczb ze znakiem i bez znaku.

Mnożenie: przesuwaj i dodawaj

Przypomnij sobie mnożenie pisemne ze szkoły: dla każdej cyfry jednego operandu mnożysz ją przez drugi operand, przesuwasz powstały wiersz o pozycję tej cyfry i sumujesz wszystkie wiersze. Na przykład 123 × 456:

        1 2 3              (a = 123)
      × 4 5 6              (b = 456)
      ─────────
        7 3 8              ← 123 × 6 (6 jest na pozycji 0, brak przesunięcia)
      6 1 5                ← 123 × 5, przesunięte o jedną pozycję w lewo (5 na pozycji 1)
    4 9 2                  ← 123 × 4, przesunięte o dwie pozycje w lewo (4 na pozycji 2)
    ─────────
    5 6 0 8 8              = 56088

Dwójkowo działa to tak samo, ale z jednym wielkim uproszczeniem: każda cyfra mnożnika to albo 0, albo 1. Więc każdy wiersz jest albo przesuniętą kopią mnożnej a (gdy bit mnożnika to 1), albo po prostu zerem (gdy bit to 0) — bez kroku mnożenia cyfra po cyfrze jak w systemie dziesiętnym. To tak, jakby każde mnożenie odbywało się przeciw liczbie dziesiętnej, której cyframi są tylko 1 i 0 — jak 25 × 101:

        2 5               (a = 25)
      × 1 0 1             (b = 101)
      ─────────
        2 5               ← cyfra 0 = 1: dodaj 25
      0 0                 ← cyfra 1 = 0: pomiń
    2 5                   ← cyfra 2 = 1: dodaj 25 przesunięte o 2 w lewo (= 2500)
    ─────────
    2 5 2 5               = 2525

Zauważ, że nie ma tu żadnego prawdziwego mnożenia cyfr — każdy wiersz to albo 25 przesunięte na swoją pozycję, albo po prostu 0. A samo przesunięcie to tylko dopełnianie zerami z dolnej strony: 25 przesunięte o 2 w lewo to 2500, z dwoma dopisanymi zerami (dwójkowo to samo przesunięcie zamienia 0011 w 1100). Cała operacja redukuje się więc do „albo dodaj dopełnioną zerami kopię a, albo pomiń”. To ta własność czyni mnożenie dwójkowe tak tanim: dwójkowo mnożnik ma cyfry zawsze z {0, 1}, więc każdy wiersz zapada się do tego samego wyboru „przesuń albo zero”, niezależnie od operandu.

Oto 3 × 5 (0011 × 0101) na 4 bitach, przepuszczone przez ten sam algorytm:

        0 0 1 1           (a = 3)
      × 0 1 0 1           (b = 5)
      ─────────
        0 0 1 1           ← bit 0 = 1: dodaj a
      0 0 0 0             ← bit 1 = 0: pomiń
    0 0 1 1               ← bit 2 = 1: dodaj a ≪ 2
  0 0 0 0                 ← bit 3 = 0: pomiń
  ─────────────────
  0 0 0 0 1 1 1 1         = 15

Układ wiersz po wierszu sugeruje n sekwencyjnych kroków — ale procesor nie potrzebuje ich sekwencyjnie. Każdy wiersz zależy tylko od a i jednego bitu b, a nie od wyniku któregokolwiek poprzedniego wiersza, więc wszystkie n wierszy da się obliczyć równolegle. Aby wyprodukować wiersz i, sprzęt przesuwa a w lewo o i (pozycja tego wiersza), a potem albo zachowuje przesuniętą wartość (jeśli b[i] to 1), albo zamienia ją na same zera (jeśli b[i] to 0). n iloczynów częściowych sumuje potem równoległe drzewo sumatorów (Wallace’a albo Dadda), co zajmuje $O(\log n)$ opóźnienia bramek — w przeciwieństwie do $O(n)$ cykli u szeregowego mnożnika typu przesuń-i-dodaj.

W sprzęcie staje się to równoległym drzewem: b rozszczepia się na swoje bity, każdy bit to gałąź, a każda gałąź decyduje 0 albo 1. Jeśli 1, ta gałąź wnosi a przesunięte o swoją pozycję; jeśli 0, wnosi zero. Wszystkie gałęzie działają równolegle, a potem drzewo sumatorów je sumuje.

Dla a = 0011 (= 3), b = 0101 (= 5) proces obliczeń wygląda tak:

              a = 0011 (rozsyłane do każdej gałęzi)
              │
  ┌───────────┼───────────┬───────────┬───────────┐
  │           │           │           │           │
  ▼           ▼           ▼           ▼
a ≪ 0       a ≪ 1       a ≪ 2       a ≪ 3            ← przesunięcie o indeks gałęzi
= 00000011  = 00000110  = 00001100  = 00011000        (wynik w polu 8-bitowym)
  │           │           │           │
  × b₀=1      × b₁=0      × b₂=1      × b₃=0          ← bramkowanie tym bitem b
  │           │           │           │                 (jeśli bᵢ=0, wyjście = 0;
  ▼           ▼           ▼           ▼                 jeśli bᵢ=1, wyjście = a≪i)
00000011    00000000    00001100    00000000
(partial₀)  (partial₁)  (partial₂)  (partial₃)
  │           │           │           │
  └───────────┴─────┬─────┴───────────┘
                    │
                    ▼
       ┌────────────────────────────┐
       │  parallel adder tree       │   ← głębokość bramek O(log n)
       │  sum = 00001111 = 15       │
       └──────────────┬─────────────┘
                      │
                      ▼
                  P = 00001111 = 15                ← iloczyn 2n-bitowy (= a × b)

Jest praktyczna pułapka, o której warto wiedzieć — mnożenie może po cichu się przepełnić, nawet gdy operandy są nigdzie blisko maksimum typu. To dlatego, że iloczyn potrzebuje $2n$ bitów, nie $n$: dla 4 bity × 4 bity największy iloczyn to $15 \times 15 = 225 = \texttt{11100001}$, co wylewa się na 8 bitów; dla 8 bitów × 8 bitów $255 \times 255 = 65{,}025$ potrzebuje 16 bitów. Różne języki radzą sobie z tym różnie:

Mnożenie ze znakiem

W przeciwieństwie do dodawania, mnożenie dla liczb ze znakiem i bez znaku nie działa tak wprost z tym samym algorytmem. To dlatego, że w uzupełnieniu do dwóch MSB mnożnika nosi wagę ujemną — więc gdy jest 1, wkład tego wiersza należy odjąć, a nie dodać. Na przykład przy b = 1110 i a = 3: czytane bez znaku, b = 14 i wszystkie wiersze są dodawane (0 + 6 + 12 + 24 = 42, co zgadza się z 3 × 14); czytane ze znakiem, b = -2 i wiersz MSB jest zamiast tego odejmowany (0 + 6 + 12 − 24 = -6, co zgadza się z 3 × -2). Te same bity operandu, u jednego wiersza odwrócony znak.

Potrzeba więc kilku poprawek do algorytmu powyżej: odejmuj (a nie dodawaj) iloczyn częściowy dla wiersza bitu znaku i rozszerzaj znakowo każdy iloczyn częściowy do pełnej szerokości $2n$ bitów, by ujemne wkłady propagowały się poprawnie do górnej połowy. Przepuszczamy 3 × -2 (0011 × 1110) przez ten przepis:

        0 0 1 1                  (a = 3)
      × 1 1 1 0                  (b = -2 ze znakiem)
      ─────────
  0 0 0 0 0 0 0 0    ← bit 0 = 0: pomiń
  0 0 0 0 0 1 1 0    ← bit 1 = 1: dodaj a ≪ 1
  0 0 0 0 1 1 0 0    ← bit 2 = 1: dodaj a ≪ 2
  1 1 1 0 1 0 0 0    ← bit 3 = 1 (MSB!): odejmij a ≪ 3 (= -24, w 8-bitowym uzupełnieniu do dwóch)
  ─────────────────
  1 1 1 1 1 0 1 0    = -6 (ze znakiem)  ✓

Rozejście się wersji ze znakiem i bez znaku żyje całkowicie w górnych $n$ bitach pełnego iloczynu $2n$-bitowego — dolne $n$ bitów jest takie samo w obu przypadkach. Na przykład, z tymi samymi bitami operandów 0011 × 1110:

  bez zn. (3 × 14 = 42):    0 0 1 0  |  1 0 1 0
  ze zn.  (3 × -2 = -6):    1 1 1 1  |  1 0 1 0
                            ───────     ───────
                            górne n     dolne n
                            (różnią)    (identyczne)

Dlatego mnożenie o tej samej szerokości (int * int → int) nie potrzebuje osobnych wariantów ze znakiem i bez znaku na poziomie języka: to po prostu dolne n bitów, które przy przepełnieniu przewijają się jak przy dodawaniu (bez szczególnego patologicznego przypadku w rodzaju INT_MIN / -1, jaki ma dzielenie).

Dzielenie: przesuwaj i odejmuj

Spójrzmy teraz na dzielenie. Na poziomie bitów nie ma w nim nic egzotycznego — to po prostu dzielenie pisemne zastosowane do postaci dwójkowej. Przypomnij sobie szkolne dzielenie pisemne, powiedzmy 105 ÷ 7:

      1 5
    ─────
7 │ 1 0 5
      7
    ─────
      3 5
      3 5
    ─────
        0

Aby obliczyć, idziemy po cyfrach dzielnej (105) od lewej do prawej. Na każdym kroku pytamy „ile razy dzielnik (7) mieści się w tym, co mamy dotąd?”, odejmujemy tyle razy, sprowadzamy następną cyfrę i powtarzamy.

Dzielenie dwójkowe działa dokładnie tak samo, tylko pytanie „ile razy?” ma jedynie dwie możliwe odpowiedzi: 0 albo 1 — dzielnik mieści się albo raz, albo wcale. To jest kluczowe uproszczenie. W systemie dziesiętnym każdy krok wymaga rzeczywistego obliczenia (albo oszacowania), by przyszpilić cyfrę od 0 do 9 — trzeba ustalić, ile dzielnika się mieści, co w ogólności wymaga mnożenia i prób z błędami.

W systemie dwójkowym nie ma nic do obliczania: jedno porównanie bieżącej reszty z dzielnikiem daje odpowiedź wprost — 1, jeśli dzielnik się mieści, 0, jeśli nie. Żadnej tabliczki mnożenia, żadnych prób — tylko jedna decyzja „odejmij albo nie” na każdy bit. Dlatego dwójkowe dzielenie pisemne tak czysto odwzorowuje się na sprzęt: pętla nadrzędna iteruje po bitach dzielnej, a każda iteracja to tylko komparator i warunkowe odejmowanie — nic więcej.

A z sekcji o porównywaniu przypomnij sobie, że komparator zrealizowany jest jako odejmowanie: R ≥ D to po prostu R − D ze sprawdzeniem flagi znaku lub przeniesienia. Więc na każdej iteracji pętli sprzęt spekulatywnie obliczą R − D: jeśli wynik jest nieujemny (brak pożyczki), zatwierdza go z powrotem do R i zapisuje 1 w Q; w przeciwnym razie odrzuca wynik i zapisuje 0. Jedno odejmowanie na iterację, zawsze.

Procesor trzyma dwa rejestry: R przechowuje bieżącą resztę, Q gromadzi iloraz bit po bicie. Na każdym kroku przesuwa R w lewo i wprowadza następny bit dzielnej, a potem porównuje R z D, zawsze obliczając R − D. W zależności od wyniku:

• jeśli R − D jest nieujemne (D się mieści) → ustawia nowy bit Q na 1 i zamienia R na ten wynik
• jeśli R − D jest ujemne (D się nie mieści) → ustawia nowy bit Q na 0, odrzuca wynik i zostawia R bez zmian

Zobaczmy przykład: 13 ÷ 3 na 4 bitach, dzielna $13_{10} = 1101_2$, dzielnik $3_{10} = 0011_2$. Przejdź krok po kroku przez widżet poniżej, by zobaczyć oba przedstawienia równolegle — szkolne dzielenie pisemne po lewej i ślad rejestrów przesuwnych procesora po prawej. Widżet pokazuje cztery wiersze rejestrów: Ds to dzielnik (to, co w tekście nazywaliśmy D), Dd to dzielna, R to bieżąca reszta, a Q to iloraz budowany bit po bicie. Model mentalny: Dd to wejściowy strumień bitów podawany do R (na każdym takcie wsuwa się następny bit dzielnej); Ds to nieruchome odniesienie, z którym porównywane jest R; R i Q to rejestry robocze, oba przesuwane w lewo na każdym takcie.

Widżet powyżej ma 14 stanów — jednolitą strukturę 3 podetapów na takt (przesuń R, porównaj/odejmij, przesuń Q). Ślad poniżej odzwierciedla tekst kroków pokazywany w panelu informacyjnym widżetu:

Step 0   — Init. Ds = 0011 (3), R = 0000, Q = 0000.

Takt 1 — bit 3 = 1 (brak odejmowania)
    Step 1   — (a) przesuń R: wsunięty bit 3 → R = 0001. Jeszcze bez porównania.
    Step 2   — (b) porównanie: 1 < 3 → brak odejmowania. Podświetlona gałąź „R < D".
    Step 3   — (c) przesuń Q: Q = 0000. Pierwsza cyfra ilorazu = 0.

Takt 2 — bit 2 = 1 (odejmowanie się odpala)
    Step 4   — (a) przesuń R: wsunięty bit 2 → R = 0011 (pośrednie, widoczne).
    Step 5   — (b) porównanie: 3 ≥ 3 → podświetlona gałąź „R ≥ D"; odejmowanie nastąpi przy następnym kliknięciu.
    Step 6   — (c) odejmowanie + przesuń Q: R = 0011 − 0011 = 0000; Q = 0001. Po stronie szkolnej pojawia się wiersz „1 1".

Takt 3 — bit 1 = 0 (brak odejmowania)
    Step 7   — (a) przesuń R: wsunięty bit 1 → R = 0000.
    Step 8   — (b) porównanie: 0 < 3 → brak odejmowania.
    Step 9   — (c) przesuń Q: Q = 0010. Trzecia cyfra ilorazu = 0.

Takt 4 — bit 0 = 1, LSB (brak odejmowania)
    Step 10  — (a) przesuń R: wsunięty bit 0 → R = 0001.
    Step 11  — (b) porównanie: 1 < 3 → brak odejmowania.
    Step 12  — (c) przesuń Q: Q = 0100. Czwarta cyfra ilorazu = 0.

Step 13  — Done. Q = 0100 (= 4), R = 0001 (= 1). 13 ÷ 3 = 4 reszty 1.

Po n krokach (po jednym na bit) masz pełny iloraz. Jakiekolwiek Q i R procesor osiągnie na końcu przebiegu, spełniają one z konstrukcji ścisłą tożsamość:

Ta tożsamość nie jest dodatkową regułą — to definicja reszty: R jest tym, co zostaje po tym, jak pętla odjęła D tyle razy, ile było możliwe. Uzyskane przez widżet Q = 4, R = 1 to trywialne sprawdzenie: 4 · 3 + 1 = 13. Przesuń-i-odejmij produkuje zarówno a / b, jak i a % b w jednym przebiegu — oba wyniki wypadają razem.

Implementacje zachowują tę tożsamość wszędzie tam, gdzie Q i R oba mieszczą się w rejestrze. Gdy prawdziwy iloraz nie jest liczbą całkowitą, trzeba go zaokrąglić — a języki podchodzą do tego dwojako:

• Obcięcie w stronę zera (C99/C++, Rust, Java, Go): a / b zaokrągla w stronę zera; reszta dziedziczy znak dzielnej.
• Dzielenie z podłogą (Python): a // b zaokrągla w stronę $-\infty$; reszta dziedziczy znak dzielnika.

Przykład z a = -17, b = 5 (prawdziwy iloraz to $-3.4$):

C:       -17 / 5  = -3     -17 % 5 = -2    (-3) * 5 + (-2) = -17   ✓
Python:  -17 // 5 = -4     -17 % 5 =  3    (-4) * 5 +  3   = -17   ✓

Oba spełniają tożsamość; różnią się tylko kierunkiem zaokrąglenia. Powyższy algorytm przesuń-i-odejmij produkuje dzielenie z obcięciem wprost — operuje na wartościach bezwzględnych i przywraca znak na granicy. Dzielenie z podłogą to mała poprawka po fakcie: jeśli znaki operandów się różnią, a reszta jest niezerowa, zmniejsz iloraz o 1 i dodaj b do reszty.

Jak właśnie widzieliśmy, algorytm przesuń-i-odejmij wykonuje jedną iterację pętli na bit, co czyni dzielenie całkowite operacją O(n) dla liczb n-bitowych — zauważalnie wolniejszą od dodawania czy mnożenia, dlatego nawet nowoczesne procesory zużywają wiele cykli na instrukcję idiv. Prostsze architektury czasem realizują je pętlą programową, a nie dedykowanym sprzętem, natomiast nowoczesne procesory rezygnują ze zwykłego przesuń-i-odejmij na rzecz szybszych algorytmów — dzielenia SRT, Newtona–Raphsona i Goldschmidta — które redukują dzielenie do garści mnożeń, bo mnożenie jest w sprzęcie znacznie tańsze.

Dzielenie ze znakiem to ten sam algorytm uruchomiony na wartościach bezwzględnych operandów, ze poprawkami znaków przed i po pętli — iloraz zmienia znak, jeśli dokładnie jeden operand był ujemny, a reszta przyjmuje znak dzielnej (C/C++) albo dzielnika (Python).

Działa to czysto dla każdej pary — z wyjątkiem jednego przypadku brzegowego.

Jedyne dzielenie ze znakiem, które się przepełnia

Przepełnienia przy dodawaniu są naprawialne w tym sensie, że przewinięcie jest dobrze zdefiniowane. Ale w uzupełnieniu do dwóch istnieje dokładnie jedna operacja arytmetyczna, która nie ma żadnej sensownej odpowiedzi: dzielenie wartości minimalnej przez -1.

To dokładnie INT_MAX + 1, czyli (2^31 − 1) + 1 = 2^31, o jeden powyżej największej reprezentowalnej wartości ze znakiem. Wyniku literalnie nie da się przedstawić żadnym 32-bitowym układem bitów w uzupełnieniu do dwóch. Nie ma przewinięcia, które dałoby właściwą odpowiedź — $2^{31}$ po prostu nie istnieje w tym formacie.

To bezpośrednia konsekwencja zakresu asymetrycznego o jeden. Każda liczba całkowita ujemna poza INT_MIN ma pasującą dodatnią; INT_MIN jest jedynym wyjątkiem. Próba zmiany jej znaku (przez jednoargumentowy - albo przez dzielenie przez -1) prosi o wartość, której format nie potrafi wyprodukować.

Różne systemy obchodzą się z tym różnie:

Wszystkie muszą dokonać wyboru, bo odpowiedź matematyczna po prostu nie mieści się w układzie bitów — nie ma tu dobrze zachowującego się wyjścia awaryjnego.

Arytmetyka liczb IEEE-754

Arytmetyka zmiennoprzecinkowa to całkiem inne zwierzę. Zamiast czystego modularnego świata uzupełnienia do dwóch IEEE-754 daje Ci siatkę wartości reprezentowalnych, której odstęp podwaja się przy każdym wzroście wykładnika — gęsto blisko zera, rzadko blisko skrajności. Każda operacja musi wyrównać wykładniki, wykonać właściwą matematykę, ponownie znormalizować wynik i zaokrąglić go tak, by zmieścił się w mantysie.

Założymy, że układ IEEE-754 binary64 już znasz — 1 bit znaku, 11 bitów wykładnika z przesunięciem, 52 bity mantysy, niejawna wiodąca 1. Jeśli to nowość, pełny rozkład jest w artykule o tym, jak Number w JavaScripcie i float w Pythonie przechowują liczby. Tutaj podejmujemy tam, gdzie ten artykuł się kończy — format jest ustalony; teraz co się dzieje, gdy wykonasz arytmetykę na dwóch takich liczbach.

Wszystkie cztery operacje arytmetyczne mają ten sam szkielet: każde z trzech pól (znak, wykładnik, mantysa) obsługiwane jest osobno, a potem wynik jest normalizowany (przymuszany z powrotem do postaci 1.xxx × 2^e) i zaokrąglany tak, by zmieścić się w 52 bitach mantysy.

Dla mnożenia i dzielenia operandy są już w postaci 1.xxx × 2^e, więc operacja biegnie wprost: znaki są XOR-owane, wykładniki dodawane (mnożenie) albo odejmowane (dzielenie), a mantysy mnożone albo dzielone. Trzy kroki: operacja → normalizacja → zaokrąglenie.

Dla dodawania i odejmowania jest dodatkowy krok wstępny — wyrównanie — bo dodawanie wartości wymaga, by były w tej samej skali. Mantysa mniejszego operandu jest przesuwana w prawo, aż oba wykładniki się zgodzą, i tylko wtedy mantysy są łączone; znak wyniku bierze się z operandu o większej wartości bezwzględnej. Cztery kroki: wyrównanie → operacja → normalizacja → zaokrąglenie.

Przejdźmy teraz przez każdą operację szczegółowo, zaczynając od dodawania.

Dodawanie: wyrównaj, dodaj, znormalizuj, zaokrąglij

Dodanie dwóch liczb zmiennoprzecinkowych jest bardziej zawiłe niż dodanie dwóch całkowitych. Pięć kroków to:

1. Porównaj wykładniki. Wybierz większy jako wykładnik odniesienia.
2. Wyrównaj mantysy. Przesuń mantysę mniejszego operandu w prawo tak, by obie mantysy reprezentowały wartości przy tym samym wykładniku. Może to zepchnąć bity za prawą krawędź (stają się one bitami guard, round i sticky, używanymi do poprawnego zaokrąglania).
3. Dodaj wyrównane mantysy. Zwykłe dodawanie dwójkowe obu (włącznie z niejawnymi wiodącymi 1).
4. Znormalizuj ponownie. Jeśli suma przelała się do następnego wykładnika (np. 1.1 + 1.1 = 11.0, co wymaga 1.10 × 2^1), przesuń mantysę w prawo i podnieś wykładnik. Jeśli suma jest mniejsza niż postać znormalizowana (zniesienie przy odejmowaniu), przesuń w lewo i zmniejsz wykładnik.
5. Zaokrąglij. Ponownie znormalizowana mantysa ma zwykle więcej bitów, niż pozwala 52-bitowe pole. Zaokrąglij do najbliższej reprezentowalnej wartości domyślną regułą IEEE-754 — do najbliższej, remisy do parzystej.

Możemy zobaczyć, jak wszystkie te kroki się stosują, śledząc szczegółowo słynny przypadek, w którym 0.1 + 0.2 daje 0.30000000000000004 zamiast 0.3. Zarówno 0.1, jak i 0.2 są nieskończonymi okresowymi liczbami dwójkowymi (tak samo jak 1/3 to 0.333… dziesiętnie: $0.1 = 0.0\overline{0011}_2$), więc każda przy przechowaniu zostaje zaokrąglona do 52 bitów mantysy, a dodawanie zaokrągla znowu. Trzy zaokrąglenia, których błędy się nie znoszą. Szczegółowe omówienie bit po bicie jest w artykule siostrzanym.

Na podstawie tego przykładu widać, że dodawanie zmiennoprzecinkowe nie jest łączne ani dokładne. Trzy zaokrąglenia dają inną odpowiedź niż jedno zaokrąglenie tego samego wyniku matematycznego. Dlatego (a + b) + c i a + (b + c) mogą dać różne wyniki zmiennoprzecinkowe.

Odejmowanie: pułapka katastrofalnego zniesienia

Odejmowanie zmiennoprzecinkowe podąża za tym samym tańcem wyrównaj-dodaj-znormalizuj-zaokrąglij co dodawanie, ale z jedną dodatkową troską: katastrofalnym zniesieniem.

Gdy odejmowane są dwie niemal równe liczby zmiennoprzecinkowe, wiodące bity się znoszą. Krok ponownej normalizacji przesuwa wtedy w lewo o wiele pozycji, „podciągając” bity niskiego rzędu, które pierwotnie były najmniej znaczącymi (a więc najmniej dokładnymi) częściami operandów.

Przykład w binary64: dwa double’e różniące się tylko ostatnim bitem mantysy:

• a = 1.0000…0001 × 2⁰ (mantysa: 51 zer, potem 1; równa się 1 + 2⁻⁵²)
• b = 1.0000…0000 × 2⁰ (mantysa: same zera; równa się 1.0)

a − b = 0.0000…0001 × 2⁰, co normalizuje się ponownie do 1.0 × 2⁻⁵². 52 wiodące bity mantysy zniosły się, a najniższy bit — już na granicy precyzji — stał się całym wynikiem. Jeśli samo a było zaokrąglonym wyjściem jakiegoś wcześniejszego obliczenia, ten najniższy bit jest w większości szumem zaokrąglenia, a odejmowanie właśnie awansowało go na pozycję najbardziej znaczącą.

Dlatego kod numeryczny często przebudowuje wzory, by unikać odejmowania niemal równych wartości — zniesienie może zamienić mały błąd zaokrąglenia w wynik bez żadnych praktycznie ważnych cyfr.

Porównywanie: porządek bitów działa (prawie)

Porównywanie liczb zmiennoprzecinkowych jest niemal tak proste jak porównywanie całkowitych: dla wartości niespecjalnych porównanie dwóch takich liczb po ich układzie bitów daje tę samą odpowiedź co porównanie ich wartości liczbowych. To dlatego, że IEEE-754 kładzie znak w MSB, potem wykładnik, potem mantysę — więc większy układ bitów (czytany jako znak-moduł) odpowiada większej liczbie. Procesory potrafią porównać dwie takie liczby jedną instrukcją sprzętową.

Ale proste prawidło łamią dwa przypadki specjalne:

• NaN jest różny od wszystkiego, włącznie z samym sobą. NaN == NaN daje false. Jest to zamierzone — NaN reprezentuje „brak poprawnej liczby”, więc nie może być niczemu równy. Algorytmy sortowania i tablice haszujące muszą obsługiwać NaN specjalnie.
• +0 == -0, mimo że ich bity znaku się różnią. Te dwa zera porównują się liczbowo jako równe, ale nie są w pełni wymienne: 1 / +0 daje +∞, a 1 / -0 daje -∞.

Pojawia się to w zaskakujących miejscach. W JavaScripcie [NaN].includes(NaN) daje true (specyfikacja języka używa tam równości bitowej), ale [NaN].indexOf(NaN) daje -1 (używa ===, które honoruje regułę IEEE-754). A w większości języków if (x == x) to standardowa idioma dla „czy x nie jest NaN?”.

Mnożenie: prostsze niż dodawanie

Zaskakująco, mnożenie zmiennoprzecinkowe jest prostsze niż dodawanie, bo nie musisz wyrównywać wykładników.

Aby obliczyć a × b:

1. Pomnóż mantysy (włącznie z niejawnymi wiodącymi 1). Każda mantysa jest co najmniej 1 (bo niejawny bit wiodący to 1) i mniejsza od 2 (cokolwiek ≥ 2 zostałoby przenormalizowane do wyższego wykładnika). Więc ich iloczyn jest co najmniej 1 i mniejszy od 4 (minimum 1 × 1 = 1; maksimum tuż poniżej 2 × 2 = 4), co znaczy, że wynik jest albo już znormalizowany (1.xxx), albo o jeden bit za duży (1x.xxx).
2. Dodaj prawdziwe wykładniki. Wykładniki z przesunięciem trzeba najpierw odprzesunąć, a potem przesunąć na nowo: $(e_1 - 1023) + (e_2 - 1023) + 1023 = e_1 + e_2 - 1023$.
3. Wykonaj XOR na bitach znaku. Dodatnia × ujemna = ujemna itd.
4. Znormalizuj ponownie, jeśli trzeba. Jeśli iloczyn mantys przelał się do 1x.xxx, przesuń w prawo o 1 i dodaj 1 do wykładnika.
5. Zaokrąglij mantysę, by zmieściła się w 52 bitach.

Brak wyrównywania oznacza tylko jedno źródło błędu zaokrąglenia (krok 5), plus jakikolwiek błąd, który był już w operandach. Więc a × b jest zwykle dokładniejsze niż a + b, gdy oba liczone są na świeżo zaokrąglonych wejściach.

Możemy zobaczyć, jak te kroki się stosują, śledząc 0.1 × 0.2, co daje 0.020000000000000004 zamiast 0.02. Zarówno 0.1, jak i 0.2 zaokrąglają się do tej samej 52-bitowej mantysy (tej samej nieskończonej okresowej liczby dwójkowej, którą widzieliśmy wcześniej), różniąc się tylko wykładnikiem:

• 0.1 ≈ 1.10011001…10011010 × $2^{-4}$ (52 bity)
• 0.2 ≈ 1.10011001…10011010 × $2^{-3}$ (52 bity)

Przechodzimy pięć kroków:

1. Mnożymy mantysy. Każda mantysa dekoduje się do w przybliżeniu 1.6 dziesiętnie (dwójkowe 1.10011001…10011010 jest najbliższym 53-bitowym przybliżeniem 8/5 = 1.6). Pełne mnożenie dwóch 53-bitowych wartości daje do 106 bitów, o wartości ≈ 1.6 × 1.6 = 2.56. Ponieważ 2.56 ≥ 2, wynik jest w postaci 1x.xxx i potrzebna jest renormalizacja.
2. Dodajemy prawdziwe wykładniki: $-4 + -3 = -7$.
3. XOR na znakach: dodatnia × dodatnia = dodatnia.
4. Renormalizujemy. Iloczyn mantys jest w postaci 1x.xxx, więc przesuwamy w prawo o 1 (mantysa staje się ≈ 1.28) i podnosimy wykładnik z $-7$ do $-6$.
5. Zaokrąglamy 106-bitowy iloczyn mantys w dół do 52 bitów.

Ostateczna przechowana wartość dekoduje się do dokładnej liczby dziesiętnej 0.0200000000000000004163336342344337026588618755340576171875 — blisko 0.02, ale nie równo. Błędy zaokrąglenia w 0.1 i 0.2 przenoszą się do iloczynu, a sam iloczyn zaokrągla się znowu.

Dzielenie: rzadko dokładne

Dzielenie zmiennoprzecinkowe odzwierciedla pięciokrokową strukturę mnożenia, z odwróconymi operacjami:

1. Podziel mantysy. Każda mantysa jest co najmniej 1 i mniejsza od 2, więc mantysa ilorazu jest co najmniej 0.5 i mniejsza od 2 — albo już znormalizowana (1.xxx), albo o jeden bit za mała (0.xxx).
2. Odejmij prawdziwe wykładniki. Ten sam taniec odprzesuń-i-przesuń-na-nowo jak przy mnożeniu: $(e_1 - 1023) - (e_2 - 1023) + 1023 = e_1 - e_2 + 1023$.
3. Wykonaj XOR na bitach znaku. Ujemna / dodatnia = ujemna itd.
4. Znormalizuj ponownie, jeśli trzeba. Jeśli mantysa ilorazu jest 0.xxx, przesuń w lewo o 1 i zmniejsz wykładnik.
5. Zaokrąglij mantysę, by zmieściła się w 52 bitach.

Wielka różnica względem mnożenia: dzielenie rzadko jest dokładne. Dwie 53-bitowe wartości mogą dać iloraz, którego przedstawienie wymaga nieskończenie wielu bitów — nawet gdy oba operandy są proste. Na przykład 1.0 / 3.0 to dwójkowy odpowiednik 1/3 = 0.333… dziesiętnie: nieskończona okresowa liczba dwójkowa, którą trzeba zaokrąglić. Więc krok 5 zaokrągla niemal zawsze, nawet gdy dla operandów żadne zaokrąglenie nie było potrzebne.

Nowoczesne procesory realizują dzielenie zmiennoprzecinkowe przez te same iteracje Newtona–Raphsona / Goldschmidta wspomniane wcześniej dla dzielenia całkowitego, redukując je do kilku mnożeń — ale dzielenie i tak jest zwykle najwolniejszą z czterech podstawowych operacji zmiennoprzecinkowych.

Nadmiar i niedomiar: nieskończoność i zero zamiast przewinięcia

W przeciwieństwie do liczb całkowitych w uzupełnieniu do dwóch, liczby zmiennoprzecinkowe nie przewijają się przy nadmiarze. IEEE-754 rezerwuje specjalne układy bitów dla wyników „zbyt dużych” i „zbyt małych”:

• Nadmiar → wykładnik przekroczyłby maksymalną reprezentowalną wartość $2^{1023}$. Wynikiem staje się $\pm\infty$, zakodowane wykładnikiem z samych jedynek i mantysą z samych zer.
• Niedomiar → wykładnik spadłby poniżej minimum ($2^{-1022}$ dla normalnych). Wynikiem staje się liczba subnormalna (mantysa nie ma niejawnej wiodącej 1, co pozwala na łagodną utratę precyzji) albo w końcu $\pm 0$.

W układzie bitów (znak | 11 bitów wykładnika | 52 bity mantysy):

+∞          :  0 | 11111111111 | 0000…0000
-∞          :  1 | 11111111111 | 0000…0000
+0          :  0 | 00000000000 | 0000…0000
-0          :  1 | 00000000000 | 0000…0000
subnormal   :  s | 00000000000 | xxxx…xxxx   (niezerowa mantysa; brak niejawnej wiodącej 1)
NaN         :  s | 11111111111 | xxxx…xxxx   (niezerowa mantysa)

Więc 1e300 × 1e300 w typie double produkuje Infinity, a nie jakiś przewinięty układ bitów. A 1e-300 × 1e-300 schodzi przez subnormalne w stronę zera.

Układy bitów dla wartości specjalnych żyją wszystkie na skrajach zakresu wykładnika, i właśnie dlatego dla pola wykładnika wybrano na początku kod z przesunięciem: kładzie on układy wykładnika z samych zer i samych jedynek na granicach, gdzie rezerwacje są naturalne.

Dzielenie przez zero: Infinity, a nie wyjątek

Całkowite dzielenie przez zero w większości języków wpada w pułapkę albo rzuca wyjątek. Zmiennoprzecinkowe dzielenie przez zero nie — produkuje ±Infinity:

> 1 / 0
Infinity
> -1 / 0
-Infinity

Python jest wyjątkiem (rzuca ZeroDivisionError na warstwie języka), ale leżąca pod spodem arytmetyka IEEE-754 produkuje Infinity; Python go tylko przechwytuje. W JavaScripcie dostajesz surowe zachowanie.

0 / 0 to inna sprawa — produkuje NaN, specjalną wartość „nie liczba”, która propaguje się przez dalszą arytmetykę i jest różna od wszystkiego, włącznie z samą sobą.

Czym te dwa systemy się różnią

Gdy oba systemy są rozłożone, kontrasty rzucają się w oczy. Arytmetyka całkowita i arytmetyka zmiennoprzecinkowa nie dzielą niemal niczego na poziomie bitów, a różnice mają znaczenie w praktyce:

Dla większości kodu aplikacyjnego różnice pokazują się jako codzienne dziwactwa:

• Liczby całkowite są przewidywalne, ale wąskie. Dodawanie jest łączne i dokładne, więc (a + b) + c == a + (b + c) zawsze. Ale wyjdź poza zakres i przewiniesz się (albo padniesz, zależnie od języka).
• Liczby zmiennoprzecinkowe są szerokie, ale nieprecyzyjne. Możesz przedstawić wartości od $10^{-308}$ do $10^{308}$, ale niewiele z nich dokładnie. Każda operacja zaokrągla, a błędy zaokrąglenia kumulują się w sposób zależny od kolejności operacji.
• Mieszanie ich wymaga ostrożności. Konwersja dużego int64 na float64 traci precyzję powyżej $2^{53}$ (granica bezpiecznych liczb całkowitych). Konwersja dużej liczby zmiennoprzecinkowej na całkowitą obcina ją. W ogólności żadna z nich nie jest odwracalna.

Pod tymi codziennymi obserwacjami leżą cztery głębsze punkty, warte zapamiętania:

1. Arytmetyka całkowita w uzupełnieniu do dwóch jest modularna. Każda operacja zachodzi modulo $2^n$, i dlatego dodawanie i odejmowanie korzystają z tego samego układu i dlatego INT_MAX + 1 = INT_MIN. Asymetryczny zakres (jedna dodatkowa ujemna) daje Ci przypadek brzegowy INT_MIN / -1, gdzie prawdziwy wynik nie ma w ogóle żadnego układu bitów.
2. Arytmetyka zmiennoprzecinkowa to wyrównaj-dodaj-znormalizuj-zaokrąglij. Każda operacja na dwóch takich liczbach obejmuje ponowne wyrównanie ich wykładników (dla dodawania), wykonanie matematyki, ponowną normalizację wyniku i zaokrąglenie do 52 bitów mantysy. Każdy krok może wprowadzić błąd, i dlatego wyniki zmiennoprzecinkowe rzadko są dokładne bitowo.
3. Nadmiar zachowuje się całkowicie inaczej. Całkowite przewijają się; zmiennoprzecinkowe nasycają się do nieskończoności. To nie jest wybór powierzchowny — odzwierciedla fundamentalnie inną strukturę tych dwóch przestrzeni liczbowych (płaska modularna kontra logarytmiczna z zarezerwowanymi końcami).
4. Bity nie noszą znaczenia — typ je nosi. Te same 32 bity mogą być int albo float, zależnie od tego, co zdecyduje program. Dodawanie w uzupełnieniu do dwóch i dodawanie zmiennoprzecinkowe to całkowicie różne operacje, które przypadkiem używają tych samych 32 bitów pamięci.

Wiedzieć, w jakim systemie arytmetycznym się znajdujesz (i jakie ma dziwactwa), jest zwykle ważniejsze niż znać konkretne kodowanie swoich liczb. Gdy obliczenie daje nieoczekiwaną odpowiedź, pytanie „który system to obsłużył?” jest zwykle najszybszą drogą do odpowiedzi.