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 — prostego schematu, w którym dodawanie ze znakiem korzysta z tego samego układu sprzętowego co dodawanie bez znaku. Dla ułamków powszechnie stosuje się zmienny przecinek IEEE-754, z osobnymi polami znaku, wykładnika i mantysy. Dodawanie i odejmowanie wymagają wyrównania mantys, a wyniki działań mogą wymagać zaokrąglenia.

Ten artykuł omawia arytmetykę obu formatów — co faktycznie dzieje się z bitami przy dodawaniu, odejmowaniu, mnożeniu i dzieleniu w każdym formacie, gdzie pojawiają się ograniczenia i czym różnią się te dwa systemy. 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) ma 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.

Zachowanie dolnych $n$ bitów daje zawijanie: największa wartość ze znakiem plus jeden staje się najmniejszą. Reguły języka mogą różnić się od wyniku sprzętowego: przepełnienie ze znakiem w C/C++ jest niezdefiniowane, a arytmetyka bez znaku zawija się. INT_MAX i INT_MIN opisują zakres typu int danej implementacji, niekoniecznie 32-bitowego. Pythonowy int i JavaScriptowy BigInt mają dowolną precyzję; Number używa liczb zmiennoprzecinkowych.

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: Przykłady stosują konwencję x86: flaga przeniesienia przy odejmowaniu wskazuje pożyczkę.

 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 pokazują różne kombinacje flag: 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 wykonania skoku JL. Wiersz JG działa tak samo z sign = 0 i overflow = 0, dając 0 ⊕ 0 = 0 (plus zero = 0), co jest warunkiem wykonania skoku 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 polegało na mnożeniu przez liczbę dziesiętną, 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 dopisywanie zer z prawej 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 obliczyć 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 operandom daleko do 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 wymaga 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 ma 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)  ✓

Różnica między wersjami ze znakiem i bez znaku występuje wyłącznie 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)

Dolne $n$ bitów iloczynu nie wymaga więc osobnych układów mnożenia ze znakiem i bez znaku. Kontrola przepełnienia i reguły języka nadal się różnią; nie oznacza to, że przepełnienie ze znakiem w C/C++ jest zdefiniowane.

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 ustalić cyfrę od 0 do 9 — trzeba ustalić, ile dzielnika się mieści, co na ogół wymaga mnożenia oraz stosowania metody prób i błędów.

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 wstępnie oblicza R − D: jeśli wynik jest nieujemny (brak pożyczki), zapisuje go w 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 zaokrągleniem w dół (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 na końcu przywraca znak. Dzielenie z zaokrągleniem w dół 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.

Ten algorytm przesuwania i odejmowania wykonuje $n$ iteracji dla $n$-bitowej dzielnej. To liczba iteracji, nie pojedynczych operacji bitowych: każde porównanie i odejmowanie także ma koszt. Dzielniki sprzętowe mogą stosować szybsze algorytmy, a ich opóźnienie zależy od procesora i argumentów.

Przy dzieleniu ze znakiem z obcięciem do zera podziel moduły, zaneguj iloraz przy różnych znakach i nadaj niezerowej reszcie znak dzielnej. Dzielenie w dół w Pythonie wymaga dodatkowo opisanej wyżej korekty; sama zmiana znaku reszty nie wystarcza.

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

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

Dla dzielenia ze znakiem o stałej szerokości przez wartość niezerową przepełnienie powoduje dokładnie jedna para: wartość minimalna podzielona przez -1. Dla typu 32-bitowego:

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) wymaga wartości, której format nie potrafi przedstawić.

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 działa zupełnie inaczej. 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 kontynuujemy od miejsca, w którym ten artykuł się kończy — format jest ustalony; teraz co się dzieje, gdy wykonasz arytmetykę na dwóch takich liczbach.

Poniższy opis zakłada normalne, skończone argumenty i zaokrąglanie do najbliższej wartości z remisami do parzystej. Oddzielamy obsługę znaku, wykładnika i części znaczącej, po czym normalizujemy i zaokrąglamy do 53 bitów znaczących (52 zapisanych bitów ułamka). Zero, liczby subnormalne, nieskończoności, NaN i przepełnienie wymagają dodatkowych przypadków.

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.

Ten przykład pokazuje, że dodawanie nie musi być dokładne. Nie musi też być łączne: w binary64 (1e16 + -1e16) + 1 daje 1, a 1e16 + (-1e16 + 1) daje 0, bo zaokrąglenie wewnętrznej sumy usuwa 1.

