Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
Kody binarne są bardzo elastyczne. Komputery potrafią przetwarzać każdą informację, jeśli tylko zostanie ona odwzorowana w kod binarny ( obrazy, filmy, dźwięk, dane z czujników, itp. ). Liczby naturalne ( ang. natural numbers ) pojawiły się jako pierwsze w naszej historii wiele tysiącleci temu. Są to liczby: 1, 2, 3, ... Tworzą one ciąg nieskończony, co oznacza, iż nie istnieje największa liczba naturalna. Dowód jest banalnie prosty: dwie kolejne liczby naturalne n i m różnią się od siebie o 1:
Załóżmy, że istnieje największa liczba naturalna nn. Tworzymy z niej liczbę mm:
Liczba mm jest również liczbą naturalną, ponieważ różni się ona od nn o 1:
Ponieważ mm jest większe o 1 od nn, liczba nn nie może być największą liczbą naturalną, a to przeczy założeniu. Prawdziwe jest zatem twierdzenie odwrotne: nie istnieje największa liczba naturalna.
Tak jest w matematyce. W informatyce niekoniecznie jest to prawdą. Na początek określimy tzw. naturalny kod binarny ( ang. NBC, natural binary code ). Konstrukcję kodu przeprowadzimy krok po kroku na przykładzie bajtu, aby wszystko było zrozumiałe. Jeśli jest to dla ciebie zbyt proste, przejdź do dalszej części rozdziału.
Bajt jest grupą 8 bitów, z których każdy może przyjmować stan 0 lub 1. Zapiszmy bitowo kilka bajtów:
00000000 11111111 10000001 00011000 11101001 |
W takiej postaci trudno nam prowadzić dalsze rozważania. Dlatego zapiszmy symbolicznie każdy bit za pomocą literki b ( b – bit ):
bbbbbbbb |
Dalej, aby rozróżniać poszczególne bity w bajcie, ponumerujemy je następująco:
b7b6b5b4b3b2b1b0 |
Numery bitów nazwijmy numerami pozycji i oznaczmy symbolicznie literką p. Bit bp oznacza bit znajdujący się na p-tej pozycji w bajcie, gdzie p = 0,1,2,...,7.
Skojarzmy z każdą pozycją p wartość równą 2p, którą będziemy nazywać wagą pozycji. Umówmy się, że bit na pozycji p-tej ma wartość równą iloczynowi bp x 2p. Jeśli bit bp ma stan 0, to wartość ta wynosi 0. Jeśli bit bp ma stan 1, to wartość bitu wynosi 2p. Wartość całego kodu w bajcie jest sumą tych iloczynów. Dla przykładu weźmy kod 11011101. Policzmy jego wartość:
Waga: | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
Bit: | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
Pozycja: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Policzmy wartości wag pozycji:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
Wymnóżmy wartości wag pozycji przez bity kodu:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Wartość: | 128 | 64 | 0 | 16 | 8 | 4 | 0 | 1 |
Zsumujmy wartości tych iloczynów:
128 + 64 + 16 + 8 + 4 + 5 = 221 |
Zatem:
11011101(NBC) = 221 |
Co uzyskaliśmy do tej pory? Potrafimy obliczyć wartość dowolnego kodu 8-bitowego. Zwróć uwagę na pewne prawidłowości, które warto zapamiętać:
Wynika z tego prosty algorytm obliczania wartości dowolnego kodu NBC:
Bitów może być dowolnie wiele.
Dla przykładu policzmy wartość kodu 111010110111. Najpierw wyznaczamy wagi pozycji, poczynając od ostatniej:
Waga: | 1 | |||||||||||
Bit: | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Kolejne wagi otrzymujemy mnożąc poprzednią przez 2 ( nie musisz w ten sposób pamiętać wartości tych wag ):
Waga: | 2048 | 1024 | 512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Sumujemy wagi pozycji, na których stoją bity 1 ( można to robić od końca lub od początku kodu ):
2048 + 1024 + 512 + 128 + 32 + 16 + 4 + 2 + 1 = 3767 |
Warto wykonać samodzielnie kilka takich obliczeń. Można też posłużyć się kalkulatorem, jeśli posiada funkcje programisty ( np. kalkulator z Windows ):
Zastanówmy się, ile różnych liczb można zakodować przy pomocy n-bitowego kodu NBC. Liczba ta jest równa liczbie kombinacji bitów. Każdy bit może przyjmować 2 kombinacje, zatem dla n bitów mamy:
Wynika z tego, iż bajt zawierający 8 bitów potrafi zakodować 28 = 256 różnych liczb. Ponieważ są to kolejne liczby naturalne od 0 w górę, to otrzymujemy zakres od 0 do 255 ( kolejna własność: największą n-bitową liczbą w kodzie NBC jest zawsze liczba o wartości 2n - 1 ).
n-bitowa liczba NBC posiada zakres od 0 do 2n - 1. Oto kilka przykładowych zakresów:
Liczba bitów | Zakres |
1 | 0 ... 1 |
2 | 0 ... 3 |
4 | 0 ... 15 |
8 | 0 ... 255 |
16 | 0 ... 65535 |
32 | 0 ... 4294967295 |
64 | 0 ... 18446744073709551615 |
Kolejne wyrazy kodu NBC budujemy w bardzo prosty sposób. Pokażemy to na przykładzie kodu 4-bitowego. Dla większej liczby bitów jest podobnie. 4 bity kodują 16 liczb naturalnych od 0 do 15. Wypełnimy bitami tego kodu tabelkę:
b3 | b2 | b1 | b0 | Wartość |
0 | ||||
1 | ||||
2 | ||||
3 | ||||
4 | ||||
5 | ||||
6 | ||||
7 | ||||
8 | ||||
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 | ||||
15 |
Zaczynamy od najmłodszego bitu b0. Tutaj na przemian umieszczamy 0 i 1:
b3 | b2 | b1 | b0 | Wartość |
0 | 0 | |||
1 | 1 | |||
0 | 2 | |||
1 | 3 | |||
0 | 4 | |||
1 | 5 | |||
0 | 6 | |||
1 | 7 | |||
0 | 8 | |||
1 | 9 | |||
0 | 10 | |||
1 | 11 | |||
0 | 12 | |||
1 | 13 | |||
0 | 14 | |||
1 | 15 |
Teraz bit b1. Ten zmienia się co dwie liczby. Zaczynamy od 0:
b3 | b2 | b1 | b0 | Wartość |
0 | 0 | 0 | ||
0 | 1 | 1 | ||
1 | 0 | 2 | ||
1 | 1 | 3 | ||
0 | 0 | 4 | ||
0 | 1 | 5 | ||
1 | 0 | 6 | ||
1 | 1 | 7 | ||
0 | 0 | 8 | ||
0 | 1 | 9 | ||
1 | 0 | 10 | ||
1 | 1 | 11 | ||
0 | 0 | 12 | ||
0 | 1 | 13 | ||
1 | 0 | 14 | ||
1 | 1 | 15 |
Bit b2 zmienia się co 4 liczby:
b3 | b2 | b1 | b0 | Wartość |
0 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 2 | |
0 | 1 | 1 | 3 | |
1 | 0 | 0 | 4 | |
1 | 0 | 1 | 5 | |
1 | 1 | 0 | 6 | |
1 | 1 | 1 | 7 | |
0 | 0 | 0 | 8 | |
0 | 0 | 1 | 9 | |
0 | 1 | 0 | 10 | |
0 | 1 | 1 | 11 | |
1 | 0 | 0 | 12 | |
1 | 0 | 1 | 13 | |
1 | 1 | 0 | 14 | |
1 | 1 | 1 | 15 |
I ostatni bit b3 zmienia się co 8 liczb ( zauważyłeś już prawidłowość? ):
b3 | b2 | b1 | b0 | Wartość |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 2 |
0 | 0 | 1 | 1 | 3 |
0 | 1 | 0 | 0 | 4 |
0 | 1 | 0 | 1 | 5 |
0 | 1 | 1 | 0 | 6 |
0 | 1 | 1 | 1 | 7 |
1 | 0 | 0 | 0 | 8 |
1 | 0 | 0 | 1 | 9 |
1 | 0 | 1 | 0 | 10 |
1 | 0 | 1 | 1 | 11 |
1 | 1 | 0 | 0 | 12 |
1 | 1 | 0 | 1 | 13 |
1 | 1 | 1 | 0 | 14 |
1 | 1 | 1 | 1 | 15 |
Jak widzisz, nie są potrzebne żadne rachunki.
W języku C++ liczby całkowite reprezentowane są typami danych:
Nazwa typu | Liczba bajtów | Liczba bitów | Zakres |
unsigned char | 1 | 8 | 0...255 |
unsigned short int | 2 | 16 | 0...65535 |
unsigned int | 4 | 32 | 0 ... 4294967295 |
unsigned long long int | 8 | 64 | 0 ... 18446744073709551615 |
Dla pewności skompiluj i uruchom poniższy program:
Przykładowy program w języku C++
// Sprawdzenie typów danych NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------ #include <iostream> #include <iomanip> using namespace std; int main() { unsigned char cv; unsigned short int sv; unsigned int iv; unsigned long long int lv; setlocale(LC_ALL,""); lv = 0; lv--; // W lv wartość maksymalna cv = sv = iv = lv; // We wszystkich zmiennych wartości maksymalne // Wyniki cout << "Liczby naturalne w typach danych języka C++" << endl << "-------------------------------------------" << endl << endl; cout << "Nazwa typu Bajty Bity Zakres" << endl; cout << left << setw(22) << "unsigned char" << right << setw(5) << sizeof(cv) << setw(5) << sizeof(cv) * 8 << " 0 ... " << (int)cv << endl; cout << left << setw(22) << "unsigned short int" << right << setw(5) << sizeof(sv) << setw(5) << sizeof(sv) * 8 << " 0 ... " << sv << endl; cout << left << setw(22) << "unsigned int" << right << setw(5) << sizeof(iv) << setw(5) << sizeof(iv) * 8 << " 0 ... " << iv << endl; cout << left << setw(22) << "unsigned long long int" << right << setw(5) << sizeof(lv) << setw(5) << sizeof(lv) * 8 << " 0 ... " << lv << endl; return 0; } |
Wynik |
Liczby naturalne w typach danych języka C++ ------------------------------------------- Nazwa typu Bajty Bity Zakres unsigned char 1 8 0 ... 255 unsigned short int 2 16 0 ... 65535 unsigned int 4 32 0 ... 4294967295 unsigned long long int 8 64 0 ... 18446744073709551615 |
Jak przekształcić liczbę dziesiętną w odpowiadającą jej liczbę NBC? Istnieje tutaj wiele algorytmów, ale nie będziemy się ich uczyć, ponieważ nie jest to celem metod numerycznych. Jeśli koniecznie musisz przekształcać takie liczby, skorzystaj z kalkulatora programisty. Zainteresowanych głębiej tym tematem odsyłam do artykułu "Binarne kodowanie liczb". Podam bardzo prosty sposób, który być może nie jest najefektywniejszy, lecz łatwo go zrozumieć.
Załóżmy, że chcemy przekształcić liczbę 91 na liczbę NBC 8-bitową. Budujemy tabelkę na poszczególne bity kodu NBC. Ponad miejscami na cyfry zapisujemy wagi pozycji:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | ? | ? | ? | ? | ? | ? | ? | ? |
Zaczynamy od najstarszego bitu. Bit ten musi wynosić 0, ponieważ waga 128 > 91:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | ? | ? | ? | ? | ? | ? | ? |
Przechodzimy do bitu o wadze 64. Ten bit będzie miał stan 1, ponieważ 64 < 91:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | ? | ? | ? | ? | ? | ? |
Ponieważ mamy już wartość 64, to musimy ją odjąć od 91, aby znaleźć kolejne bity:
91 - 64 = 27 |
To nowa wartość, którą w podobny sposób kodujemy na pozostałych bitach. Waga 32 nie wchodzi do kodu NBC, ponieważ 32 > 27:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | 0 | ? | ? | ? | ? | ? |
Przechodzimy do wagi 16, ponieważ 16 < 27, waga ta wchodzi do kodu NBC:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | 0 | 1 | ? | ? | ? | ? |
Wagę 16 odejmujemy od liczby 27: 27 - 16 = 11. Otrzymaliśmy nową wartość, kontynuujemy z wagą 8, ponieważ 8 < 11, waga 8 wchodzi do kodu NBC:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | 0 | 1 | 1 | ? | ? | ? |
Odejmujemy wagę 8 od 11: 11 - 8 = 3 i otrzymujemy nową liczbę 3. Waga 4 nie wchodzi do kodu NBC, ponieważ 4 > 3:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | 0 | 1 | 1 | 0 | ? | ? |
Waga 2 wchodzi do kodu NBC, ponieważ 2 < 3:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | 0 | 1 | 1 | 0 | 1 | ? |
Odejmujemy: 3 - 2 = 1. Ostatnia waga wchodzi do kodu NBC:
Waga: | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Bit: | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Mamy wszystkie bity, ponieważ 1 - 1 = 0. Ponieważ wagi odejmowaliśmy od konwertowanej wartości aż do otrzymania zera, to suma tych wag da nam liczbę wyjściową:
1 + 2 + 8 + 16 + 64 = 91 |
Zatem:
91 = 01011011(NBC) |
Wypróbuj poniższy program. Przekształca on wprowadzoną liczbę dziesiętną w liczbę binarną w kodzie NBC. Zera wiodące ( bity o stanie 0 na początku liczby ) są pomijane w wyniku.
Przykładowy program w języku C++
// Przeliczanie na NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------ #include <iostream> using namespace std; int main() { unsigned long long int m,v; setlocale(LC_ALL,""); cout << "Przeliczanie liczb naturalnych na liczby binarne w kodzie NBC" << endl << "-------------------------------------------------------------" << endl << endl; cout << "Podaj liczbę naturalną lub zero : "; cin >> v; // Odczytujemy liczbę do konwersji // Komputer przechowuje liczbę w pamięci w kodzie NBC. // Nic nie musimy przeliczać. Zrobi to komputer za nas. cout << v << " = "; if(v) { // Szukamy pozycji pierwszego bitu 1 for(m = 0x1000000000000000L; !(v & m); m >>= 1); // Począwszy od tej pozycji do pozycji 0 wyświetlamy wszystkie bity liczby while(m) { cout << ((v & m) > 0); m >>= 1; } } else cout << 0; cout << "(NBC)" << endl; return 0; } |
Wynik |
Przeliczanie liczb naturalnych na liczby binarne
w kodzie NBC ------------------------------------------------------------- Podaj liczbę naturalną lub zero : 2019 2019 = 11111100011(NBC) |
Operacje dodawania i mnożenia dla liczb naturalnych zapisanych w kodzie NBC dają dobre wyniki pod warunkiem, iż wyniki te mieszczą się w zakresie liczb danego typu. Na przykład liczby 8-bitowe NBC mają zakres od 0 do 255. Zatem dodawanie:
100 + 100 = 200 |
da poprawny wynik, ponieważ 200 < 255. Jednak dodawanie:
100 + 200 = 300 |
nie da poprawnego wyniku, ponieważ liczba 300 jest większa od maksymalnej liczby, którą można przedstawić kodem 8-bitowym. Co dostaniemy w wyniku? Otrzymamy wynik obcięty do 8 młodszych bitów:
300 = 100101100(NBC) = 00101100(NBC8) = 44 |
Bit zaznaczony na czerwono jest 9-tym bitem kodu i zostanie pominięty w wyniku. Dlatego otrzymasz wartość 44, a nie spodziewane 300. Taka sytuacja nazywa się nadmiarem ( ang. overflow ). Nadmiar oznacza przekroczenie dopuszczalnego zakresu i zawsze prowadzi do błędu. Wykonując obliczenia na liczbach naturalnych powinieneś sprawdzać, czy nie doprowadzą one do nadmiaru.
W języku C++ nadmiar możemy wykryć, jeśli obliczenia wykonujemy w typie wyższym ( np. unsigned int ), a wyniki przekształcamy na typ niższy ( np. unsigned char ).
Poniższy program odczytuje dwie liczby 8-bitowe, a następnie dodaje je i wyświetla wynik, sprawdzając, czy nie pojawił się nadmiar.
Przykładowy program w języku C++
// Dodawanie dwóch liczb 8-bitowych NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------ #include <iostream> using namespace std; int main() { unsigned int a,b,ir; unsigned char cr; setlocale(LC_ALL,""); cout << "Dodawanie 8-bitowych liczb naturalnych" << endl << "--------------------------------------" << endl << endl; // Liczby wczytujemy jako 32-bitowe cout << "a = "; cin >> a; cout << "b = "; cin >> b; // Wczytane liczby obcinamy do 8 bitów a &= 0x000000ff; b &= 0x000000ff; // Wykonujemy dodawanie cr = ir + a + b; // Wyświetlamy wyniki cout << a << " + " << b << " = " << (unsigned int)cr; // Sprawdzamy, czy wynik jest poprawny, czy z nadmiarem if(ir == cr) cout << " : Wynik poprawny"; else cout << " : Wynik błędny, NADMIAR!!!"; cout << endl << endl; return 0; } |
Przykładowe wyniki ( zakres 8-bitowych liczb NBC wynosi od 0 do 255 ):
Dodawanie 8-bitowych liczb naturalnych -------------------------------------- a = 100 b = 100 100 + 100 = 200 : Wynik poprawny |
Dodawanie 8-bitowych liczb naturalnych -------------------------------------- a = 100 b = 200 100 + 200 = 44 : Wynik błędny, NADMIAR!!! |
Innym sposobem wykrycia nadmiaru jest sprawdzenie, czy wynik dodawania jest mniejszy od większej z dodawanych liczb ( nie trzeba wtedy stosować do obliczeń większego typu ). Np. dla liczb 8-bitowych NBC (zakres 0...255 ):
100 + 156 = 0 ( 100 + 156 = 256 = 100000000(NBC), co po obcięciu od 8 bitów daje 00000000(NBC) ). |
Przykładowy
program w języku C++ // Dodawanie dwóch liczb 8-bitowych NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------ #include <iostream> using namespace std; int main() { unsigned int x,y; // 32-bitowe zmienne pomocnicze unsigned char a,b,m,r; // Właściwe zmienne 8-bitowe setlocale(LC_ALL,""); cout << "Dodawanie 8-bitowych liczb naturalnych" << endl << "--------------------------------------" << endl << endl; // Liczby wczytujemy jako 32-bitowe, gdyż inaczej dane wejściowe // zostałyby zinterpretowane jako znaki, a nie liczby. cout << "a = "; cin >> x; cout << "b = "; cin >> y; // Wczytane liczby zapamiętujemy w zmiennych 8-bitowych NBC a = x; b = y; // Zapamiętujemy większą z liczb a,b m = a; if(b > a) m = b; // Wykonujemy dodawanie r = a + b; // Wyświetlamy wyniki cout << (unsigned int)a << " + " << (unsigned int)b << " = " << (unsigned int)r; // Sprawdzamy, czy wynik jest poprawny, czy z nadmiarem if(r >= m) cout << " : Wynik poprawny"; else cout << " : Wynik błędny, NADMIAR!!!"; cout << endl << endl; return 0; } |
Przykładowe wyniki ( zakres 8-bitowych liczb NBC wynosi od 0 do 255 ):
Dodawanie 8-bitowych liczb
naturalnych -------------------------------------- a = 100 b = 100 100 + 100 = 200 : Wynik poprawny |
Dodawanie 8-bitowych liczb
naturalnych -------------------------------------- a = 100 b = 200 100 + 200 = 44 : Wynik błędny, NADMIAR!!! |
Podobnie jest z mnożeniem. Jeśli wynik mnożenia wykracza poza zakres, mamy do czynienia z nadmiarem.
Przykładowy program w języku C++
// Mnożenie dwóch liczb 16-bitowych NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------------- #include <iostream> using namespace std; int main() { unsigned long long int a,b,lr; unsigned short int sr; setlocale(LC_ALL,""); cout << "Mnożenie 16-bitowych liczb naturalnych" << endl << "--------------------------------------" << endl << endl; // Liczby wczytujemy jako 32-bitowe cout << "a = "; cin >> a; cout << "b = "; cin >> b; // Wczytane liczby obcinamy do 16 bitów a &= 0x000000000000ffffL; b &= 0x000000000000ffffL; // Wykonujemy mnożenie sr = lr = a * b; // Wyświetlamy wyniki cout << a << " x " << b << " = " << sr; if(lr == sr) cout << " : Wynik poprawny"; else cout << " : Wynik błędny, NADMIAR!!!"; cout << endl << endl; return 0; } |
Przykładowe wyniki ( zakres 16-bitowych liczb NBC wynosi od 0 do 65535 ):
Mnożenie 16-bitowych liczb naturalnych -------------------------------------- a = 100 b = 500 100 x 500 = 50000 : Wynik poprawny |
Mnożenie 16-bitowych liczb naturalnych -------------------------------------- a = 100 b = 1000 100 x 1000 = 34464 : Wynik błędny, NADMIAR!!! |
Dzielenie liczb naturalnych NBC zdefiniowane jest jako dzielenie całkowite, tzn. wynik określa ile razy dzielnik mieści się w dzielnej. Na przykład:
7 / 2 = 3 |
Ponieważ 2 mieści się 3 razy w 7 i zostaje reszta 1. Wartość reszty z dzielenia daje nam operacja %:
7 % 2 = 1 |
Wynik dzielenia jest zawsze poprawny pod warunkiem, że dzielnik jest różny od zera.
Przykładowy program w języku C++
// Dzielenie i reszta z dzielenia liczb NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned int a,b; setlocale(LC_ALL,""); cout << "Dzielenie i reszta z dzielenia liczb NBC" << endl << "----------------------------------------" << endl << endl; // Wczytujemy liczby do dzielenia cout << "a = "; cin >> a; cout << "b = "; cin >> b; // Sprawdzamy, czy dzielnik jest zerem if(!b) cout << "DZIELENIE PRZEZ ZERO !!!"; else cout << a << " / " << b << " = " << a / b << endl << a << " % " << b << " = " << a % b; cout << endl << endl; return 0; } |
Wynik |
Dzielenie i reszta z dzielenia liczb NBC ---------------------------------------- a = 7 b = 2 7 / 2 = 3 7 % 2 = 1 |
Dzielenie i reszta z dzielenia liczb NBC ---------------------------------------- a = 7 b = 0 DZIELENIE PRZEZ ZERO !!! |
Wykonując działania na liczbach NBC należy zwracać uwagę na ich prawidłową kolejność. Na przykład chcesz policzyć 2/3 z 9:
2 / 3 * 9 = 0 |
Dlaczego tak się dzieje? Operacje dzielenia i mnożenia mają ten sam priorytet, a to oznacza, iż zostaną wykonane w kolejności zapisu od strony lewej do prawej. Zatem komputer najpierw wykona dzielenie całkowite:
2 / 3 = 0 |
Następnie wynik tego dzielenia jest mnożony przez 9:
0 * 9 = 0 |
I wynikiem jest zero. Jeśli chcesz otrzymać 2/3 z 9, to należy zmienić kolejność obliczeń:
9 * 2 / 3 = 6 |
Teraz komputer najpierw wykona mnożenie:
9 * 2 = 18 |
A następnie ten wynik podzieli przez 3:
18 / 3 = 6 |
Jeśli wykonujesz mnożenie i dzielenie liczb naturalnych NBC, dzielenie umieszczaj na końcu wyrażenia. |
Przy odejmowaniu liczb NBC należy sprawdzać, czy odjemnik nie jest większy od odjemnej, ponieważ wtedy wynik będzie ujemny, czyli poniżej dolnej granicy zakresu. Taką sytuację nazywamy niedomiarem ( ang. underflow ). Niedomiar daje zawsze błędne wyniki, ponieważ kod NBC nie potrafi reprezentować liczb ujemnych.
Przykładowy program wykonuje odejmowanie i sprawdza warunek niedomiaru.
Przykładowy program w języku C++
// Odejmowanie liczb naturalnych NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned int a,b; setlocale(LC_ALL,""); cout << "Odejmowanie 32-bitowych liczb naturalnych w kodzie NBC" << endl << "------------------------------------------------------" << endl << endl; // Odczytujemy dane wejściowe cout << "a = "; cin >> a; cout << "b = "; cin >> b; // Wykonujemy odejmowanie cout << a << " - " << b << " = " << a - b; // Sprawdzamy niedomiar if(a >= b) cout << " : Wynik prawidłowy"; else cout << " : Wynik błędny, NIEDOMIAR !!!"; cout << endl << endl; return 0; } |
Wynik |
Odejmowanie 32-bitowych liczb naturalnych w
kodzie NBC ------------------------------------------------------ a = 25 b = 12 25 - 12 = 13 : Wynik prawidłowy |
Odejmowanie 32-bitowych liczb naturalnych w
kodzie NBC ------------------------------------------------------ a = 25 b = 26 25 - 26 = 4294967295 : Wynik błędny, NIEDOMIAR !!! |
Przy mnożeniu dużych liczb NBC (np. 64-bitowych ) możesz mieć kłopoty przy sprawdzaniu poprawności wyniku, ponieważ operacji tej nie da się wykonać w większym typie danych ( bez użycia specjalnej biblioteki arytmetycznej dużych liczb ). W takim przypadku poprawność otrzymanego wyniku sprawdza się za pomocą dzielenia całkowitego:
Jeśli (b > 0) i (r = a * b), to (a = r /
b) Jeśli (b = 0), to (r = 0) i wynik jest zawsze poprawny |
Poniższy program mnoży dwie 64-bitowe liczby NBC i sprawdza poprawność wyniku.
Przykładowy program w języku C++
// Mnożenie liczb naturalnych NBC // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned long long int a,b,r; setlocale(LC_ALL,""); cout << "Mnożenie 64-bitowych liczb naturalnych w kodzie NBC" << endl << "---------------------------------------------------" << endl << endl; // Odczytujemy dane wejściowe cout << "a = "; cin >> a; cout << "b = "; cin >> b; // Wykonujemy mnożenie r = a * b; // Wypisujemy wynik cout << a << " x " << b << " = " << r; // Sprawdzamy nadmiar if (b && (a != r / b)) cout << " Wynik błędny, NADMIAR !!!"; else cout << " Wynik prawidłowy"; cout << endl << endl; return 0; } |
Wynik |
Mnożenie 64-bitowych liczb naturalnych w kodzie
NBC --------------------------------------------------- a = 1999999999 b = 1999999999 1999999999 x 1999999999 = 3999999996000000001 Wynik prawidłowy |
Mnożenie 64-bitowych liczb naturalnych w kodzie
NBC --------------------------------------------------- a = 9999999999 b = 9999999999 9999999999 x 9999999999 = 7766279611452241921 Wynik błędny, NADMIAR !!! |
W celu redukcji obliczeń przyjmijmy:
Istnieje kilka metod rozwiązania tego problemu. Najprostsza polega na sprawdzaniu kwadratów kolejnych liczb naturalnych 1,2,3... aż do momentu, gdy kwadrat będzie większy od n. W takim przypadku za [√n] przyjmujemy ostatnio sprawdzaną liczbę pomniejszoną o 1.
Przykładowy program w języku C++
// Kwadratowy pierwiastek całkowity // Metoda 1 // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned int n, i, isqr; setlocale(LC_ALL,""); cout << "Obliczanie wartości kwadratowego pierwiastka całkowitego" << endl << "--------------------------------------------------------" << endl << endl; // Odczytujemy liczbę, której pierwiastek całkowity ma zostać obliczony cout << "Liczba = "; cin >> n; if(n < 2) isqr = n; // Pierwiastki z 0 i z 1 są równe odpowiednio 0 i 1 else { for(i = 2; i * i <= n; i++); isqr = i - 1; } cout << "Pierwiastek = " << isqr << endl << "Błąd = " << n - isqr * isqr << endl << endl; return 0; } |
Wynik |
Obliczanie wartości kwadratowego pierwiastka
całkowitego -------------------------------------------------------- Liczba = 1 Pierwiastek = 1 Błąd = 0 |
Obliczanie wartości kwadratowego pierwiastka
całkowitego -------------------------------------------------------- Liczba = 8976976 Pierwiastek = 2996 Błąd = 960 |
Kolejny program wykorzystuje tę samą metodę. Usprawnienie polega na wyliczaniu kolejnych kwadratów nie poprzez mnożenie, lecz poprzez dodawanie, które jest szybsze od mnożenia.
Jeśli mamy kwadrat liczby n, to kwadrat następnej liczby wynosi:
Binarnie mnożenie przez 2 wykonujemy za pomocą przesunięcia bitów o 1 pozycję w lewo:
0110(NBC)
= 6 1100(NBC) = 12 |
W języku C++ wykonujemy tę operację operatorem bitowym <<. Przesunięcie bitów wykonywane jest szybko, ponieważ dla mikroprocesora jest to bardzo prosta operacja.
Program po modyfikacji wygląda następująco:
Przykładowy program w języku C++
// Kwadratowy pierwiastek całkowity // Metoda 2 // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned int n, i, n2; setlocale(LC_ALL,""); cout << "Obliczanie wartości kwadratowego pierwiastka całkowitego" << endl << "--------------------------------------------------------" << endl << endl; // Odczytujemy liczbę, której pierwiastek całkowity ma zostać obliczony cout << "Liczba = "; cin >> n; if(n < 2) i = n; // Pierwiastki 0 i 1 są równe odpowiednio 0 i 1 else { n2 = 1; // Pierwszy kwadrat for(i = 1; (n2 += 1 + (i << 1) ) <= n; i++); } cout << "Pierwiastek = " << i << endl << "Błąd = " << n - i * i << endl << endl; return 0; } |
Wynik |
Obliczanie wartości kwadratowego pierwiastka
całkowitego -------------------------------------------------------- Liczba = 0 Pierwiastek = 0 Błąd = 0 |
Obliczanie wartości kwadratowego pierwiastka
całkowitego -------------------------------------------------------- Liczba = 9999 Pierwiastek = 99 Błąd = 198 |
W powyższych programach wyliczenie pierwiastka wymaga tyle obiegów pętli, ile wynosi wartość pierwiastka. Zatem czas wykonania będzie proporcjonalny do pierwiastka z n. W informatyce taką własność nazywamy czasową złożonością obliczeniową ( ang. time computational complexity ) i oznaczamy symbolem O(√n) ( czytaj "omikron pierwiastek z n" ). Istnieją dużo szybsze algorytmy, które obliczają wartość całkowitego pierwiastka kwadratowego. Jedną z takich metod jest metoda babilońska:
Pracujemy z trzema zmiennymi, oznaczmy je n, x i y. Zmienna n przechowuje wartość liczby, której pierwiastek obliczamy. Zmienna x jest kolejnym przybliżeniem pierwiastka. Zmienna y jest zmienną pomocniczą, która służy do sprawdzenia, czy x osiągnęło pożądaną dokładność.
n | – | liczba, której pierwiastek należy obliczyć, n N |
x | – | całkowity pierwiastek z n, x N |
y | – | do sprawdzenia dokładności x, y N |
K01: | x ← n | inicjujemy zmienne |
K02: | y ← 1 | |
K03: | Dopóki x > y, wykonuj kroki K4...K5 |
pętla obliczająca pierwiastek |
K04: | wyliczamy przybliżenie pierwiastka | |
K05: | sprawdzamy przybliżenie | |
K06: | Zakończ |
W algorytmie występują dwa dzielenia w pętli. Dzielenie przez 2 możemy zastąpić dużo szybszym przesunięciem bitów o 1 pozycję w prawo:
1100(NBC) = 12 0110(NBC) = 6 |
Operację przesunięcia bitów w języku C++ wykonujemy za pomocą operatora bitowego >>.
Przykładowy program w języku C++
// Kwadratowy pierwiastek całkowity // Metoda 3 // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned int n,x,y,i; setlocale(LC_ALL,""); cout << "Obliczanie wartości kwadratowego pierwiastka całkowitego" << endl << "--------------------------------------------------------" << endl << endl; // Odczytujemy liczbę, której pierwiastek całkowity ma zostać obliczony cout << "Liczba = "; cin >> n; i = 0; x = n; y = 1; while(x > y) // Sprawdzamy, czy x osiągnęło pożądaną dokładność { // Jeśli nie, to wyliczamy kolejne przybliżenie pierwiastka x = (x + y) >> 1; // Średnia arytmetyczna y = n / x; i++; // Licznik obiegów } cout << "Pierwiastek = " << x << endl << "Błąd = " << n - x * x << endl << "Obiegi = " << i << endl; return 0; } |
Wynik |
Obliczanie wartości kwadratowego pierwiastka
całkowitego -------------------------------------------------------- Liczba = 9 Pierwiastek = 3 Błąd = 0 Obiegi = 2 |
Obliczanie wartości kwadratowego pierwiastka
całkowitego -------------------------------------------------------- Liczba = 9999 Pierwiastek = 99 Błąd = 198 Obiegi = 10 |
W programie został dodany licznik obiegów pętli wyznaczającej kolejne przybliżenia pierwiastka. Czas obliczeń jest zbieżny do logarytmu z n, co zapisujemy jako O(log n). Złożoność logarytmiczna jest dużo korzystniejsza od złożoności pierwiastkowej.
Na przykład logarytm przy podstawie 3 z liczby 9 jest równy 2, ponieważ 32 = 9.
Logarytm całkowity jest zawsze liczbą całkowitą. Jest to największy całkowity wykładnik, dla którego potęga podstawy o tym wykładniku jest niewiększa od liczby logarytmowanej. Z definicji tej wynika, iż logarytm ten ma zawsze wykładnik największej potęgi 2, która nie jest większa od liczby logarytmowanej. Jeśli rozważymy bitowo kod NBC, to okaże się, że największą potęgą 2 o pożądanej wartości jest waga najstarszego bitu równego 1 w kodzie NBC tej liczby:
5 = 101NBC
= 22 + 20, stąd [log25]
= 2 7 = 111NBC = 22 + 21 + 20, stąd [log27] = 2 9 = 1001NBC = 23 = 20, stąd [log29] = 3 15 = 1111NBC = 23 + 22 + 21 + 20, stąd [log215] = 3 17 = 10001NBC = 24 + 20, stąd [log217] = 4 131 = 10000011NBC = 27 + 21 + 20, stąd [log2131] = 7 |
Wartość tej potęgi jest równa 2p, gdzie p jest numerem pozycji najstarszego bitu. Wynika stąd prosty algorytm wyznaczania logarytmu całkowitego o podstawie 2 dla liczby naturalnej x ( zero nie jest liczbą naturalną ):
Zadanie to można wykonać na kilka sposobów. Jeden z nich przedstawia przykładowy program:
Przykładowy program w języku C++
// Logarytm całkowity o podstawie 2 // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //----------------------------------------- #include <iostream> using namespace std; int main() { unsigned long long int x,m; unsigned int p; setlocale(LC_ALL,""); cout << "Obliczanie wartości logarytmu całkowitego o podstawie 2" << endl << "-------------------------------------------------------" << endl << endl; // Odczytujemy liczbę, której logarytm ma zostać obliczony cout << "Liczba = "; cin >> x; if(!x) cout << "Nie istnieje logarytm z liczby 0"; else { p = 63; // Numer pozycji najstarszego bitu m = 0x8000000000000000L; // Maska bitowa while(!(x & m)) { m >>= 1; p--; } cout << "Logarytm = " << p << endl << "Błąd = " << x - m; } cout << endl << endl; return 0; } |
Wynik |
Obliczanie wartości logarytmu całkowitego o
podstawie 2 ------------------------------------------------------- Liczba = 0 Nie istnieje logarytm z liczby 0 |
Obliczanie wartości logarytmu całkowitego o
podstawie 2 ------------------------------------------------------- Liczba = 131 Logarytm = 7 Błąd = 3 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.