Jeśli poszukasz w sieci How to convert from decimal to binary, znajdziesz cztery proste algorytmy: dwa dla liczb całkowitych i dwa dla ułamków. Zostały przedstawione wraz z przykładami poniżej, w pierwszej części artykułu. Choć sama znajomość algorytmów niemal zawsze wystarcza, postanowiłem spróbować zrozumieć, dlaczego one działają. W drugiej części ten artykuł wyjaśnia całkiem podstawową matematykę stojącą za każdym z nich. Jej znajomość może pomóc Ci odtworzyć dowolny z algorytmów, gdybyś nagle o nim zapomniał. Gorąco radzę wziąć notes i długopis i wykonywać działania razem ze mną — matematyka zapadnie wtedy lepiej w pamięć. Oto te cztery algorytmy z przykładami, które można znaleźć w sieci.

Konwersja dziesiętnej liczby całkowitej na binarną

Aby przekonwertować liczbę całkowitą na system binarny, weź daną liczbę i podziel ją przez 2, notując iloraz i resztę. Dziel iloraz przez 2 dalej, aż otrzymasz iloraz równy zeru. Następnie po prostu wypisz reszty w odwrotnej kolejności.

Oto przykład takiej konwersji na liczbie 12. Najpierw podzielmy liczbę przez dwa, podając iloraz i resztę:

$$\begin{aligned} 12 : 2 &= 6 + 0 \\ 6 : 2 &= 3 + 0 \\ 3 : 2 &= 1 + 1 \\ 1 : 2 &= 0 + 1 \end{aligned}$$

Teraz wystarczy wypisać reszty w odwrotnej kolejności — 1100. Zatem 12 w systemie dziesiętnym zapisuje się jako 1100 w systemie binarnym.

Konwersja ułamka dziesiętnego na binarny

Aby przekonwertować ułamek na system binarny, weź dany ułamek i pomnóż go przez 2, notując powstałą część całkowitą i ułamkową. Mnóż przez 2 dalej, aż powstała część ułamkowa będzie równa zeru. Następnie po prostu wypisz części całkowite z wyników każdego mnożenia.

Oto przykład takiej konwersji na ułamku 0.375.

$$\begin{aligned} 0.375 \cdot 2 &= 0 + 0.75 \\ 0.75 \cdot 2 &= 1 + 0.5 \\ 0.5 \cdot 2 &= 1 + 0 \end{aligned}$$

Teraz po prostu wypiszmy powstałą część całkowitą z każdego kroku — 0.011. Zatem 0.375 w systemie dziesiętnym zapisuje się jako 0.011 w systemie binarnym.

Konwersja binarnej liczby całkowitej na dziesiętną

Aby przekonwertować binarną liczbę całkowitą na dziesiętną, zacznij od lewej. Weź bieżącą sumę, pomnóż ją przez dwa i dodaj bieżącą cyfrę. Kontynuuj, aż skończą się cyfry. Oto przykład takiej konwersji na liczbie całkowitej 1011.

$$\begin{aligned} 2 \cdot 0 + 1 &= 1 \\ 2 \cdot 1 + 0 &= 2 \\ 2 \cdot 2 + 1 &= 5 \\ 2 \cdot 5 + 1 &= 11 \end{aligned}$$

Konwersja ułamka binarnego na dziesiętny

Aby przekonwertować ułamek binarny na dziesiętny, zacznij od prawej z sumą równą 0. Weź bieżącą sumę, dodaj bieżącą cyfrę i podziel wynik przez 2. Kontynuuj, aż skończą się cyfry. Oto przykład takiej konwersji na ułamku 0.1011. Dzielenie przez 2 zastąpiłem po prostu mnożeniem przez 1/2.

$$\begin{aligned} \frac{1}{2} \cdot (1 + 0) &= 0.5 \\ \frac{1}{2} \cdot (1 + 0.5) &= 0.75 \\ \frac{1}{2} \cdot (0 + 0.75) &= 0.375 \\ \frac{1}{2} \cdot (1 + 0.375) &= 0.6875 \end{aligned}$$

Masz oto 4 proste algorytmy, które pozwolą Ci przeliczać liczby binarne na dziesiętne i z powrotem.

Rozwinięcie liczby przy podstawie q

Kluczem do zrozumienia, dlaczego te algorytmy działają, jest rozwinięcie liczby przy podstawie q. Liczbę całkowitą w dowolnym systemie liczbowym można przedstawić w następującej postaci:

