Strona główna » Algorytmy » Artykuły » Przeliczanie systemów liczbowych

Przeliczanie systemów liczbowych

· Liczby całkowite · Ułamki ·

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·102 + 2·10 + 3·100

Ł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 an.

Przykłady systemów

SystemInaczejPodstawaCyfryPrzykład użycia
dwójkowybinarny20, 1system binarny jest podstawą wszystkiego związanego z informatyką
ósemkowyoktalny80 - 7w system UNIX do reprezentowania poziomu dostępu do pliku
szesnastkowyheksadecymalny160 - 9, A - Fokreślanie koloru podczas stylizowania strony

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:

IteracjaOperacjaWynikAktualna liczba
#121 / 210 r. 11
#210 / 25 r. 001
#35 / 22 r. 1101
#42 / 21 r. 00101
#51 / 20 r. 110101

Liczba a wynosi już 0, więc nie wykonujemy iteracji #6. W ten sposób odczytujemy, że 2110 = 101012.

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 ni-1.

Weźmy przykładowo 101213. Chcąc przeliczyć wyliczamy kolejne pozycje:1·34 + 0·33 + 1·32 + 2·3 + 1·30 = 81 + 0 + 9 + 6 + 1 = 97. Z tego możemy odczytać, że 101213 = 9710.

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ć 183 na system ósemkowy:

183 = 1·3 + 8 = 1110

IteracjaKrok 1Krok 2Aktualna liczba
#111 / 81 r. 33
#21 / 80 r. 113

Z tego odczytujemy, że 183 = 138.

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ę 101011112:


KrokLiczba
#0101011112
#1010210121112
#2210510710
#32578
Analogicznie wykonujemy zamianę systemu binarnego na szesnastkowy.

Szybka konwersja - szesnastkowy na binarny

Algorytm wygląda następująco:

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

Przykładowo zamienimy liczbę 2116:

KrokLiczba
#02116
#1210110
#20010201012
#31001012

W ten sposób wyliczamy, że 2116 = 1001012.

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.

  1.   char* wynik = new char[dl + 1];
  2.   for(int i = dl, pot = 1; i >= 0; i--){
  3.     wynik[i - 1] = getCharValue(a % n);
  4.     a /= n;
  5.   }
  6.   wynik[dl]='\0';
  7.   return wynik;
  8. }

(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. }

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.