Zanim przystąpimy do implementacji algorytmu konwersji liczb z systemu dwójkowego na dziesiętny, przypomnijmy, w jaki sposób dokonywane jest takie przekształcenie. Przeanalizujmy przykład zamiany liczby zapisanej w systemie dwójkowym (binarnym) na system dziesiętny, czyli o podstawie 10. Ułatwi to późniejsze zaimplementowanie algorytmu w języku C++.

Dokonamy konwersji liczby 1011 z systemu dwójkowego na dziesiętny.

Jak rozwiązalibyśmy to zadanie, gdybyśmy mieli do dyspozycji kartkę i długopis?

R1TfcDsUYaSBP

Ilustracja. Wiersz pierwszy: 1011 indeks dolny (2) koniec indeksu dolnego równa się ( ) indeks dolny (10) koniec indeksu dolnego, wiersz drugi: $1·2^0+1·2^1+0·2^2+1·2^3=$, wiersz trzeci: 1 + 2 + 0 + 8 = 11a się ( ) indeks dolny (10) koniec indeksu dolnego, wiersz drugi: $1·2^0+1·2^1+0·2^2+1·2^{3=}$, wiersz trzeci: 1 + 2 + 0 + 8 = 11

Konwersja polega na mnożeniu kolejnych bitów (zaczynając od najmłodszego bitunajmłodszy bitnajmłodszego bitu i kończąc na najstarszym bicienajstarszy bitnajstarszym bicie) przez wagę pozycji, czyli kolejne potęgi liczby 2 (zaczynając od potęgi zerowej). Po zsumowaniu iloczynów częściowych otrzymamy wynik – liczbę zapisaną w systemie dziesiętnym.

Oto wynik końcowy wraz z odpowiednim zapisem:

Komputerowa realizacja w języku C++

Teraz zastanówmy się, jak zaimplementować omówiony algorytm przy użyciu języka programowania C++.

Algorytm zamiany liczby z systemu binarnego na system dziesiętny zapiszemy w ciele funkcji o nazwie konwertujBinDec(). Zwróci ona zmienną typu całkowitego (int) – będzie to liczba przekształcona do postaci dziesiętnej. Jako argument funkcja przyjmie liczbę zapisaną w systemie binarnym i przechowywaną w zmiennej typu string liczbaBin. Dlaczego użyjemy zmiennej typu string? W tym przypadku łatwiej będzie użyć właśnie tego typu zmiennej – podczas konwersji potrzebna jest znajomość wartości liczbowych poszczególnych cyfr, nie zaś całej liczby.

#include <string>

#include <iostream>
#include <string>
using namespace std;

int konwertujBinDec(string liczbaBin) {

}

Następnie zadeklarujmy kilka zmiennych:

• int wynik – zmienna, w której będziemy sumować kolejne iloczyny częściowe powstałe wskutek mnożenia wag przez bity. Będzie to wartość zwracana przez funkcję konwertujBinDec(),

• int waga – będzie przyjmować kolejne wagi bitów, czyli kolejne potęgi liczby 2,

• int bit – do niej zapiszemy konkretny bit konwertowanej liczby.

#include <iostream>
#include <string>
using namespace std

int konwertujBinDec(string liczba_bin) {
	int wynik = 0;
	int waga = 1;
	int bit = 0;
}

Zmienna waga na początku przyjmuje wartość 1, ponieważ wagą najmłodszego bitu jest 2Indeks górny 0⁰, czyli 1.

Napiszmy teraz pętlę typu for, w której kolejne bity, zaczynając od najmłodszego, będą mnożone przez odpowiadające im wagi.

int konwertujBinDec(string liczbaBin) {
	int wynik = 0;
	int waga = 1;
	int bit = 0;

	for (int i = liczbaBin.length() - 1; i >= 0; i--) {
		bit = liczbaBin[i] - '0';
		wynik = wynik + bit * waga;
		waga = waga * 2;
	}

	return wynik;
}

Omówmy teraz poszczególne fragmenty kodu.