$$N = x_n \cdot q^n + \ldots + x_1 \cdot q^1 + x_0 \cdot q^0$$

gdzie N to liczba całkowita, x to cyfra (od 0 do 9 dla systemu o podstawie 10, 0 i 1 dla systemu o podstawie 2), a q to wartość podstawy (10 dla systemu o podstawie 10, 2 dla systemu o podstawie 2).

W całym artykule ta postać jest nazywana rozwinięciem liczby N przy podstawie q albo po prostu rozwinięciem przy podstawie q. Zobaczmy, jak wygląda dla liczby 12 w systemie dziesiętnym i binarnym:

$$\begin{aligned} 12_{10} &= 1 \cdot 10^1 + 2 \cdot 10^0 \\ 1100_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 \end{aligned}$$

Podobnie liczbę ułamkową w dowolnym systemie liczbowym można przedstawić w następującej postaci:

$$N = x_1 \cdot q^{-1} + x_2 \cdot q^{-2} + \ldots + x_n \cdot q^n$$

gdzie N to ułamek, x to cyfra (od 0 do 9 dla systemu o podstawie 10, 0 i 1 dla systemu o podstawie 2), a q to wartość podstawy (10 dla systemu o podstawie 10, 2 dla systemu o podstawie 2).

Dla liczby 0.375 w systemie dziesiętnym i binarnym reprezentacja wygląda tak:

$$\begin{aligned} 0.375_{10} &= 3 \cdot 10^{-1} + 7 \cdot 10^{-2} + 5 \cdot 10^{-3} \\ 0.011_2 &= 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} \end{aligned}$$

Konwersja dziesiętnej liczby całkowitej na binarną

Jak się okazuje, tej postaci rozwinięcia przy podstawie q możemy użyć do przeliczenia liczby z systemu dziesiętnego na binarny. Zróbmy to dla tej samej liczby 12. Najpierw udajmy, że nie wiemy, jak zapisuje się ją binarnie, i wypiszmy ją z nieznanymi cyframi zastąpionymi przez x:

$$12_{10} = x_n \cdot 2^n + \ldots + x_1 \cdot 2^1 + x_0 \cdot 2^0$$

Naszym zadaniem jest znaleźć wszystkie x. Zobaczmy, co da się tu zrobić. Pierwsze, co trzeba zauważyć, to że wszystkie składniki poza ostatnim będą liczbami parzystymi, bo wszystkie są wielokrotnościami dwójki. Korzystając z tej informacji, możemy wywnioskować cyfrę dla x0: jeśli przeliczana liczba całkowita jest parzysta, to x0 równa się 0, a jeśli nieparzysta — to x0 musi być 1. Mamy liczbę 12, która jest parzysta, więc x0 wynosi zero. Zapiszmy tę informację:

$$12_{10} = x_n \cdot 2^n + \ldots + x_1 \cdot 2^1 + 0$$

Następnie musimy znaleźć wartość x1. Ponieważ wszystkie składniki od x1 do xN są wielokrotnościami dwójki, możemy wyłączyć 2 przed nawias, żeby wyodrębnić x1. Zróbmy to:

$$12_{10} = 2(\underbrace{x_n \cdot 2^{n-1} + \ldots + x_1 \cdot 2^0}_{6}) + 0$$

Łatwo też zauważyć, że suma wartości w nawiasie równa się 6. Nasz pierwszy krok możemy więc zapisać jako:

$$12 = 2 \cdot 6 + 0$$

Szukajmy dalej pozostałych x. Wielomian w nawiasie możemy wypisać jako osobne wyrażenie:

$$6_{10} = x_n \cdot 2^{n-1} + \ldots + x_2 \cdot 2^1 + x_1 \cdot 2^0$$

Stosując tę samą logikę co wyżej, widzimy, że x1 równa się 0. Przepiszmy to i znowu wyłączmy 2 przed nawias:

$$6_{10} = 2 \cdot (\underbrace{x_n \cdot 2^{n-2} + \ldots + x_2 \cdot 2^0}_{3}) + 0$$

Zatem nasz drugi krok to:

$$6 = 2 \cdot 3 + 0$$

Teraz widać schemat. Możemy wyłączać 2 przed nawias dalej, aż iloraz będzie równy zeru. Podążmy za tym schematem i zobaczmy, co otrzymamy.

$$3_{10} = 2 \cdot (\underbrace{x_n \cdot 2^{n-3} + \ldots + x_3 \cdot 2^0}_{1}) + 1$$