Odejmowanie: pułapka katastrofalnego zniesienia

Odejmowanie zmiennoprzecinkowe przebiega według tych samych kroków co dodawanie — wyrównaj, dodaj, znormalizuj i zaokrąglij — ale wiąże się z jednym dodatkowym problemem: 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)

Tutaj a − b = 2⁻⁵² jest dokładne: samo znoszenie cyfr nie oznacza błędu zaokrąglenia. Problem pojawia się, gdy argumenty zawierają już błędy wcześniejszych obliczeń. Ich mała różnica może wtedy mieć duży błąd względny.

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 praktycznie bez poprawnych cyfr znaczących.

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

Dla nieujemnych skończonych wartości binary64 porządek wzorców bitowych jako liczb bez znaku odpowiada porządkowi liczbowemu. Dla wartości ujemnych trzeba odwrócić porządek modułów, a przy różnych znakach uwzględnić znak. Surowe porównanie bez znaku nie działa więc dla wszystkich floatów.

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 -∞.

JavaScriptowe [NaN].includes(NaN) zwraca true, bo używa SameValueZero, które uznaje NaN za równe i zrównuje +0 z -0. To nie porównanie bitowe. [NaN].indexOf(NaN) zwraca -1, ponieważ używa ścisłej równości.

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 pozbawić przesunięcia, a następnie dodać je do wyniku: $(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.

Zarówno dodawanie, jak i mnożenie zaokrągla dokładny wynik raz do formatu docelowego. Wyrównanie wykładników nie dodaje osobnego zaokrąglenia, jeśli poprawnie zachowuje się bity guard, round i sticky. Żadna z tych operacji nie jest z natury dokładniejsza dla dowolnych argumentów.

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 do 53 bitów znaczących (52 zapisanych i jednego domyślnego bitu wiodącego).

Ostateczna przechowana wartość dekoduje się do dokładnej liczby dziesiętnej 0.02000000000000000388578058618804789148271083831787109375 — 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. Tak jak przy mnożeniu, najpierw odejmujemy przesunięcia od wykładników, a następnie dodajemy przesunięcie do wyniku: $(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.

Dzielenie sprzętowe może używać algorytmów wyznaczających kolejne cyfry lub przybliżających odwrotność, zależnie od procesora. Zwykle jest wolniejsze od mnożenia, ale dokładne opóźnienie zależy od architektury.

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”:

• Przepełnienie: zaokrąglony wynik wymaga wykładnika większego od maksimum, 1023 dla binary64. Przy zaokrąglaniu do najbliższej wartości daje ±∞; tryby kierunkowe mogą zamiast tego zwrócić największy skończony moduł, $(2-2^{-52})2^{1023}$, z odpowiednim znakiem.
• Bardzo małe wyniki: poniżej najmniejszego normalnego modułu, $2^{-1022}$, liczby subnormalne zachowują część precyzji aż do $2^{-1074}$; mniejsze wyniki mogą zaokrąglić się do zera. Dokładny wynik subnormalny nie musi ustawić flagi niedomiaru.

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)

Na przykład przy zaokrąglaniu do najbliższej wartości 1e300 * 1e300 daje nieskończoność, a 1e-300 * 1e-300 zaokrągla się bezpośrednio do zera. Stopniowy niedomiar opisuje dostępne wartości subnormalne, nie ciąg wartości pośrednich odwiedzanych przez każdą operację.

Wzorce bitowe wartości specjalnych znajdują się 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ą

Po omówieniu obu systemów wyraźnie widać różnice. Arytmetyka całkowita i arytmetyka zmiennoprzecinkowa mają niewiele wspólnego na poziomie bitów, a różnice mają znaczenie w praktyce:

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

• Dodawanie całkowitoliczbowe jest dokładne, gdy wyniki pośrednie mieszczą się w zakresie. Zachowanie przy przepełnieniu zależy od języka, nie tylko kodowania.
• Arytmetyka zmiennoprzecinkowa ma szeroki zakres, ale skończoną precyzję. Zaokrąglanie może sprawić, że kolejność operacji ma znaczenie.
• Konwersja między liczbami całkowitymi i floatami może gubić informacje. Powyżej $2^{53}$ binary64 nie reprezentuje każdej liczby całkowitej; konwersja w drugą stronę zależy też od języka i zakresu typu docelowego.

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.