1 Podstawy informatyki 2013/2014Łukasz Sztangret Katedra Informatyki Stosowanej i Modelowania Prezentacja przygotowana w oparciu o materiały Danuty Szeligi i Pawła Jerzego Matuszyka

2 Jednostki informacji Bit (ang. bit) (Shannon, 1948)Najmniejsza ilość informacji potrzebna do określenia, który z dwóch równie prawdopodobnych stanów przyjął układ Bajt (ang. byte) (Shannon, 1948) Najmniejsza adresowalna jednostka informacji pamięci komputerowej, składająca się z bitów Zazwyczaj przyjmuje się, że 1B = 8b (oktet) Najbardziej znaczący bit (bajt) = bit (bajt) o największej wadze (w zapisie z lewej strony) Najmniej znaczący bit (bajt) = bit (bajt) o najmniejszej wadze (w zapisie z prawej strony)

3 Jednostki informacji 1kb = 1 024b 1Mb = 1 024kb = b 1Gb = 1 024Mb = kb = b

4 Sposoby zapisu danych w pamięciJak zapisać wielobajtowe dane pod danym adresem? W jakiej kolejności przesyłać kolejne bajty? Big-endian Najbardziej znaczący bajt jest umieszczany jako pierwszy Little-endian Najmniej znaczący bajt jest umieszczany jako pierwszy

5 Reprezentacja liczb w komputerzeReprezentacja liczb całkowitych Reprezentacja liczb nieujemnych Kod znak-moduł Kod U1 Kod U2 Kod z nadmiarem Liczby stałoprzecinkowe Liczby zmiennoprzecinkowe

6 Systemy reprezentacji liczbSystemy addytywne Posiadają osobne symbole dla pierwszych kilku małych liczb oraz kolejne symbole dla ich wielokrotności. W systemach tych liczby tworzy się przez sumowanie wartości kolejnych symboli. jedynkowy (ludy pierwotne, np. Pigmeje) egipski (dziesiątkowy) rzymski (Etruskowie, Rzym) Systemy pozycyjne W pozycyjnych systemach liczbowych ten sam symbol (cyfra) ma różną w zależności od pozycji, którą zajmuje w zapisie danej liczby. dwójkowy ósemkowy dziesiętny szesnastkowy Źródło:

7 Systemy reprezentacji liczbSystemy addytywne Posiadają osobne symbole dla pierwszych kilku małych liczb oraz kolejne symbole dla ich wielokrotności. W systemach tych liczby tworzy się przez sumowanie wartości kolejnych symboli. jedynkowy (ludy pierwotne, np. Pigmeje) egipski (dziesiątkowy) rzymski (Etruskowie, Rzym) Systemy pozycyjne W pozycyjnych systemach liczbowych ten sam symbol (cyfra) ma różną w zależności od pozycji, którą zajmuje w zapisie danej liczby. dwójkowy ósemkowy dziesiętny szesnastkowy

8 System egipski (system addytywny)4622 Źródło:

9 System rzymski (system addytywny)II 2 IV 4 XIX 19 XCVI 96 CDLXXI 461 MCMXCII 1992

10 System Majów (system pozycyjny)

11 Liczbowe systemy pozycyjneCechy dowolnego systemu pozycyjnego o podstawie p System pozycyjny charakteryzuje liczba zwaną podstawą systemu pozycyjnego Do zapisu liczby służą cyfry bądź litery (w przypadku podstawy > 10) Cyfr jest zawsze tyle, ile wynosi podstawa systemu: 0,1,2,...,(p-1) Cyfry ustawiamy na kolejnych pozycjach Pozycje numerujemy od 0 poczynając od strony prawej zapisu Każda pozycja posiada swoją wagę Waga jest równa podstawie systemu podniesionej do potęgi o wartości numeru pozycji Cyfry bądź litery określają ile razy waga danej pozycji uczestniczy w wartości liczby Wartość liczby obliczamy sumując iloczyny cyfr przez wagi ich pozycji