Ponieważ iloraz równa się 1, został tylko jeden składnik, przepiszmy więc poprzednie wyrażenie:

$$3_{10} = 2 \cdot (\underbrace{x_3 \cdot 2^0}_{1}) + 1$$

Zatem nasz trzeci krok to:

$$3 = 2 \cdot 1 + 1$$

Kończymy więc z czymś takim:

$$1_{10} = x_3 \cdot 2^0$$

Jasne jest, że x3 równa się 1. Ale ponieważ nasz algorytm potrzebuje ilorazu, przepiszmy poprzednie wyrażenie tak, żeby go zawierało:

$$1_{10} = 2 \cdot 0 + 1$$

Skoro wyszedł nam iloraz 0, nie ma już z czym pracować i to był nasz ostatni krok. Wypiszmy go:

$$1 = 2 \cdot 0 + 1$$

Konwersja zakończona. Oto jak wygląda krok po kroku:

$$\begin{aligned} 12 &= 2 \cdot 6 + 0 \\ 6 &= 2 \cdot 3 + 0 \\ 3 &= 2 \cdot 1 + 1 \\ 1 &= 2 \cdot 0 + 1 \end{aligned}$$

Teraz jasne jest, że reszta w każdym kroku odpowiada wartości x na odpowiedniej pozycji: pierwsza reszta odpowiada pierwszemu x, druga reszta drugiemu x i tak dalej. Zatem liczba 12 binarnie, według opisanego wyżej algorytmu, zapisuje się jako 1100.

Pamiętaj, że zaczęliśmy od zamiaru pokazania, dlaczego działa algorytm z dzieleniem przez 2. Weźmy opisane wyżej kroki i przenieśmy 2 na lewą stronę wyrażeń:

$$\begin{aligned} 12 = 2 \cdot 6 + 0 &\rightarrow 12 : 2 = 6 + 0 \\ 6 = 2 \cdot 3 + 0 &\rightarrow 6 : 2 = 3 + 0 \\ 3 = 2 \cdot 1 + 1 &\rightarrow 3 : 2 = 1 + 1 \\ 1 = 2 \cdot 0 + 1 &\rightarrow 1 : 2 = 0 + 1 \end{aligned}$$

W ten sposób widać, jak doszliśmy do algorytmu opisanego na początku. Obliczenia z tych czterech kroków możemy też zapisać w jednej reprezentacji, o tak:

$$12 = 2 \cdot (\underbrace{2 \cdot (\overbrace{2 \cdot (\underbrace{2 \cdot 0 + 1}_{1}) + 1 \cdot 2^0}^{3}) + 0 \cdot 2^0}_{6}) + 0 \cdot 2^0$$

Upewnij się, że rozumiesz, jak dochodzimy do tej reprezentacji, bo będzie nam potrzebna przy badaniu, jak działa algorytm konwersji z systemu binarnego na dziesiętny.

Konwersja ułamka dziesiętnego na binarny

Żeby pokazać, dlaczego przy konwersji ułamków na system binarny mnożymy przez 2 i bierzemy część całkowitą, również posłużę się postacią rozwinięcia przy podstawie q — dla ułamków. Wezmę liczbę ułamkową 0.375 z pierwszej części artykułu. Podobnie jak przy części całkowitej, udajmy, że nie wiemy, jak ta liczba zapisuje się binarnie, i wypiszmy ją z nieznanymi cyframi zastąpionymi przez x:

$$0.375_{10} = x_1 \cdot 2^{-1} + x_2 \cdot 2^{-2} + \ldots + x_n \cdot 2^n$$

Tak jak przy liczbach całkowitych, naszym zadaniem jest znaleźć wszystkie x, wyodrębniając je pojedynczo. Zobaczmy, jak to zrobić. Pierwsze, co warto zauważyć, to że ujemne potęgi 2 dają nam ułamki z mianownikiem 2 w potęgach dodatnich. Przepiszmy powyższe wyrażenie:

$$0.375_{10} = x_1 \cdot \frac{1}{2} + x_2 \cdot \frac{1}{2^2} + \ldots + x_n \cdot \frac{1}{2^n}$$

Od razu widać, że w prawej części wyrażenia możemy po prostu wyłączyć 1/2 przed nawias. Zróbmy to:

$$0.375_{10} = \frac{1}{2} \cdot (x_1 + x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}})$$

a następnie przenieśmy 1/2 na lewą stronę

$$0.375 \cdot 2 = x_1 + x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}$$

