Zamiana Liczb: Od Dziesiętnego do Binarnego

W jednym z wcześniejszych wpisów pokazałem zamianę liczb z systemu binarnego na dziesiętny. Teraz robimy drogę w drugą stronę: z dziesiętnego na binarny – i to z częścią ułamkową, której większość poradników w sieci albo nie rusza, albo zbywa jednym zdaniem. A to właśnie ułamki są tu najciekawsze: to one tłumaczą, dlaczego 0.1 + 0.2 nie daje równo 0.3. Zaczniemy od matematyki (część całkowita i ułamkowa osobno), potem zaimplementujemy algorytm w Pythonie, JavaScript, PHP i C++, a na końcu połączymy to z niedokładnością liczb zmiennoprzecinkowych.

Część całkowita – dzielenie przez 2 z resztą

Część całkowitą zamieniamy na binarną przez kolejne dzielenie przez 2 i zapisywanie reszt. Reszty czytamy od dołu do góry – ostatnia reszta jest najstarszym bitem.

Weźmy 101:

Czytając reszty od dołu: 101₁₀ = 1100101₂. Możemy to sprawdzić wstecz: 2⁶ + 2⁵ + 2² + 2⁰ = 64 + 32 + 4 + 1 = 101. Zgadza się.

Część ułamkowa – mnożenie przez 2 (sedno tematu)

Z częścią po przecinku robimy operację odwrotną do części całkowitej: zamiast dzielić, mnożymy przez 2. Zasada jest taka:

1. Mnożymy część ułamkową przez 2.
2. Część całkowita wyniku (0 albo 1) to kolejny bit – tym razem czytany od góry do dołu.
3. Zostawiamy samą część ułamkową i powtarzamy, aż dojdziemy do zera (ułamek skończony) albo reszta zacznie się powtarzać (ułamek nieskończony, okresowy).

Przykład skończony: 0.8125

Bity od góry: 0.8125₁₀ = 0.1101₂. Sprawdzenie: 2⁻¹ + 2⁻² + 2⁻⁴ = 0.5 + 0.25 + 0.0625 = 0.8125. Razem z częścią całkowitą: 101.8125₁₀ = 1100101.1101₂.

Reszta doszła do zera, więc rozwinięcie jest skończone. Ale tak ma tylko garstka ułamków.

Przykład nieskończony: 0.1

Spróbujmy z pozornie banalnym 0.1:

W kroku 5 reszta 0.2 powtarza się – a skoro reszta jest ta sama, to od tego miejsca wszystko się zapętla w nieskończoność. Dostajemy:

0.1₁₀ = 0.0001100110011…₂ = 0.0(0011)₂

gdzie (0011) to powtarzający się okres. To jest dokładnie ten nieskończony ciąg, o którym mowa we wpisie o niedokładności – tylko tutaj widać, skąd się bierze: komputer musi go gdzieś uciąć, więc zapisuje jedynie przybliżenie 0.1.

Kiedy ułamek dziesiętny ma skończone rozwinięcie binarne?

To pytanie warte złota, bo odpowiedź jest prosta i jednoznaczna:

Ułamek (w postaci nieskracalnej) ma skończone rozwinięcie binarne wtedy i tylko wtedy, gdy jego mianownik jest potęgą dwójki.

Dlaczego? Bo skończony ułamek binarny to z definicji k / 2ⁿ. Sprawdźmy:

• 0.5 = 1/2 → mianownik 2¹ → skończone (0.1₂).
• 0.25 = 1/4 → 2² → skończone (0.01₂).
• 0.8125 = 13/16 → 2⁴ → skończone (0.1101₂).
• 0.1 = 1/10 = 1/(2·5) → mianownik ma czynnik 5, nie jest potęgą dwójki → nieskończone.

Tu kryje się asymetria, która myli intuicję: w systemie dziesiętnym ułamek kończy się, gdy mianownik to 2ᵃ · 5ᵇ (bo 10 = 2 · 5). W binarnym – tylko gdy mianownik to 2ⁿ. Dlatego każdy ułamek skończony w binarnym jest skończony w dziesiętnym, ale nie odwrotnie. 0.1, 0.2, 0.3 – wszystkie ładne w zapisie dziesiętnym – w binarnym są nieskończone. To źródło całej rodziny problemów z precyzją.

Implementacja w Pythonie

Zacznijmy od bezpośredniego przełożenia algorytmu: dzielenie dla części całkowitej, mnożenie dla ułamkowej. Pętlę ułamkową ograniczamy liczbą bitów, żeby nie kręciła się w nieskończoność dla ułamków okresowych.

def decimal_to_binary(value, max_bits=52):
    integer = int(value)
    frac = value - integer

    # część całkowita: reszty z dzielenia przez 2, czytane od dołu
    int_bits = ""
    n = integer
    while n > 0:
        int_bits = str(n % 2) + int_bits
        n //= 2
    int_bits = int_bits or "0"

    # część ułamkowa: część całkowita z mnożenia przez 2, czytana od góry
    frac_bits = ""
    while frac and len(frac_bits) < max_bits:
        frac *= 2
        bit = int(frac)
        frac_bits += str(bit)
        frac -= bit

    return f"{int_bits}.{frac_bits}" if frac_bits else int_bits

print(decimal_to_binary(101.8125))  # 1100101.1101
print(decimal_to_binary(0.1))       # 0.0001100110011001100110011001100110011001100110011010

Zwróć uwagę na drugi wynik: to nie czysty okres 0.0(0011), tylko 52 bity zakończone… 1010. Dlaczego? Bo do funkcji trafił float, a 0.1 jako float to już jest przybliżenie. Konwertując float, konwertujesz nie liczbę 0.1, lecz to, co komputer pod nią naprawdę trzyma. To zresztą najlepsza ilustracja problemu – ale do pokazania prawdziwego, matematycznego rozwinięcia potrzebujemy arytmetyki dokładnej.

Wersja dokładna z wykryciem okresu

Użyjmy fractions.Fraction, który trzyma liczbę jako dokładny ułamek (Fraction('0.1') to równo 1/10), i wykryjmy moment, w którym reszta się powtarza – czyli początek okresu:

from fractions import Fraction

def fraction_to_binary(text, max_bits=64):
    frac = Fraction(text)        # Fraction('0.1') == 1/10 — dokładnie, bez błędu float
    bits = ""
    seen = {}                    # reszta -> pozycja bitu (do wykrycia cyklu)
    period_at = None

    while frac != 0 and len(bits) < max_bits:
        if frac in seen:         # ta reszta już była -> stąd zaczyna się okres
            period_at = seen[frac]
            break
        seen[frac] = len(bits)
        frac *= 2
        bit = int(frac)          # 0 albo 1
        bits += str(bit)
        frac -= bit              # zostaje sama część ułamkowa

    if period_at is not None:
        bits = bits[:period_at] + "(" + bits[period_at:] + ")"
    return "0." + bits

print(fraction_to_binary("0.8125"))  # 0.1101      (skończone)
print(fraction_to_binary("0.1"))     # 0.0(0011)   (okres 0011)
print(fraction_to_binary("0.2"))     # 0.(0011)
print(fraction_to_binary("0.3"))     # 0.0(1001)

Ta wersja pokazuje liczbę taką, jaka jest matematycznie – z jawnie zaznaczonym okresem w nawiasie. Różnica między tym wynikiem a poprzednim (float) to w pigułce cała natura błędów zmiennoprzecinkowych.

Implementacja w JavaScript

W JavaScript algorytm wygląda niemal identycznie. Tu również operujemy na number (czyli double), więc dla ułamków nieskończonych zobaczymy ucięte rozwinięcie – dokładnie to, co silnik trzyma w pamięci.

function decimalToBinary(value, maxBits = 52) {
    let integer = Math.trunc(value);
    let frac = value - integer;

    // część całkowita
    let intBits = "";
    for (let n = integer; n > 0; n = Math.floor(n / 2)) {
        intBits = (n % 2) + intBits;
    }
    intBits = intBits || "0";

    // część ułamkowa
    let fracBits = "";
    while (frac > 0 && fracBits.length < maxBits) {
        frac *= 2;
        const bit = Math.floor(frac);
        fracBits += bit;
        frac -= bit;
    }

    return fracBits ? `${intBits}.${fracBits}` : intBits;
}

console.log(decimalToBinary(101.8125)); // "1100101.1101"
console.log(decimalToBinary(0.1));      // "0.000110011001100110011..." (ucięte – to zapis przybliżenia)

