Przeliczanie systemów liczbowych

System pozycyjny

Codziennie posługujemy się systemem dziesiętnym zwanym inaczej decymalnym. Jest to system pozycyjny co oznacza, że liczba składa się z cyfr, których wartość zależy od pozycji oraz podstawy systemu. Rozpatrzmy przykładowo liczbę 123. System dziesiętny ma podstawę 10 czyli możemy liczbę zapisać jako:

123 = 100 + 20 + 3 = 1·10² + 2·10 + 3·10⁰

Łatwo zauważyć, że cyfra na i-tej pozycji od prawej strony ma wartość i-ta cyfra pomnożona przez 10 do i-1.

Inne systemy pozycyjne

System pozycyjny może mieć dowolną podstawę n. Oznacza to, że na dowolnej pozycji mamy n różnych sposobów zapisania cyfry. Rezultatem tego jest, że liczba na i-tej pozycji od prawej strony ma wartość i-ta cyfra pomnożona przez n do i-1. W celu odróżnienia liczb w różnych system zapisach przyjmuje się, że liczba a o bazie n zapisuje się jako a_n.

Przykłady systemów

Przeliczanie systemu dziesiętnego na inny

Weźmy liczbę a z systemu dziesiętnego. Chcąc przeliczyć ją do innego systemu o podstawie n należy:

1. Podziel liczbę przez n i pobierz resztę z dzielenia.
2. W i-tym kroku zapisz cyfrę na i-tej pozycji od prawej strony
3. Jeśli a jest różne od 0 to wróć do (1.)

Przykład

Weźmy przykładowo liczbę 21, które chcemy przeliczyć na system binarny:

Liczba a wynosi już 0, więc nie wykonujemy iteracji #6. W ten sposób odczytujemy, że 21₁₀ = 10101₂.

Inny system na dziesiętny

Weźmy liczbę a o bazie n. Chcąc przeliczyć ją do systemu dziesiętnego należy zsumować wartości wszystkich cyfr liczby pamiętając, że i-ta cyfra ma wartość i-tej cyfry pomnożona przez n^i-1.

Weźmy przykładowo 10121₃. Chcąc przeliczyć wyliczamy kolejne pozycje:1·3⁴ + 0·3³ + 1·3² + 2·3 + 1·3⁰ = 81 + 0 + 9 + 6 + 1 = 97. Z tego możemy odczytać, że 10121₃ = 97₁₀.

Przeliczanie między dowolnymi systemami

Załóżmy, że mamy liczbę a z systemu m i chcemy przeliczyć ją na system n. Dokonujemy tego:

1. Zamieniając liczbę a z systemu m na dziesiętny
2. Powstałą liczbę przeliczamy na system n

Przykładowo chcemy przeliczyć 18₃ na system ósemkowy:

18₃ = 1·3 + 8 = 11₁₀

Z tego odczytujemy, że 18₃ = 13₈.

Szybka konwersja - binarny na ósemkowy

Algorytm wygląda następująco:

1. Począwszy od prawej grupujemy cyfry liczby binarnej po 3
2. Każdą grupkę zamieniamy na system ósemkowy

Przykładowo zamienimy liczbę 10101111₂:

Szybka konwersja - szesnastkowy na binarny

Algorytm wygląda następująco:

1. Każdą cyfrę przeliczamy na system binarny

Przykładowo zamienimy liczbę 21₁₆:

Różne systemy liczbowe w C++

C++ pozwala wprowadzać bezpośrednio liczby w systemie ósemkowym, dziesiętnym i szesnastkowym. System dziesiętny wprowadzamy bez zastanowienia:

1. int a = 75; // a = 75

W przypadku, gdy chcemy wprowadzić liczbę w systemie ósemkowym to na początku liczby używamy 0:

1. int a = 075; // a = 61

Z kolei dla systemu szesnastkowego jest to 0x:

1. int a = 0x75; // a = 117

Implementacja przeliczania

Wartość cyfry

Ze względu na różne liczby to będziemy przechowywać ich wartości w tablicy char*. W ten sposób będziemy mogli wprowadzić liczbę nawet w systemie szesnastkowym. Taki sposób zapisu nie pozwala na wykonywanie operacji arytmetycznych, ponieważ każda cyfra będzie miała wartość ASCII, a nie dziesiętną, dlatego stworzymy funkcję pomocniczą getIntValue().