Dobrze, wyodrębniliśmy x1 i wiemy, że może być równe 1 albo 0. Żeby ustalić, która to cyfra, spójrzmy na pozostałe składniki:

$$x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}$$

Zastanówmy się, jak duża może być suma tych liczb. Jeśli największa wartość cyfr x to 1, to możemy po prostu zastąpić x jedynkami i zapisać sumę jako:

$$\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \ldots + \frac{1}{2^n}$$

Cóż, jest to szereg geometryczny ułamków, a suma takiego szeregu mieści się w granicach [0 < suma < 1], więc maksimum, jakie ta suma może dać, to 1. Spójrzmy teraz ponownie na nasze wyrażenie:

$$0.375 \cdot 2 = x_1 + \underbrace{x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}}_{\text{co najwyżej } 1}$$

Teraz powinno być jasne, że jeśli prawa strona jest mniejsza od 1, to x1 nie może być równe 1, a więc równa się 0, podczas gdy pozostała część równa się 0.75.

$$0.375 \cdot 2 = 0 + \underbrace{x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}}_{0.75}$$

Wygląda to dokładnie jak pierwszy krok algorytmu przedstawionego na początku:

$$0.375 \cdot 2 = 0 + 0.75$$

Weźmy część ułamkową 0.75 i wyłączmy kolejną 1/2, żeby wyodrębnić x2:

$$0.75 = \frac{1}{2} \cdot (x_2 + \ldots + x_n \cdot \frac{1}{2^{n-2}})$$

i przenieśmy 1/2 na lewo:

$$\underbrace{0.75 \cdot 2}_{1.5} = x_2 + x_3 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-2}}$$

Teraz, jeśli x2 równa się 0, to suma po prawej stronie wyrażenia nie może być większa niż 1, ale lewa strona wynosi 1.5, więc x2 musi być 1, a pozostała część 0.5. Wypiszmy to:

$$\underbrace{0.75 \cdot 2}_{1.5} = 1 + \underbrace{x_3 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-2}}}_{0.5}$$

I znowu jest to zgodne ze schematem algorytmu przedstawionego na początku:

$$0.75 \cdot 2 = 1 + 0.5$$

Powtórzmy te same działania dla pozostałej części ułamkowej 0.5.

$$\underbrace{0.5 \cdot 2}_{1} = x_3 + \ldots + x_n \cdot \frac{1}{2^{n-3}}$$

Stosując tę samą logikę co wyżej, widzimy, że x3 równa się 1 i nie zostaje żadna część ułamkowa:

$$\underbrace{0.5 \cdot 2}_{1} = 1 + \underbrace{\ldots + x_n \cdot \frac{1}{2^{n-3}}}_{0}$$

Ponieważ pozostała część ułamkowa równa się 0, nasz ostatni krok wygląda tak:

$$0.5 \cdot 2 = 1 + 0$$

Wypiszmy więc wszystkie kroki jeszcze raz:

$$\begin{aligned} 0.375 \cdot 2 &= 0 + 0.75 \\ 0.75 \cdot 2 &= 1 + 0.5 \\ 0.5 \cdot 2 &= 1 + 0 \end{aligned}$$

To dokładnie ten algorytm, który przedstawiłem na początku. Tak samo jak przy liczbach całkowitych, obliczenia z tych trzech kroków możemy też zapisać w jednej reprezentacji:

$$0.375 = \frac{1}{2} \cdot (0 + \frac{1}{2} \cdot (1 + \frac{1}{2} \cdot (1 + 0)))$$

Znowu ważne jest, żebyś w pełni pojął tę reprezentację, bo będzie nam potrzebna przy omawianiu konwersji z binarnego na dziesiętny.

Dlaczego nie wszystkie ułamki da się skończenie zapisać binarnie

Fakt, że niektórych ułamków zapisywanych skończenie w systemie dziesiętnym nie da się zapisać skończenie w systemie binarnym, dla wielu programistów jest zaskoczeniem. Ale to właśnie z tego nieporozumienia bierze się pozornie dziwny wynik dodawania 0.1 do 0.2. Co zatem decyduje o tym, czy ułamek da się skończenie zapisać w danym systemie liczbowym? Otóż, żeby liczba dała się zapisać skończenie, mianownik ułamka musi być potęgą podstawy systemu. Na przykład dla systemu o podstawie 10 mianownik musi być potęgą 10 — i dlatego 0.625 możemy zapisać skończenie w systemie dziesiętnym:

$$\frac{625}{10^3} = 0.625$$

a 1/3 nie możemy zapisać skończenie:

