Eg´esz sza´mok a´bra´zola´sa (jegyzet) B´erci Norbert 2015. szeptember 10-i ´ora anyaga
Tartalomjegyz´ ek 1. Sz´ amrendszerek 1.1. A sz´amrendszer alapja ´es a sz´amjegyek 1.2. Alaki- ´es helyi´ert´ek . . . . . . . . . . . 1.3. Eg´esz sz´ amok le´ır´ asa . . . . . . . . . . 1.4. Nem eg´esz sz´ amok le´ır´ asa . . . . . . . ´ alt´ 1.5. Atv´ as sz´ amrendszerek k¨ oz¨ott . . . . 1.6. Feladatok . . . . . . . . . . . . . . . . 1.7. Sz´ amrendszerek pontoss´aga . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
2. M´ ert´ ekegys´ egek
1 1 2 2 2 3 3 4 4
3. Eg´ esz sz´ amok g´ epi ´ abr´ azol´ asa 3.1. Nem negat´ıv eg´esz sz´ amok ´ abr´azol´asa . . . . . . . 3.2. Negat´ıv eg´esz sz´ amok ´ abr´ azol´asa . . . . . . . . . . 3.3. Eg´esz sz´ amok adat´ abr´ azol´ asainak ¨osszehasonl´ıt´asa 3.4. Eg´esz sz´ amok ´ abr´ azol´ asi hat´ arai ´es pontoss´aga . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4 5 5 7 7
1. Sz´ amrendszerek A sz´ amrendszer [numeral system - nem numeric system!] a sz´ am (mint matematikai fogalom) ´ırott form´ aban t¨ ort´en˝ o megjelen´ıt´es´ere alkalmas m´odszer. Ebben a r´eszben a helyi´ert´eken (poz´ıci´on) alapul´ o sz´ amrendszereket t´argyaljuk. L´eteznek nem poz´ıci´ on alapul´o sz´amrendszerek is, ilyenek p´eld´ aul a sorrendis´egen alapul´ o r´ omai sz´amok, de ezekkel a tov´ abbiakban nem foglalkozunk.
1.1. A sz´ amrendszer alapja ´ es a sz´ amjegyek A helyi´ert´eken alapul´ o sz´amrendszerek k´et legfontosabb param´etere a sz´ amrendszer alapja [base, radix] ´es az egyes poz´ıci´ okba ´ırhat´ o sz´ amjegyek [digit]. Ezek nem f¨ uggetlenek: a sz´ amrendszer alapja meghat´ arozza az egyes poz´ıci´ okba ´ırhat´o sz´ amjegyek maximum´at: ha a sz´amrendszer A alap´ u, akkor a legkisebb felhaszn´ alhat´ o sz´ amjegy a 0, a legnagyobb az A − 1. 1.1.1. p´ elda. A t´ızes sz´ amrendszerben a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 sz´ amjegyek szerepelhetnek, a nyolcas sz´ amrendszerben a 0, 1, 2, 3, 4, 5, 6, 7 sz´amjegyek k¨oz¨ ul v´alaszthatunk, m´ıg a kettesben a 0, 1 a k´et lehets´eges sz´ amjegy. T´ızn´el nagyobb alap´ u sz´ amrendszerek eset´eben a sz´ amjegyek halmaz´at 9 ut´an az ABC bet˝ uivel eg´esz´ıtj¨ uk ki. A kis ´es nagybet˝ uk k¨ oz¨ott ´altal´aban nem tesz¨ unk k¨ ul¨onbs´eget, b´ar egyes nagy alap´ u sz´ amrendszerekn´el erre m´egis sz¨ uks´eg lehet. 0 Revision
: 64 (Date : 2014 − 09 − 2013 : 31 : 30 + 0200(Sat, 20Sep2014))
1
1.1.2. p´ elda. A tizenhatos sz´ amrendszerben haszn´ alhat´o sz´amjegyek”: 0, 1, 2, 3, 4, 5, 6, 7, 8, ” 9, a, b, c, d, e, f (vagy 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). Ha az a sz¨ ovegk¨ ornyezetb˝ ol nem egy´ertelm˝ u, a sz´amrendszer alapj´at sz¨ogletes z´ ar´ojelben a jobb als´o indexbe t´eve jel¨ olhetj¨ uk. P´eld´ aul: 5221[10] , 726[8] vagy 80[16] . A j´ ol ismert t´ızes alap´ u decim´ alis sz´amrendszeren k´ıv¨ ul az informatik´aban a leggyakrabban haszn´ altak a k¨ ovetkez˝ ok: a kettes alap´ u bin´ aris, a nyolcas alap´ u okt´ alis ´es a tizenhatos alap´ u hexadecim´ alis. Az el˝ oz˝ oekben eml´ıtett, indexben t¨ort´en˝o sz´amrendszer megad´as mellett bin´ aris sz´ amrendszer jel¨ ol´es´ere haszn´ alatos a b postfix, okt´alis esetben egy kezd˝o 0 szerepeltet´ese, hexadecim´alis sz´ amok eset´en a 0x, 0X prefixek vagy a h postfix. Az informatik´aban ezeket a jel¨ ol´eseket haszn´ aljuk a legink´ abb. P´eld´aul: 100b (bin´aris), 065 (okt´alis), 0x243 (hexadecim´alis), 0X331 (hexadecim´alis), 22h (hexadecim´alis). Ha sem a sz´am el˝ott, sem ut´ana, sem az index´eben nincs jel¨ olve, akkor decim´ alis sz´ amrendszerben ´ertelmezz¨ uk a le´ırtakat.
1.2. Alaki- ´ es helyi´ ert´ ek Egy adott sz´ amrendszerben le´ırt sz´ am eset´eben egy sz´ amjegy ´ert´eke egyenl˝o a sz´amjegy alaki ´ert´ek´enek ´es helyi´ert´ek´enek szorzat´ aval. A sz´ amjegy alaki ´ert´eke a sz´amjegyhez tartoz´o ´ert´ek, a helyi´ert´ek pedig a sz´ amrendszer alapj´ anak a poz´ıci´o szerinti hatv´ anya. A 0, 1, . . . , 9 eset´eben az alaki ´ert´ek egy´ertelm˝ u, a bet˝ ukkel kieg´esz´ıtett esetben ezek: a=10, b=11, c=12, d=13 stb. 1.2.1. p´ elda. A t´ızes sz´ amrendszerben fel´ırt 32 sz´am eset´eben a 3 helyi´ert´eke 101 = 10, mivel az jobbr´ ol a m´asodik poz´ıci´ on szerepel (´es a helyi´ert´ekeket a nulladik hatv´anyt´ol ind´ıtjuk), ´ıgy ebben a p´eld´ aban a 3 sz´ amjegy ´ert´eke: 3 · 101 = 3 · 10 = 30. 1.2.2. p´ elda. A t´ızes sz´ amrendszerben fel´ırt 32 sz´ am eset´eben a 2 helyi´ert´eke 100 = 1, mivel az jobbr´ ol az els˝o poz´ıci´ on szerepel (´es a helyi´ert´ekeket a nulladik hatv´anyt´ol ind´ıtjuk), ´ıgy ebben a p´eld´ aban a 2 sz´amjegy ´ert´eke: 2 · 100 = 2 · 1 = 2.
1.3. Eg´ esz sz´ amok le´ır´ asa Eg´esz sz´ amokat ´ altal´ anos esetben az an an−1 . . . a1 a0 alakban ´ırhatunk fel, ´es az ´ıgy fel´ırt sz´ am ´ert´eke (A alap´ u sz´ amrendszert felt´etelezve): (an · An ) + (an−1 · An−1 ) + · · · + (a1 · A1 ) + (a0 · A0 ) ami nem m´as, mint a le´ırt sz´ amjegyek (az el˝ oz˝oekben megismert m´ odon kisz´amolt) ´ert´ekeinek osszege. ¨ 1.3.1. p´ elda. Trivi´ alis p´elda: 405[10] = 4 · 102 + 0 · 101 + 5 · 100 = 400 + 5 1.3.2. p´ elda. 405[8] = 4 · 82 + 0 · 81 + 5 · 80 = 256 + 5 = 261 1.3.3. p´ elda. 1001101[2] = 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 64 + 8 + 4 + 1 = 77 1.3.4. p´ elda. 0xA3 = 10 · 161 + 3 · 160 = 10 · 16 + 3 · 1 = 163 A negat´ıv eg´esz sz´ amokat u ´gy ´ırjuk le, hogy abszol´ ut ´ert´ek¨ uket az el˝ oz˝o m´odon fel´ırjuk valamely sz´ amrendszerben, majd el´e − jelet tesz¨ unk (b´ar ezt a jel¨ol´est a t´ızes sz´amrendszeren k´ıv¨ ul a gyakorlatban nem alkalmazzuk).
1.4. Nem eg´ esz sz´ amok le´ır´ asa Az eg´esz sz´ amokn´ al megismert fel´ır´ asi m´odszert kiterjeszthetj¨ uk u ´gy, hogy a helyi´ert´ekek megad´ as´ an´ al nem ´ allunk meg a nulladik hatv´ anyn´ al, hanem folytatjuk azt a negat´ıv hatv´ anyokra ´ is, ´ıgy lehet˝ os´eg¨ unk ad´ odik nem eg´esz sz´amok le´ır´as´ara. Altal´ anos esetben teh´at ennek alakja: an an−1 . . . a1 a0 a−1 . . . a−k , ´es az ´ıgy fel´ırt sz´am ´ert´eke (A alap´ u sz´amrendszert felt´etelezve): an · An + an−1 · An−1 + · · · + a1 · A1 + a0 · A0 + a−1 · A−1 + · · · + a−k · A−k
2
Annak ´erdek´eben, hogy a mindk´et v´eg´en (eg´esz- illetve t¨ort r´esz) tetsz˝olegesen b˝ov´ıthet˝o fel´ır´as egy´ertelm˝ u legyen, ennek a k´et r´esznek a hat´ar´ at jel¨olj¨ uk tizedesvessz˝ovel. Mi a magyar helyes´ır´ assal ellent´etben, a nem eg´esz sz´ amok felsorol´ as´anak k¨onnyebb olvashat´os´aga ´erdek´eben a ol´est fogjuk alkalmazni. (Pl. 1,6, 2,4, 5,9 helyett 1.6, 2.4, 5.9) tov´ abbiakban a tizedespontos1 jel¨ 1.4.1. p´ elda. Trivi´ alis p´elda: 405.23[10] = 4 · 102 + 0 · 101 + 5 · 100 + 2 · 10−1 + 3 · 10−2 = 1 1 4 · 100 + 5 · 1 + 2 · 10 + 3 · 100 1.4.2. p´ elda. 405.23[8] = 4 · 82 + 0 · 81 + 5 · 80 + 2 · 8−1 + 3 · 8−2 = 4 · 64 + 5 · 1 + 2 · 3 256 + 5 + 28 + 64 = 261 19 64 = 261.296875
1 8
+3·
1 82
=
1.4.3. p´ elda. 1001101.01[2] = 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 + 0 · 2−1 + 1 · 2−2 = 64 + 8 + 4 + 1 + 14 = 77.25 Negat´ıv nem eg´esz sz´ amok le´ır´ asa a negat´ıv eg´esz sz´ amok le´ır´ as´ahoz hasonl´oan a − jel sz´am el´e ´ır´ as´ aval t¨ ort´enik (amit szint´en csak a t´ızes sz´amrendszer eset´eben haszn´ alunk).
´ alt´ 1.5. Atv´ as sz´ amrendszerek k¨ oz¨ ott Az adott sz´amrendszerb˝ ol t´ızes sz´ amrendszerbe v´ alt´ast az 1.3 ´es az 1.4 r´eszek p´eld´aiban hallgat´olagosan m´ar bemutattuk. A ford´ıtott a´tv´alt´asra nem t´er¨ unk ki (a m´odszer k¨onnyen kital´alhat´o, l´ asd 1.6.5. feladat). Az ´ atv´ alt´ as nagym´ert´ekben egyszer˝ us¨odik, ha bin´ arisb´ol okt´alis vagy hexadecim´alis sz´ amrendszerbe kell ´ atv´ altani: egyszer˝ uen h´armas´aval (okt´alis esetben) vagy n´egyes´evel (hexadecim´alis esetben) kell a bin´ aris sz´ amjegyeket csoportos´ıtani, ´es az ´ıgy k´epzett csoportokat ´atv´altani: 1.5.1. p´ elda. 1010111001[2] = 001 010 111 001[2] = 1271[8] Az ´ atv´ alt´as ford´ıtott ir´ anyban is hasonl´oan egyszer˝ u: az egyes okt´alis vagy hexadecim´alis sz´amjegyeket kell ´ atv´ altani ´es az ´ıgy kapott h´ armas illetve n´egyes bin´ aris csoportokat egym´as ut´an ´ırni: 1.5.2. p´ elda. 2b9[16] = 0010 1011 1001[2] = 1010111001[2] Okt´ alisb´ ol hexadecim´alisba vagy decim´alisb´ ol hexadecim´alisba illetve ford´ıtva a bin´ aris sz´amrendszert k¨ ozbeiktatva is ´ atv´ althatunk ezzel a m´odszerrel: 1.5.3. p´ elda. 2b9[16] = 0010 1011 1001[2] = 1010111001[2] = 001 010 111 001[2] = 1271[8]
1.6. Feladatok 1.6.1. feladat. 1010111001[2] = ?[8] = ?[16] 1.6.2. feladat. 54[8] = ?[16] 1.6.3. feladat. 962[10] = ?[8] = ?[16] 1.6.4. feladat. 9a2d[16] = ?[2] = ?[8] = ?[16] 1.6.5. feladat. Adjunk algoritmust (m´odszert) decim´alisb´ol a) okt´alis-, b) hexadecim´alis sz´ amrendszerbe t¨ ort´en˝ o k¨ ozvetlen (teh´ at nem a bin´ aris sz´amrendszer k¨ozbeiktat´as´aval t¨ort´en˝o) ´atv´alt´ asra! 1.6.6. feladat. Minden racion´ alis sz´ am (t¨ort) le´ırhat´o b´armilyen alap´ u sz´amrendszerben v´eges sz´ amjegy felhaszn´ al´ as´ aval? A http://www.exploringbinary.com/binary-converter/ oldalon kipr´ob´alhat´ok, ellen˝orizhet˝ok az atv´ ´ alt´asok. 1 Ha nagyon pontosak akarunk lenni, akkor tizedespontr´ ol csak a t´ızes sz´ amrendszer haszn´ alata eset´ en besz´ elhetn´ enk, bin´ aris esetben ink´ abb bin´ aris pontr´ ol van sz´ o (´ es hasonl´ oan okt´ alis, hexadecim´ alis stb. esetben).
3
1.7. Sz´ amrendszerek pontoss´ aga Fontos kiemelni, hogy nem eg´esz sz´ amok fel´ır´asa eset´en nem biztos, hogy a sz´am pontosan le´ırhat´ o v´eges sz´ amjeggyel! S˝ ot, egy konkr´et nem eg´esz sz´am ´abr´azol´as´anak pontoss´aga f¨ ugg a sz´ amrendszer alapj´ at´ ol: p´eld´ aul az 31 t´ızes sz´amrendszerben nem ´ırhat´o fel v´eges sz´amjeggyel, ugyanakkor h´ armas sz´ amrendszerben pontosan fel´ırhat´o: 13 = 0.1[3] = 0.33333 . . .[10] 1.7.1. feladat. Adjunk meg n´eh´ any p´eld´ at arra, amikor az egyik sz´amrendszerben v´eges sz´ amjeggyel fel´ırhat´ o sz´ am a m´asik sz´ amrendszerben nem ´ırhat´o fel v´eges sz´ amjeggyel! 1.7.2. feladat. a) Adjunk meg n´eh´ any p´eld´at olyan sz´amra, ami egyetlen sz´amrendszerben sem ´ırhat´ o fel v´eges sz´ amjeggyel! b) Fel´ırhat´ok ezek a sz´amok t¨ort alakban? c) Milyen sz´ amhalmazt alkotnak ezek a sz´ amok? 1.7.3. feladat. Kiv´ alaszthat´o olyan alap´ u sz´amrendszer, amiben minden racion´alis sz´ am pontosan ´ abr´ azolhat´ o v´eges hossz´ u karaktersorozattal? Indokoljuk meg!
2. M´ ert´ ekegys´ egek Az informatik´ aban haszn´ alatos legkisebb egys´eg a bit [bit] (sok esetben b-vel r¨ovid´ıtik, de a legfrissebb szabv´ any2 a r¨ ovid´ıt´es n´elk¨ uli form´at aj´ anlja, ami k´ezenfekv˝o a sz´amrendszerek r´eszben ´ eke 0 vagy 1 lehet. t´ argyaltak miatt, hiszen a b postfix a bin´aris sz´amrendszert jel¨oli). Ert´ Haszn´ alhatjuk t´ arol´ okapacit´ as vagy inform´aci´omennyis´eg jel¨ol´es´ere. Az ut´obbi egy fels˝obb ´eves t´ argy, az Inform´ aci´ o ´es k´ odelm´elet t´em´aja, mi itt csak a t´arol´asi vonatkoz´as´aval foglalkozunk. A b´ ajt [byte] az informatika m´asik legfontosabb egys´ege, jele: B. Mi az ´altal´anosan elfogadott, a gyakorlatban majdnem kiz´ ar´ olagosan haszn´alt 1 B = 8 bit ´atv´ alt´ast haszn´aljuk, b´ar egyes (egzotikus) architekt´ ur´ ak eset´eben enn´el t¨obb vagy kevesebb bit is alkothat egy b´ajtot. Az SI m´ert´ekegys´egrendszerben haszn´alatos k (kilo), M (mega), G (giga), T (tera), P (peta) stb. prefixek mellett a bit ´es a b´ ajt eset´eben haszn´alatosak a Ki (kibi), Mi (mebi), Gi (gibi), Ti (tebi), Pi (pebi) stb. bin´ aris prefixek is (l´asd az 1. ´abr´an). Fontos kiemelni, hogy az egyre nagyobb prefixek eset´eben egyre nagyobb a k¨ ul¨onbs´eg az SI ´es a bin´ aris prefixek k¨ oz¨ ott. P´eld´ aul a G (10003 ) ´es Gi (10243 ) k¨oz¨ott a k¨ ul¨onbs´eg kb. 7%, a T (10004 ) ´es Ti (10244 ) k¨ oz¨ ott m´ar kb. 10%.3 A kapcsolat a prefixek ´es a sz´ amrendszerek k¨oz¨ott ott fedezhet˝o fel, hogy a haszn´ alt prefixek mindig a sz´ amrendszer alapja valamely hatv´any´anak hatv´anyai. Az SI esetben ez a t´ız harmadik hatv´ anya (illetve ennek tov´ abbi hatv´ anyai), de ugyanez igaz a bin´aris prefixekre is, amikor is ez a kett˝ o tizedik hatv´ anya (illetve ennek tov´abbi hatv´anyai). SI prefix k (kilo) M (mega) G (giga) T (tera) P (peta)
bin´aris prefix szorz´o Ki (kibi) 1024 Mi (mebi) 10242 Gi (gibi) 10243 Ti (tebi) 10244 Pi (pebi) 10245
szorz´o 1000 10002 10003 10004 10005
1. ´ abra. SI ´es bin´ aris prefixek
3. Eg´ esz sz´ amok g´ epi ´ abr´ azol´ asa A g´epi sz´ am´abr´ azol´ as a sz´ amok (sz´ am´ıt´o)g´epek mem´ori´aj´ aban vagy egy´eb egys´eg´eben t¨ort´en˝o t´ arol´ as´ at vagy valamely adath´ al´ ozaton t¨ort´en˝o tov´ abb´ıt´as form´atum´at adja meg. 2 ISO/IEC
80000, Part 13 - Information science and technology fontos ez a h´ att´ ert´ arak eset´ eben, ahol a gy´ art´ ok ink´ abb az SI prefixeket haszn´ alj´ ak, mert ´ıgy egy 1000000000000 B m´ eret˝ u lemezegys´ eg eset´ eben 1 TB-ot t¨ untethetnek fel, m´ıg ugyanez a bin´ aris prefixekkel csup´ an 0.9 TiB 3 K¨ ul¨ on¨ osen
4
3.1. Nem negat´ıv eg´ esz sz´ amok ´ abr´ azol´ asa Egy nem negat´ıv (el˝ ojel n´elk¨ uli) eg´esz sz´am [unsigned integer] ´abr´azol´asa megegyezik a bin´aris sz´ amrendszern´el megismert le´ır´ assal, azaz egy nem negat´ıv eg´esz sz´amot a kettes sz´amrendszerbe atv´ ´ altott form´ aj´ aban t´ arolunk. A t¨om¨orebb ´ır´asm´od miatt ugyanakkor ezt legt¨obbsz¨or nem bin´ aris, hanem hexadecim´alis form´aban ´ırjuk le. (Ne feledj¨ uk, hogy a bin´arisb´ol hexadecim´alisba v´ alt´ as nem m´ as, mint n´egy bites´evel csoportos´ıt´as, ahogy azt az el˝ oz˝oekben l´athattuk.) A kapott ´ert´ekeket ´ altal´ aban valamilyen fix hosszon t´aroljuk (a nem haszn´alt helyi´ert´ekekre null´ at ´ırunk), ami a gyakorlatban kiz´ ar´olag eg´esz byte m´eret˝ u ´abr´azol´ ast jelent. ´Igy az el˝ojel n´elk¨ uli eg´eszek is legt¨ obbsz¨ or 1, 2, 4, 8, . . . byte (8, 16, 32, 64, . . . bit) hossz´ uak lehetnek. ´Igy is h´ıvjuk ezeket: 8 bites el˝ ojel n´elk¨ uli eg´esz, 16 bites el˝ojel n´elk¨ uli eg´esz stb. 3.1.1. p´ elda. A 46[10] sz´ amot a mem´ori´aban a k¨ovetkez˝ok´eppen t´aroljuk 1 b´ajton: 00101110 (=0x2E). 3.1.2. feladat. Az ¨ osszead´ as m˝ uvelet hogyan v´egezhet˝o el az el˝ojel n´elk¨ uli eg´esz sz´amok bin´aris t´ arol´ asa eset´en? Adjunk erre m´odszert (algoritmust)! 3.1.3. feladat. Hogyan d¨ onthet˝ o el k´et el˝ ojel n´elk¨ uli eg´esz sz´amr´ol, hogy melyik a nagyobb? Adjunk r´ a algoritmust!
3.2. Negat´ıv eg´ esz sz´ amok ´ abr´ azol´ asa Ebben a r´eszben a negat´ıv eg´eszek ´ abr´azol´as´anak v´altozatait tekintj¨ uk ´at. 3.2.1. El˝ ojelbites ´ abr´ azol´ as A legegyszer˝ ubb m´odszer az el˝ ojeles eg´eszek ´abr´azol´as´ara, ha az el˝ojel n´elk¨ uli eg´eszek ´abr´azol´ as´ahoz egy el˝ ojelet jelent˝ o bitet adunk (ami 0, ha pozit´ıv az el˝ojel ´es 1, ha negat´ıv az el˝ojel) ´es az abr´ ´ azol´ asb´ ol fennmarad´ o t¨ obbi biten t´aroljuk a sz´am abszol´ ut ´ert´ek´et az el˝oz˝ oekben t´argyaltak szerint. 3.2.1. p´ elda. A −32 el˝ ojelbites ´ abr´ azol´asa 8 biten (1 bit el˝ojel + 7 bit ´ert´ek): 10100000 3.2.2. p´ elda. A 18 el˝ ojelbites ´ abr´ azol´asa 8 biten (1 bit el˝ojel + 7 bit ´ert´ek): 00010010 Ez a megold´ as sok szempontb´ ol nem megfelel˝o: a legk´ezenfekv˝obb probl´ema, hogy ezzel a m´odszerrel lehets´eges a +0 ´es a −0 ´ abr´ azol´asa is (8 biten ezek a k¨ovetkez˝ok: +0 = 00000000, -0 = 10000000), ami zavarhoz vezet (p´eld´ aul a nulla-e” vizsg´alatot ´ıgy k´et k¨ ul¨onb¨oz˝ o ´ert´ekre kell ” megtenni), tov´ abb´ a az ilyen m´odon fel´ırt sz´amokkal v´egzett m˝ uveletek bonyolultabbak, mint amennyire az felt´etlen¨ ul sz¨ uks´eges lenne. alt ¨osszead´ as m˝ uvelet elv´egezhet˝o-e m´ odos´ıt´ as n´elk¨ ul az 3.2.3. feladat. A 3.1.2. feladatban kital´ el˝ ojelbites sz´ am´abr´ azol´ asi m´odszer haszn´alat´aval? Adjunk meg egy p´eld´at! 3.2.4. feladat. M´ odos´ıtsuk a 3.1.3. feladatban kital´alt algoritmust, hogy az k´et el˝ojeles sz´am k¨ oz¨ ul is ki tudja v´ alasztani a nagyobbikat! 3.2.2. Kettes komplemens ´ abr´ azol´ as Sokkal jobb eredm´enyre vezet a kettes komplemens ´abr´azol´ as: ahelyett, hogy egy el˝ojelbittel jel¨oln´enk az el˝ ojelet, a k¨ ovetkez˝ o m´odon j´ arunk el: a negat´ıv sz´ amhoz egyet hozz´ aadunk, az eredm´eny abszol´ ut ´ert´ek´et bin´ arisan ´ abr´ azoljuk a megadott sz´am´ u biten (az el˝oz˝ oekben t´argyaltak szerint, mivel ez nem negat´ıv), v´eg¨ ul az ´ıgy kapott sz´ amjegyeket invert´aljuk. Ebb˝ol a sz´am´ıt´asi m´odb´ol k¨ ovetkezik az ´ abr´ azol´ as neve: kettes komplemens. A kettes komplemens sz´ am´ abr´ azol´ asi m´odszert el˝ ojeles eg´esz [signed integer] sz´am´abr´azol´asnak nevezz¨ uk. 3.2.5. p´ elda. A −2 kettes komplemens ´abr´azol´ asa 8 biten: −2 + 1 = −1 ennek abszol´ ut ´ert´eke: 1, ´ abr´ azolva: 00000001, invert´ alva: 11111110. 5
3.2.6. p´ elda. A −19 kettes komplemens ´abr´azol´asa 8 biten: −19 + 1 = −18 ennek abszol´ ut ´ert´eke: 18, ´ abr´ azolva: 00010010, invert´alva: 11101101. Fontos tudnival´ ok: • Kettes komplemens ´ abr´ azol´ asban is lehets´eges nem negat´ıv sz´amok ´abr´azol´asa, aminek m´odja megegyezik az el˝ ojel n´elk¨ uli eg´eszek t´arol´ asi m´odj´aval. (Azaz ebben az esetben nem kell az el˝ oz˝ oekben ismertetett m˝ uveleteket elv´egezni.) • A kettes komplemens ´ abr´ azol´ asban m´ar csak egyetlen ´abr´azol´asi m´odja van a null´anak. • Az esetek t´ ulnyom´o t¨ obbs´eg´eben a g´epi sz´am´abr´azol´ as sor´an az el˝ojeles eg´eszek a´br´azol´ as´ara a kettes komplemens ´ abr´ azol´ ast haszn´ aljuk. 3.2.7. feladat. Adjuk meg a 0 kettes komplemens ´abr´azol´as´at 8, 16, 32, 64 biten! 3.2.8. feladat. Adjuk meg a −1 kettes komplemens ´abr´azol´as´at 8, 16, 32, 64 biten! 3.2.9. feladat. Adjuk meg az 1 kettes komplemens ´abr´azol´as´at 8 biten! 3.2.10. feladat. A 3.1.2. feladatban kital´alt ¨osszead´ as m˝ uvelet elv´egezhet˝o-e m´ odos´ıt´ as n´elk¨ ul a kettes komplemens sz´am´ abr´ azol´ asi m´odszer haszn´alat´aval? Adjuk ¨ossze az el˝ oz˝o k´et feladatban kisz´amolt, 8 bites −1 ´es 1 ´ert´eket, ´es ellen˝orizz¨ uk, hogy null´ at kaptunk-e! 3.2.11. feladat. K´et, kettes komplemens m´odon ´abr´azolt sz´ amr´ol hogyan d¨onthet˝o el, hogy melyik a nagyobb? Alkalmazhat´ o m´ odos´ıt´ as n´elk¨ ul ugyanaz az algoritmus, mint a 3.1.3 feladatban? 3.2.3. Eltolt ´ abr´ azol´ as Soroljuk fel egy list´ aban az n biten t¨ort´en˝o el˝ ojel n´elk¨ uli sz´am´abr´azol´ assal fel´ırhat´o ´ert´ekeket n¨ ovekv˝ o sorrendben. Az eltolt [excess] sz´am´abr´azol´ asi m´odszer ezeket az eltol´ as m´ert´ek´eben lefel´e tolja u ´gy, hogy az u ´jonnan bel´ep˝ o elemek az ´ert´ek szerint cs¨okken˝o negat´ıv sz´ amok legyenek (l´asd 2. ´ abra). t´ arolt adat 3 biten 000 001 010 011 100 101 110 111
adat ´ertelmez´ese el˝ ojel n´elk¨ uli eg´esz excess-2 0 −2 1 −1 2 0 3 1 4 2 5 3 6 4 7 5
excess-4 −4 −3 −2 −1 0 1 2 3
2. ´ abra. A 3 biten t´arolhat´o ´ert´ekek el˝ojel n´elk¨ uli eg´esz ´es excess-2 illetve excess-4 szerinti ´ertelmez´ese
3.2.12. feladat. L´etezik olyan excess ´abr´azol´ as, ami a negat´ıv sz´ amok eset´eben megegyezik a kettes komplemens ´ abr´ azol´ assal? A lista eltol´ asa helyett az ´ abr´ azoland´o ´ert´ekeket u ´gy is megkaphatjuk, hogy az ´abr´azoland´o sz´ amhoz hozz´ aadjuk az eltol´ as m´ert´ek´et, ´es az eredm´eny¨ ul kapott sz´ amot ´abr´azoljuk az el˝ojel n´elk¨ uli eg´esz sz´ am´abr´ azol´ asi m´odszere szerint. 3.2.13. feladat. Mi biztos´ıtja, hogy az el˝ oz˝o m´odszer m˝ uk¨odik? (Mi garant´alja, hogy nem negat´ıv sz´ amot kapunk, ha az ´ abr´ azoland´o sz´ amhoz hozz´aadjuk az eltol´ as m´ert´ek´et?) Ha m´egsem m˝ uk¨ odik, az mit jelent? 6
3.2.14. p´ elda. A −2 excess-2 ´ abr´ azol´asa 3 biten: −2 + 2 = 0, teh´ at ´abr´azoland´o a 0 a nem negat´ıv eg´eszek ´ abr´ azol´ asa szerint: 000 (l´asd 2. ´abra els˝o sora). 3.2.15. p´ elda. A −3 excess-4 ´ abr´ azol´asa 3 biten: −3 + 4 = 1, teh´ at ´abr´azoland´ o az 1 a nem negat´ıv eg´eszek ´ abr´ azol´ asa szerint: 001 (l´asd 2. ´abra m´asodik sora). 3.2.16. p´ elda. Az 5 excess-2 ´ abr´ azol´ asa 3 biten: 5 + 2 = 7, teh´ at ´abr´azoland´o a 7 a nem negat´ıv eg´eszek ´ abr´ azol´ asa szerint: 111 (l´ asd 2. ´abra utols´o sora).
3.3. Eg´ esz sz´ amok adat´ abr´ azol´ asainak ¨ osszehasonl´ıt´ asa 3.3.1. feladat. Hasonl´ıtsuk ¨ ossze az el˝oz˝ oekben ismertetett, negat´ıv sz´amok ´abr´azol´ as´ara is alkalmas m´odszereket az al´ abbi szempontok alapj´ an: • Az ¨ osszead´ as m˝ uvelet elv´egezhet˝ o ugyan´ ugy, mint a nem negat´ıv eg´eszek ´abr´azol´as´an´ al? • K´et ´ abr´ azolt sz´am eset´eben a kisebb/nagyobb eld¨ont´ese (rendez´es) elv´egezhet˝o ugyan´ ugy, mint a nem negat´ıv eg´eszekn´el? • H´ anyf´elek´eppen ´ abr´ azolhat´ o a nulla? • Hogyan v´egezhet˝ o el az invert´ al´ as (diszkr´et matematikai nyelven az addit´ıv inverz sz´am´ıt´ asa)? • Hogyan v´egezhet˝ o el a kivon´ as m˝ uvelet? 3.3.2. feladat. Hasonl´ıtsuk ¨ ossze a 8 bites sz´am´abr´azol´asok eset´en az el˝ojel n´elk¨ uli eg´esz, az el˝ ojelbites eg´esz, a kettes komplemens, a 127-tel eltolt, a 255-tel eltolt ´es a 256-tal eltolt sz´amabr´ ´ azol´ asokat! (T´ abl´ azatosan foglaljuk ¨ossze: egy sor legyen a t´arolt 8 bit, az oszlopok legyenek a vizsg´ alt ´ abr´ azol´ asi m´odok, egy adott mez˝ obe ´ırjuk be a mez˝o sor´anak megfelel˝o bitsorozat ´ertelmez´es´et az oszlopnak megfelel˝ o sz´ am´abr´azol´as eset´eben, hasonl´oan a 2. ´abr´ahoz!)
3.4. Eg´ esz sz´ amok ´ abr´ azol´ asi hat´ arai ´ es pontoss´ aga 3.4.1. El˝ ojel n´ elku esz t´ arol´ as ´ abr´ azol´ asi hat´ arai ´ es pontoss´ aga ¨ li eg´ Az N biten t¨ ort´en˝ o, el˝ ojel n´elk¨ uli eg´esz sz´ am´abr´azol´as eset´en a t´arolhat´o legkisebb ´ert´ek: 0, a t´ arolhat´ o legnagyobb ´ert´ek: 2N − 1. El˝ ojel n´elk¨ uli eg´esz sz´ am´abr´ azol´ as eset´eben a t´arol´as pontos, hiszen csak eg´esz sz´ amokat kell t´ arolni, ´es a hat´ arokon bel¨ ul minden eg´esz sz´ am pontosan t´arolhat´o. Ebb˝ ol ad´ od´oan az ´abr´azol´ asi intervallumot az ´ abr´ azolhat´ o sz´ amok egyenletesen t¨oltik ki (l´asd a 3. ´abr´an).
1 N
0
2 −1 = 31
3. ´ abra. 5 bites el˝ ojel n´elk¨ uli eg´esz sz´am´abr´azol´ as eset´en az a ´br´ azol´ asi intervallum ´es az ezen bel¨ ul ´abr´azolhat´o sz´ amok. 3.4.1. p´ elda. Ha 8 bites el˝ ojel n´elk¨ uli eg´esz ´abr´azol´ast haszn´alunk, akkor a legkisebb ´abr´azolhat´o sz´ am a 00000000 (´ert´eke 0), a legnagyobb ´abr´azolhat´o sz´ am az 11111111 (´ert´eke 255). 3.4.2. feladat. Mennyi a legnagyobb t´arolhat´o ´ert´ek 8, 16, 32, 64 bites el˝ojel n´elk¨ uli eg´esz eset´eben? ¨ 3.4.3. feladat. Osszesen h´ any k¨ ul¨ onb¨oz˝ o ´ert´ek t´arolhat´o 8, 16, 32, 64 biten, el˝ojel n´elk¨ uli eg´esz sz´ am´abr´ azol´ as eset´eben?
7
3.4.2. Kettes komplemens t´ arol´ as ´ abr´ azol´ asi hat´ arai ´ es pontoss´ aga Ha kettes komplemens m´ odon ´ abr´ azolunk egy eg´esz sz´amot ´es ehhez N bit ´all rendelkez´esre, akkor a t´ arolhat´ o legkisebb ´ert´ek: −2N −1 , a t´arolhat´o legnagyobb ´ert´ek: 2N −1 − 1. Kettes komplemens sz´ am´abr´ azol´ as eset´eben a t´ arol´ as pontos, hiszen csak eg´esz sz´ amokat kell t´arolni, ´es a hat´arokon bel¨ ul minden eg´esz sz´ am pontosan t´ arolhat´o. Ebb˝ol ad´ od´oan az ´abr´azol´asi intervallumot az abr´ ´ azolhat´ o sz´ amok egyenletesen t¨ oltik ki (l´asd a 4. ´abr´an).
−1 −2
N−1
1 0
= − 16
2
N−1
−1 = 15
4. ´ abra. 5 bites kettes komplemens sz´am´abr´azol´as eset´en az a ´br´ azol´ asi intervallum ´es az ezen bel¨ ul ´abr´azolhat´o sz´ amok. 3.4.4. p´ elda. Ha 8 bites kettes komplemens ´abr´azol´ ast haszn´alunk, akkor a legkisebb ´abr´azolhat´o sz´ am az 10000000 (´ert´eke -128), a legnagyobb ´abr´azolhat´o sz´ am a 01111111 (´ert´eke 127). 3.4.5. feladat. Kettes komplemens ´ abr´azol´as eset´en mi´ert nem ugyanannyi sz´am t´arolhat´o a pozit´ıv ´es a negat´ıv tartom´ anyban? (Azaz mi´ert nem -127 ´es 127 vagy -128 ´es 128 a k´et hat´ar?) 3.4.6. feladat. Mennyi az ´ert´eke a kettes komplemens ´abr´azol´assal, 8 biten t´arolt 11111111 illetve a 00000000 sz´ amoknak? 3.4.7. feladat. Eld¨ onthet˝ o egyszer˝ uen (r´an´ez´esre) egy kettes komplemens m´odon ´abr´azolt sz´amr´ ol, hogy az negat´ıv vagy pozit´ıv? ¨ 3.4.8. feladat. Osszesen h´ any k¨ ul¨ onb¨oz˝ o ´ert´ek t´arolhat´o 8, 16, 32, 64 biten, kettes komplemens sz´ am´abr´ azol´ as eset´eben? 3.4.9. feladat. Mi a kapcsolat a 3.4.3. feladat ´es a 3.4.8. feladatban kapott eredm´enyek k¨oz¨ott? 3.4.3. Eltolt t´ arol´ as ´ abr´ azol´ asi hat´ arai ´ es pontoss´ aga Az N biten t¨ ort´en˝ o eltolt-M ´ abr´ azol´ as eset´en a legkisebb ´abr´azolhat´o sz´am a −M , a legnagyobb abr´ ´ azolhat´ o sz´ am a −M + 2N − 1. Eltolt sz´am´abr´azol´as eset´eben a t´arol´ as pontos, hiszen csak eg´esz sz´amokat kell t´ arolni, ´es a hat´ arokon bel¨ ul minden eg´esz sz´ am pontosan t´arolhat´o. Ebb˝ ol ad´ od´ oan az ´ abr´ azol´ asi intervallumot az ´abr´azolhat´o sz´ amok egyenletesen t¨oltik ki (l´asd az 5. abr´ ´ an).
−1 −M = −16
1 0
N
−M+2 −1 = 15
5. ´ abra. 6 bites excess-16 sz´ am´abr´azol´as eset´en az ´ abr´ azol´ asi intervallum ´es az ezen bel¨ ul ´abr´azolhat´o sz´ amok.
3.4.4. T´ ulcsordul´ as Az eg´esz sz´ amok v´eges biten t¨ ort´en˝ o´ abr´azol´asa miatt mindig van legkisebb ´es legnagyobb ´abr´ azolhat´o sz´ am. Amikor m˝ uveletet v´egz¨ unk, elk´epzelhet˝o, hogy a m˝ uvelet eredm´enye m´ar nem abr´ ´ azolhat´ o az operandusokkal megegyez˝o m´eretben. Ezt a jelens´eget t´ ulcsordul´asnak [overflow] nevezz¨ uk. T´ ulcsordul´ as teh´ at lehets´eges pozit´ıv ´es negat´ıv ir´anyban is! Figyelem, az alulcsordul´as
8
(l´ asd a ??. r´eszt) nem a negat´ıv ir´ anyban t¨ort´en˝o t´ ulcsordul´ast jelenti! K¨onnyebben megjegyezhet˝ o, ha u ´gy tekint¨ unk a t´ ulcsordul´ asra, hogy a sz´am abszol´ ut ´ert´eke t´ ul nagy ´es emiatt nem abr´ ´ azolhat´ o. T´ ulcsordul´ as eset´en – megval´ os´ıt´ ast´ol f¨ ugg˝ oen – lehets´eges • lev´ ag´ as: a t´ ulcsordult eredm´eny m´eg ´abr´azolhat´o r´esz´et t´aroljuk, a nem ´abr´azolhat´o r´eszt egyszer˝ uen elfelejtj¨ uk”. 4 A legt¨obb architekt´ ura ´ıgy m˝ uk¨odik. ” • szatur´ aci´ o : a t´ ulcsordult eredm´eny helyett a legnagyobb illetve legkisebb ´abr´azolhat´o ´ert´eket t´ aroljuk. 3.4.10. p´ elda. T´ ulcsordul´ as pozit´ıv ir´anyban: ha 8 bites el˝ojel n´elk¨ uli eg´eszekkel dolgozunk, a 156+172=328 ¨ osszeget m´ar nem tudjuk 8 biten t´arolni (mert a legnagyobb t´arolhat´o ´ert´ek a 255). 3.4.11. p´ elda. T´ ulcsordul´ as negat´ıv ir´anyban: ha 8 bites el˝ojeles eg´eszekkel dolgozunk, a -84+(79)=-163 ¨ osszeget m´ar nem tudjuk 8 biten t´arolni (mert a legkisebb t´arolhat´ o ´ert´ek a -127). 3.4.12. p´ elda. Lev´ ag´ as: ha 8 bites el˝ojel n´elk¨ uli eg´eszekkel dolgozunk, a 156[10] = 10011100[2] ´es a 172[10] = 10101100[2] val´ odi ¨ osszege (328[10] = 101001000[2] ) helyett annak a 8 utols´o bitj´et t´ aroljuk: 01001000. 3.4.13. p´ elda. Szatur´ aci´ o: ha 8 bites el˝ojel n´elk¨ uli eg´eszekkel dolgozunk, a 156[10] = 10011100[2] ´es a 172[10] = 10101100[2] val´ odi ¨ osszege (328[10] = 101001000[2] ) helyett az ´abr´azolhat´o legnagyobb sz´ amot t´ aroljuk: 11111111. 3.4.14. feladat. Mi (volt) az Y2K probl´ema? Mi a kapcsolat a t´ ulcsordul´as ´es az Y2K probl´ema k¨ oz¨ ott?
4 P´ eld´ aul mechanikus g´ az´ or´ an´ al vagy r´ egebbi aut´ ok kilom´ eter sz´ aml´ al´ oj´ an´ al figyelhet˝ o meg ilyen jelens´ eg, mert fix sz´ am´ u helyi´ ert´ eken t¨ ort´ enik a m´ er´ es. A kilom´ eter sz´ aml´ al´ ok tekintet´ eben ezt a tulajdons´ agot kihaszn´ alva tekerik k¨ orbe egyes nepperek az ´ or´ at, hogy a kocsi kevesebbet futottnak t˝ unj¨ on.
9