1. int getIntValue(char c){
2.   if(c >= '0' && c <= '9')
3.     return c - '0';
4.   if(c >= 'A' && c <= 'F')
5.     return 10 + c - 'A';
6.   return 0;
7. }

(2.) Jeśli znak jest cyfrą to (2.) zwracamy pozycję znaku minus pozycję znaku 0. (3.) Jeśli znak to litera od A do F to (4.) zwracamy pozycję znaku - pozycją znaku A i dodajemy 10, ponieważ A ma wartość dziesiętną 10 w systemie szesnastkowym.

Wartość liczby

Potrzebujemy jeszcze funkcji, która na podstawie wartości cyfry określi jej reprezentacje przy pomocy znaku:

1. char getCharValue(int a){
2.   if(a >= 0 && a <= 9)
3.     return '0' + a;
4.   if(a >= 10 && a <= 15)
5.     return 'A' + a - 10;
6.   return ' ';
7. }

Przeliczanie liczby na system dziesiętny

Jako argumenty otrzymamy liczbę a jako char* oraz jej system n jako int. Naszym zadaniem jest zwrócenie wartości w systemie dziesiętnym.

1. int anyToDecimal(char* a, int n){
2.   int liczba = 0;
3.   for(int i = strlen(a) - 1, pot = 1; i >= 0; i--){
4.     liczba += getIntValue(a[i])*pot;
5.     pot *= n;
6.   }
7.   return liczba;
8. }

(2.) Liczbę w systemie dziesiętnym przechowamy w standardowej zmiennej int. Dalej (3.) Dla każdej cyfry w liczbie - zaczynając od najmniej znaczącej, czyli od pierwszej od prawej: (4.) Wyliczamy wartość cyfry na pozycji i i o tyle zwiększamy liczba. (5.) Zwiększamy potęgę, aby w następnym kroku prawidłowo wyliczyć wartość cyfry na następnej pozycji. Na koniec (7.) zwracamy liczba.

System dziesiętny na dowolny

Liczbę wynikową zapiszemy w tablicy char*, dlatego na początek obliczymy długość tekstu wynikowego:

1. char* decimalToAny(int a, int n){
2.   int dl = 0;
3.   int pot = 1;
4.   while(a > pot){
5.     pot*=n;
6.     dl++;
7.   }

(2.) dl przechowa nam długość tekstu wynikowego, a (2.) pot pomoże nam określić jak dużą potęgę znajdziemy w konwertowanej liczbie. (4.) Dopóki potęga jest niższa od liczby to oznacza to, że w podanej długości nie zmieścimy liczby wynikowej, więc (5.) obliczamy kolejną potęge i (6.) zwiększamy długość tekstu, aż (4.) pot będzie większa od n.

8.   char* wynik = new char[dl + 1];
9.   for(int i = dl, pot = 1; i >= 0; i--){
10.     wynik[i - 1] = getCharValue(a % n);
11.     a /= n;
12.   }
13.   wynik[dl]='\0';
14.   return wynik;
15. }

(8.) Alokujemy pamięć pod tekst wynikowy. (9.) Znamy długość tekstu wynikowego, więc tyle wykonamy iteracji pętli for, gdzie (10.) Obliczymy resztę z dzielenia w i-tym kroku i zapiszemy od wynik oraz podzielimy a przez n. Nie martwimy się o część ułamkową, ponieważ dzielenie liczb całkowitych da liczbę całkowitą. Na koniec (13.) dopisujemy znak końca danych i (14.) zwracamy wynik.

Testowanie funkcji

Poniższa funkcja main() prezentuje przykładowe zastosowanie napisanych funkcji:

1. int main () {
2.   char* a = "75";
3.   int b = anyToDecimal(a,16);
4.   cout << b << endl;
5.   char* c = decimalToAny(b, 8);
6.   cout << c << endl;
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Dostosuj funkcje getIntValue() oraz getCharValue(), aby można było wykonać konwersję z /do systemu osiemnastkowego

Zadanie 2

Dopisz funkcję goodNumSys(), która sprawdzi czy dana liczba jest prawidłowo zapisana w danym systemie.

• Kod źródłowy Zadanie 1, 2