$$\frac{1}{3} = 0.3333\ldots = 0.\overline{3}$$

Tak samo jest w systemie o podstawie 2:

$$\frac{625}{1000} = \frac{5}{8} = \frac{5}{2^3}$$

Ale jeśli sprawdzimy 0.1, mianownik wynosi 10 i nie jest potęgą 2, więc 0.1 będzie w systemie binarnym ułamkiem nieskończonym. Zobaczmy to za pomocą algorytmu, którego nauczyliśmy się wyżej:

$$\begin{aligned} 0.1 \cdot 2 &= 0 + 0.2 \\ 0.2 \cdot 2 &= 0 + 0.4 \\ 0.4 \cdot 2 &= 0 + 0.8 \\ 0.8 \cdot 2 &= 1 + 0.6 \\ 0.6 \cdot 2 &= 1 + 0.2 \\ 0.2 \cdot 2 &= 0 + 0.4 \\ 0.4 \cdot 2 &= 0 + 0.8 \\ &\ldots \end{aligned}$$

Moglibyśmy tak w nieskończoność, ale zapiszmy to jako ułamek okresowy:

$$0.1_{10} = 0.00011001100110011\ldots_2 = 0.0\overline{0011}$$

Konwersja binarnej liczby całkowitej na dziesiętną

Posłużę się tą samą binarną liczbą całkowitą 1011 z pierwszej sekcji, żeby pokazać, dlaczego algorytm z mnożeniem przez 2 działa. Tutaj również użyjemy postaci rozwinięcia przy podstawie q. Zapiszmy ją w tej postaci:

$$1011_2 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0$$

Ponieważ wszystkie składniki są wielokrotnościami 2, możemy wyłączać 2 przed nawias, aż iloraz będzie równy zeru. Zróbmy to:

$$1011_2 = 2 \cdot (2 \cdot (2 \cdot (2 \cdot 0 + 1) + 0) + 1) + 1$$

Teraz, jeśli po prostu zachowasz kolejność działań matematycznych, dojdziesz dokładnie do tych samych kroków, które pokazałem na początku, mianowicie:

$$11_{10} = 2 \cdot (\underbrace{2 \cdot (\overbrace{2 \cdot (\underbrace{2 \cdot 0 + 1}_{1}) + 0}^{2}) + 1}_{5}) + 1$$ $$\begin{aligned} 2 \cdot 0 + 1 &= 1 \\ 2 \cdot 1 + 0 &= 2 \\ 2 \cdot 2 + 1 &= 5 \\ 2 \cdot 5 + 1 &= 11 \end{aligned}$$

W ten sposób 1011 binarnie to 11 dziesiętnie.

Konwersja ułamka binarnego na dziesiętny

Doszliśmy do ostatniego algorytmu. Prawdopodobnie sam już rozgryzłeś jego mechanikę. Jeśli nie, zobaczmy, dlaczego działa. Postać rozwinięcia przy podstawie q i tutaj jest kluczem. Weźmiemy liczbę 0.1011 z pierwszej sekcji. Zapiszmy ją w postaci rozwiniętej:

$$0.1011_2 = 1 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2^2} + 1 \cdot \frac{1}{2^3} + 1 \cdot \frac{1}{2^4}$$

Znowu, ponieważ wszystkie składniki są wielokrotnościami 1/2, możemy wyłączać 1/2 przed nawias, aż nie zostanie żadna część ułamkowa. Zróbmy to:

$$0.1011_2 = \frac{1}{2} \cdot (1 + \frac{1}{2} \cdot (0 + \frac{1}{2} \cdot (1 + \frac{1}{2} \cdot (1 + 0))))$$

Zachowanie kolejności działań matematycznych daje algorytm nakreślony na początku:

$$0.6875_{10} = \underbrace{\frac{1}{2} \cdot (1 + \overbrace{\frac{1}{2} \cdot (0 + \frac{1}{2} \cdot (1 + \underbrace{\frac{1}{2} \cdot (1 + 0)}_{0.5}))}^{0.75})}_{0.375}$$ $$\begin{aligned} \frac{1}{2} \cdot (1 + 0) &= 0.5 \\ \frac{1}{2} \cdot (1 + 0.5) &= 0.75 \\ \frac{1}{2} \cdot (0 + 0.75) &= 0.375 \\ \frac{1}{2} \cdot (1 + 0.375) &= 0.6875 \end{aligned}$$

W ten sposób 0.1011 binarnie to 0.6875 dziesiętnie.