• int bit = liczbaBin[i] - '0' → w zmiennej typu int zapisujemy zmienną typu string i odejmujemy od niej liczbę odpowiadającą w kodzie ASCII znakowi zera. Dzięki temu w zmiennej bit zostaje zapisana liczba 0 lub 1. Zmienna liczbaBin[i] w kodzie ASCII to znak '0' lub '1' (ponieważ tylko takie liczby mogą pojawić się w systemie binarnym), a odpowiadające tym znakom liczby to, kolejno, 48 i 49. Oznacza to, że jeżeli liczbaBin[i] będzie znakiem '1', zostanie wykonane działanie 49–48, czyli zmienna bin przyjmie wartość liczbową 1. Jeżeli natomiast liczbaBin[i] będzie znakiem '0', wykonane zostanie działanie 48–48, a zmienna bin przyjmie wartość liczbową 0,

• wynik = wynik + bit * waga → dodajemy kolejne iloczyny częściowe,

• waga = waga * 2 → aby uzyskać wagę kolejnej pozycji, mnożymy aktualną wagę razy podstawę systemu, czyli 2.

Napiszmy kod, który umożliwi użytkownikowi wpisanie własnej liczby w celu wykonania konwersji do systemu dziesiętnego. Skorzystamy ze strumienia cin. Przeanalizujmy poniższy fragment kodu:

string liczbaTest;

cin >> liczbaTest;

Oczywiście musimy zadeklarować zmienną liczbaTest, do której zapisana zostanie informacja podana przez użytkownika.

Kolejnym krokiem będzie wywołanie funkcji konwertujBinDec() dla argumentu liczbaTest i wypisanie wyniku (czyli liczby przekształconej do postaci dziesiętnej). W tym przypadku posłużymy się strumieniem cout.

Oto kod całego programu:

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int konwertujBinDec(string liczbaBin) {
	int wynik = 0;
	int waga = 1;
	int bit = 0;

	for (int i = liczbaBin.length() - 1; i >= 0; i--) {
		bit = liczbaBin[i] - '0';
		wynik = wynik + bit * waga;
		waga = waga * 2;
	}

	return wynik;
}

int main() {
	string liczbaTest;
    
	cin >> liczbaTest;
	cout << konwertujBinDec(liczbaTest);

	return 0;
}

Alternatywnym rozwiązaniem powyższego problemu jest zastosowanie schematu Hornera przy konwersji. Pozwoli to zmniejszyć złożoność obliczeniową algorytmu do złożoności liniowej.

Poniższej przedstawiona została implementacja rozwiązania alternatywnego:

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int konwertujBinDec(string liczbaBin) {
	int wynik = 0;
	int bit = 0;

	for (int i = 0; i < liczbaBin.size(); i++) {
		bit = liczbaBin[i] - '0';
		wynik = wynik * 2 + bit;
	}

	return wynik;
}

int main() {
	string liczbaTest;
    
	cin >> liczbaTest;
	cout << konwertujBinDec(liczbaTest);

	return 0;
}

Konwersja części ułamkowej

Konwersja części ułamkowej z systemu binarnego na dziesiętny przebiega bardzo podobnie do przekształcania części całkowitej. Mnożymy kolejne bity przez wagi pozycji, jednak tym razem są one kolejnymi potęgami odwrotności podstawy systemu, czyli liczby 2.

Posłużmy się przykładem:

RduAzhfvp5X3c

Ilustracja. Wiersz pierwszy: 0,1101 indeks dolny (2) koniec indeksu dolnego równa się ( ) indeks dolny (10) koniec indeksu dolnego, wiersz drugi: $1·2^{-1}+1·2^{-2}+0·2^{-3}+1·2^{-4}=$, wiersz trzeci: 0,5 + 0,25 + 0 + 0,0625 = 0,8125

Mnożymy kolejne bity (zaczynając od bitu umieszczonego skrajnie po lewej stronie) przez wagę pozycji, czyli przez kolejne odwrotności potęgi liczby 2 (zaczynając od 2Indeks górny -1^-1). Następnie sumujemy iloczyny częściowe. Tak otrzymany wynik jest ułamkiem zapisanym w systemie dziesiętnym.

Słownik