Implementacja w PHP

<?php
function decimalToBinary(float $value, int $maxBits = 52): string {
    $integer = (int) $value;
    $frac = $value - $integer;

    // część całkowita
    $intBits = "";
    for ($n = $integer; $n > 0; $n = intdiv($n, 2)) {
        $intBits = ($n % 2) . $intBits;
    }
    $intBits = $intBits !== "" ? $intBits : "0";

    // część ułamkowa
    $fracBits = "";
    while ($frac > 0 && strlen($fracBits) < $maxBits) {
        $frac *= 2;
        $bit = (int) $frac;
        $fracBits .= $bit;
        $frac -= $bit;
    }

    return $fracBits !== "" ? "$intBits.$fracBits" : $intBits;
}

echo decimalToBinary(101.8125), PHP_EOL; // 1100101.1101
echo decimalToBinary(0.1), PHP_EOL;      // 0.000110011001100110011... (ucięte)

Używamy intdiv() do dzielenia całkowitego części całkowitej oraz mnożenia przez 2 dla części ułamkowej – ta sama logika, co wcześniej.

Implementacja w C++

#include <iostream>
#include <string>

std::string decimalToBinary(double value, int maxBits = 52) {
    long long integer = static_cast<long long>(value);
    double frac = value - integer;

    // część całkowita
    std::string intBits;
    for (long long n = integer; n > 0; n /= 2) {
        intBits = std::to_string(n % 2) + intBits;
    }
    if (intBits.empty()) intBits = "0";

    // część ułamkowa
    std::string fracBits;
    while (frac > 0 && static_cast<int>(fracBits.size()) < maxBits) {
        frac *= 2;
        int bit = static_cast<int>(frac);
        fracBits += std::to_string(bit);
        frac -= bit;
    }

    return fracBits.empty() ? intBits : intBits + "." + fracBits;
}

int main() {
    std::cout << decimalToBinary(101.8125) << std::endl; // 1100101.1101
    std::cout << decimalToBinary(0.1) << std::endl;       // 0.000110011001100110011... (ucięte)
    return 0;
}

We wszystkich czterech językach algorytm jest ten sam – różni się tylko składnia. I we wszystkich (poza dokładną wersją z Fraction w Pythonie) działamy na typie zmiennoprzecinkowym, więc dla 0.1 dostajemy ucięte rozwinięcie.

Most do niedokładności zmiennoprzecinkowej

Teraz spina się wszystko. Skoro 0.1₁₀ = 0.0(0011)₂ i 0.2₁₀ = 0.(0011)₂ to nieskończone ułamki binarne, komputer musi je przyciąć do skończonej liczby bitów (w double – do 52 bitów mantysy). Zapisuje więc nie 0.1 i 0.2, lecz ich przybliżenia. Gdy je dodasz, sumują się też drobne błędy obcięcia – i dlatego:

0.1 + 0.2 === 0.3   // false
0.1 + 0.2           // 0.30000000000000004

To nie jest błąd języka ani procesora – to bezpośredni skutek tego, co policzyliśmy wyżej ręcznie. Jak sobie z tym radzić w praktyce (typy Decimal/BigDecimal, porównania z tolerancją, liczby całkowite zamiast ułamków) opisałem w osobnym wpisie: Zrozumienie niedokładności liczb zmiennoprzecinkowych.

Podsumowanie

Zamiana z dziesiętnego na binarny to dwa lustrzane algorytmy: dzielenie przez 2 (część całkowita, reszty od dołu) i mnożenie przez 2 (część ułamkowa, bity od góry). Część całkowita zawsze się kończy. Część ułamkowa – tylko wtedy, gdy mianownik nieskracalnego ułamka jest potęgą dwójki; w przeciwnym razie dostajemy nieskończone rozwinięcie okresowe, które komputer musi uciąć. I właśnie to obcięcie jest źródłem słynnego 0.1 + 0.2 ≠ 0.3.

Jeśli chcesz prześledzić drogę w przeciwną stronę, zajrzyj do wpisu Zamiana Liczb: Od Binarnego do Dziesiętnego, a po praktyczne sposoby walki z błędami precyzji – do wpisu o niedokładności liczb zmiennoprzecinkowych.