12 Liczbowe systemy pozycyjneSystem dwójkowy p=2, cyfry: 0,1 1010(2)=1*23+0*22+1*21+0*20=10(10) System ósemkowy p=8, cyfry: (8)=1*83+2*82+3*81+4*80=668(10) System dziesiętny p=10, cyfry: (10)=1*103+2*102+3*101+4*100=1234(10) System szesnastkowy p=16, cyfry: 0-9, A-F 12AF(16)=1*163+2*162+10*161+15*160=4783(10)

13 Liczbowe systemy pozycyjne – schemat HorneraWartość liczby reprezentowanej przez ciąg znaków (zapisanej w systemie pozycyjnym) Cn-1 Cn-2…C1C0 obliczamy ze wzoru Inne rozwiązanie - zastosowanie schematu Hornera Rozpatrzmy wielomian współczynniki ai wielomianu odpowiadają cyfrom Ci, kolejne potęgi x to potęgi podstawy p Budowa schematu Cn-1Cn-2...C2C1C0 = Cn-1 pn-1 + Cn-2 pn C2 p2 + C1 p1 + C0 p0 W(x) = an-1 xn-1 + an-2 xn a2 x2 + a1 x + a0

14 Schemat Hornera Dla pięciocyfrowej liczby w systemie pozycyjnym ZaletyOszczędność przy mnożeniu Sposób przetwarzania cyfr Brane są kolejno jedna cyfra po drugiej z ciągu wejściowego aż do napotkania końca zapisu (taka kolejność cyfr jest zwykle zgodna z kolejnością ich przechowywania w łańcuchu tekstowym) long int sh(char *s, unsigned int p) { int result=0; int i; i=0; while(s[i]){ result = result*p + (s[i]-'0'); i++; } return result; Dla pięciocyfrowej liczby w systemie pozycyjnym Wzór 10 mnożeń, 4 dodawania Schemat Hornera 4 mnożenia, 4 dodawania

15 Przeliczanie liczb pomiędzy systemami(2)->(16) AC56 (2)->(8) 5673

16 Przeliczanie liczb pomiędzy systemami(10)->(2) 246(10)= (2) (10)->(16) 246(10)=F6(16) (10)->(8) 246(10)=366(8) 246/16=15 Reszta 6 15/16=0 Reszta F 246/2=123 Reszta 0 123/2=61 Reszta 1 61/2=30 30/2=15 15/2=7 7/2=3 3/2=1 1/2=0 246/8=30 Reszta 6 30/8=3 3/8=0 Reszta 3

17 System 10 System 16 System 8 System 2 11 111111 12 C 14 1100 +29 +1DPrzykłady dodawania System 10 System 16 System 8 System 2 11 111111 12 C 14 1100 +29 +1D +35 +11101 41 29 51 101001

18 Przykłady dodawania System 2 System 10 10000 1000 1001 1 10 20 101 5 100 4 110 6 010 2 +011 +3 10100 10100(2)=1*24+1*22=16+4=20(10)

19 Nadmiar (integer overflow)Założenie: reprezentacja 4-bitowa bez znaku. Bit nadmiaru jest ustawiony na 1. Nadmiar występuje wtedy, gdy wynik działania nie mieści się w dopuszczalnym zakresie liczb, które mogą być zapisane w danej reprezentacji. 11111 1001 9 1011 11 10100 4

20 int main() { unsigned short int a; cout< 2 65535

21 Liczba całkowita ze znakiem (kodowana na 8 bitach)Kodowanie znak-moduł Liczba całkowita ze znakiem (kodowana na 8 bitach) Znak (najbardziej znaczący bit): 1 oznacza liczbę ujemną 0 oznacza liczbę dodatnią Moduł liczby (7 bitów) 1 + 55

22 Liczba ujemna jest kodowana jako znak 1 Kodowanie znak-moduł Liczba ujemna jest kodowana jako znak 1 i kod binarny modułu tej liczby Sposób wygodny dla człowieka Przy operacjach arytmetycznych trzeba porównywać znaki Reprezentacja liczby 0: oraz Zakres liczb: [-2n-1+1, 2n-1-1] 1 - 55

23 Kod uzupełnień do 1 (U1) Liczba ujemna x jest kodowana na jeden zdwóch (równoważnych) sposobów (dla liczby -55): Kod binarny modułu negacja bitowa Kod binarny liczby =256-56=200 Sposób mało wygodny dla człowieka Łatwe operacje arytmetyczne Reprezentacja liczby 0: oraz Zakres liczb: [-2n-1+1, 2n-1-1]

24 Zasady dodawania (U1) Liczby zapisane w kodzie U1 dodajemy zgodnie z zasadami dodawania dwójkowego, ale jeżeli wystąpi przeniesienie poza bit znaku, to do wyniku dodajemy 1. -77 43 -34 11111 77 43 120 77 -43 34 -77 -43 -120

25 Kod uzupełnień do 2 (U2) Liczba ujemna x jest kodowana na jeden zdwóch (równoważnych) sposobów (dla liczby -55): Kod binarny modułu negacja bitowa i dodajemy 1 = Kod binarny liczby 28-55=256-55=201 Sposób mało wygodny dla człowieka Łatwe operacje arytmetyczne Reprezentacja liczby 0: Zakres liczb: [-2n-1, 2n-1-1]

26 Zasady dodawania (U2) Liczby zapisane w kodzie U2 dodajemy zgodnie z zasadami dodawania dwójkowego. -77 43 -34 77 -43 34 -77 -43 -120

27 Kod z nadmiarem (bias) Wartość liczby to wartość binarna pomniejszona o pewną stałą zwaną nadmiarem (bias) W zależności od nadmiaru możemy otrzymywać różne zakresy kodowanych liczb. Zakres liczb: [-bias, 2n-1-bias]

28 int main() { int a; cout<<"Podaj liczbe\n\n"; cin>>a; for (int i=31; i>=0; i--) cout<<((a>>i)&1); cout< 5 -5

29 Liczby stałoprzecinkoweZapis liczby stałoprzecinkowej w systemie pozycyjnym: Część całkowita – n cyfr Część ułamkowa – m cyfr

30 (10)=?(2) Część całkowitą sukcesywnie dzielimy przez 2 i bierzemy reszty (10)= (2) Część ułamkową sukcesywnie mnożymy przez 2 i bierzemy część całkowitą 55/2=27 1 27/2=13 13/2=6 6/2=3 3/2=1 1/2=0 0.8125*2=1.625 1 0.625*2=1.25 0.25*2=0.5 0.5*2=1

31 0.1(10)=?(2) Nie każdy ułamek skończony w systemie 10 jest skończony w systemie 2! 0.1(10)=0.0(0011)(2) 0.1*2=0.2 0.2*2=0.4 0.4*2=0.8 0.8*2=1.6 1 0.6*2=1.2 …

32 #include using namespace std; int main() { float x=0#include using namespace std; int main() { float x=0.1; if(10*x==1) cout << "Tak\n"; else cout << "Nie\n"; return 0; } #include using namespace std; int main() { double x=0.1; if(10*x==1) cout << "Tak\n"; else cout << "Nie\n"; return 0; }

33 Zakres binarnych liczb stałoprzecinkowych. Błędy zaokrągleńn – liczba bitów części całkowitej m – liczba bitów części ułamkowej Największa liczba: Błędy zaokrągleń Niech Ld – wartość dokładna liczby (w systemie dziesiętnym) Lb – wartość w zapisie binarnym Błąd bezwzględny Błąd względny

34 Błędy zaokrągleń Reprezentacja liczby 0.1 za pomocą pięciu bitów ułamkowych:

35 Liczby zmiennoprzecinkowes – znak liczby m – mantysa p – podstawa systemu c – cecha

36 Liczby zmiennoprzecinkowePołożenie przecinka w liczbach zmiennoprzecinkowych nie jest ustalone. Znormalizowana liczba zmiennoprzecinkowa to taka liczba, której mantysa spełnia zależność: W systemie dwójkowym mantysa jest zawsze równa 1!

37 Precyzja liczb zmiennoprzecinkowychZałożenia: mantysa 3 bity, bez znaku, liczba stałoprzecinkowa, przecinek po pierwszym bicie cecha 3 bity bez znaku x.xx·2xxx 0.00 0.01 0.10 0.11 1.00 1.01 1.10 1.11 000 0.25 0.5 0.75 1 1.25 1.5 1.75 001 2 2.5 3 3.5 010 4 5 6 7 011 8 10 12 14 100 16 20 24 28 101 32 40 48 56 110 64 80 96 112 111 128 160 192 224

38 Precyzja liczb zmiennoprzecinkowychPróba zakodowania liczby 9 Mamy do dyspozycji format: x.xx·2xxx A zatem mantysa zostanie obcięta do 1.00 i w ten sposób dostaniemy liczbę

39 Standard IEEE 754 W celu ujednolicenia reprezentacji binarnej oraz operacji numerycznych na różnych platformach sprzętowych, wprowadzono standard zapisu zmiennoprzecinkowego IEEE 754 (William Kahan). Standard ten definiuje: formaty reprezentacji liczb zmiennoprzecinkowych: single-precision (32 bity) double-precision (64bity) single-extended precision (> 43 bitów) double-extended precision (> 79 bitów, zazwyczaj 80 bitów) wartości specjalne (np. nieskończoność, NaN) zmiennoprzecinkowe operacje modele zaokrąglania wyjątki

40 Ogólny format w standardzie IEEE 754Sign (bit znaku): 0 – liczba dodatnia, 1 – liczba ujemna Exponent (cecha): kod z nadmiarem (bias=2e-1-1) Fraction (mantysa): liczba stałoprzecinkowa pozbawiona najbardziej znaczącego bitu reprezentującego część całkowitą (prawdziwa mantysa to 1.Fraction) Wartości specjalne Typ cecha mantysa zero Liczby nieznormalizowane ≠0 Liczby znormalizowane 1 – 2e-1 Dowolna Nieskończoności 2e-1 NaN

41 Liczba pojedynczej precyzji - floatZnak – 1 bit Cecha – 8 bitów, bias=127 Mantysa – 23 bity W sumie 32 bity 1 1 jest zawsze

42 Liczba podwójnej precyzji - doubleZnak – 1 bit Cecha – 11 bitów, bias=1023 Mantysa – 52 bity W sumie 64 bity 1 1 jest zawsze

43 Analiza bitów liczby o pojedynczej precyzjistring b2s(bity &B){ string S; if(B.S) S="1 "; else S="0 "; for (int i=7; i>=0; i--) S+=(B.E>>i&1)+'0'; S+=' '; for (int i=22; i>=0; i--) S+=(B.M>>i&1)+'0'; return S;} int main(){ union{ float f; bity b; }; cout<<"Podaj liczbe rzeczywista\n"; cin>>f; cout< #include #include #include using namespace std; struct bity { int M:23,E:8,S:1; }; ostream &operator<<(ostream &strum, bity &B) if(B.S) strum<<'-'; else strum<<'+'; double m=1,e=0; for (int i=22; i>=0; i--) m+=(B.M>>i&1)*pow(2.0,i-23); for (int i=7; i>=0; i--) e+=(B.E>>i&1)*pow(2.0,i); strum< strum< return strum; }

44 Prezentacja udostępniona na licencji Creative Commons: Uznanie autorstwa, Na tych samych warunkach 3.0. Pewne prawa zastrzeżone na rzecz autorów. Zezwala się na dowolne wykorzystywanie treści pod warunkiem wskazania autorów jako właścicieli praw do prezentacji oraz zachowania niniejszej informacji licencyjnej tak długo, jak tylko na utwory zależne będzie udzielana taka sama licencja. Tekst licencji dostępny jest na stronie: