Skaičiavimo sistemos: uždaviniai su sprendimais žingsnis po žingsnio

1Kas yra skaičiavimo sistema

Kasdieniame gyvenime skaičiuojate dešimtaine sistema, kurios pagrindas 10. Joje yra dešimt skaitmenų, nuo 0 iki 9, ir kiekviena vieta verta dešimt kartų daugiau nei vieta jos dešinėje.

Skaičiuje 352 trejetas vertas 300, penketas 50, o dvejetas 2. Vietų vertės iš dešinės yra 1, 10, 100.

Kompiuteris viską saugo kaip įjungtus arba išjungtus jungiklius. Todėl jis skaičiuoja dvejetaine sistema, kurios pagrindas 2, su vieninteliais skaitmenimis 0 ir 1.

Vienas dvejetainis skaitmuo yra bitas. 8 bitų grupė yra baitas.

Taisyklė kiekvienoje sistemoje ta pati: kiekvieno skaitmens vertė yra jo reikšmė, padauginta iš pagrindo laipsnio.

2Dvejetainė ir šešioliktainė

Dvejetainėje sistemoje vietų vertės iš dešinės yra 1, 2, 4, 8, 16 ir t. t. Kiekviena vieta verta du kartus daugiau nei vieta jos dešinėje.

8 bitų skaičiui vietų vertės yra 128, 64, 32, 16, 8, 4, 2 ir 1.

Norėdami perskaityti dvejetainį skaičių, sudėkite visų bitų, lygių 1, vietų vertes. Skaičiui 0011 0010 tai 32 + 16 + 2 = 50.

Ilgas bitų eilutes sunku skaityti. Programuotojai jas dažnai rašo šešioliktaine (hex) sistema, kurios pagrindas 16.

Hex reikia 16 skaitmenų. Naudojami nuo 0 iki 9, o tada raidės A = 10, B = 11, C = 12, D = 13, E = 14 ir F = 15.

Hex vietų vertės iš dešinės yra 1, 16, 256 ir 4096. Hex skaičius dažnai rašomas su 0x priekyje, pavyzdžiui, 0x2F.

Vienas hex skaitmuo yra lygiai 4 bitai, todėl 0011 0010 yra 0x32: 0011 yra 3, o 0010 yra 2.

3Neigiami skaičiai: papildomasis kodas

Baitas, kurio visos vietos teigiamos, saugo nuo 0 iki 255. Tai vadinama be ženklo.

Neigiamiems skaičiams saugoti kompiuteriai naudoja papildomąjį kodą (two’s complement). Vienintelis skirtumas: kairiausias bitas vertas −128, o ne +128.

Taigi 1000 0011 yra −128 + 2 + 1 = −125. Kairiausias bitas vadinamas ženklo bitu: kai jis 1, skaičius neigiamas.

8 bitų papildomojo kodo skaičius kinta nuo −128 (1000 0000) iki +127 (0111 1111).

Norėdami užrašyti neigiamą skaičių −x, pradėkite nuo +x dvejetainėje sistemoje, invertuokite kiekvieną bitą (0 tampa 1, 1 tampa 0) ir pridėkite 1.

Pavyzdys −5: 5 yra 0000 0101. Invertuota gaunama 1111 1010. Pridėjus 1 gaunama 1111 1011.

Tas pats bitų rinkinys, skaitomas kaip be ženklo, turi vertę 256 − x. Skaičiui −5 tai 251, ir 1111 1011 iš tikrųjų yra 128 + 64 + 32 + 16 + 8 + 2 + 1 = 251.

4Metodas žingsnis po žingsnio

Dvejetainis ar hex į dešimtainį:

1. Po kiekvienu skaitmeniu užrašykite vietos vertę: dvejetainei 2 laipsnius, hex 16 laipsnius, pradėdami nuo 1 dešinėje.
2. Hex sistemoje kiekvieną raidę pakeiskite jos verte: nuo A = 10 iki F = 15.
3. Kiekvieną skaitmenį padauginkite iš jo vietos vertės ir viską sudėkite.

Papildomasis kodas:

1. Norėdami perskaityti rinkinį, kairiausiam bitui priskirkite vertę −128 (8 bitais) ir sudėkite visų vienetinių bitų vietų vertes.
2. Norėdami užrašyti −x, užrašykite +x 8 bitais, invertuokite kiekvieną bitą ir pridėkite 1.
3. To rinkinio vertė be ženklo yra 256 − x. Naudokite ją savo bitams patikrinti.

Bitai, intervalai ir atmintis:

1. n bitų duoda 2ⁿ skirtingų rinkinių.
2. Be ženklo jie saugo nuo 0 iki 2ⁿ − 1. Papildomuoju kodu jie saugo nuo −2ⁿ⁻¹ iki 2ⁿ⁻¹ − 1.
3. Kad k elementų turėtų savo kodą, raskite mažiausią b, kuriam 2^b ≥ k.
4. Atminčiai elementų skaičių padauginkite iš bitų elementui, tada baitams dalykite iš 8, o KiB – iš 1024.

5Išspręstas pavyzdys

Sekite kiekvieną žingsnį. Pabandykite nuspėti kitą, prieš jį atidarydami.

6Dažnos klaidos

• Pamirštama pridėti 1 po bitų invertavimo. Rezultatas vienetu per mažas.
• Papildomojo kodo rinkinys skaitomas kaip be ženklo, pavyzdžiui, 1111 1111 kaip 255, o ne −1.
• Ženklo bitas laikomas minuso ženklu prieš kitus bitus. Papildomajame kode jis vertas −128.
• Vietos išdėstomos atvirkščia tvarka. Vieta, verta 1, visada yra dešinėje.
• Hex sistemoje naudojama A = 11. Raidės prasideda nuo A = 10.
• Atminties uždaviniuose painiojami bitai ir baitai. Bitų skaičių padalykite iš 8.

7Kaip atrodo egzamino uždaviniai

• Lengvi: dvejetainis ir hex į dešimtainį. 8 bitų dvejetainį skaičių arba 3 skaitmenų hex skaičių paverskite dešimtainiu.
• Vidutiniai: papildomasis kodas. Perskaitykite 8 bitų rinkinio su ženklu vertę arba neigiamą skaičių užrašykite rinkiniu ir nurodykite jo vertę be ženklo.
• Sunkūs: bitai, intervalai ir atmintis. Didžiausia arba mažiausia (labiausiai neigiama) vertė, tilpstanti n bituose, bitų skaičius k kodų, arba paveikslėlio užimama atmintis.

Sunkaus uždavinio pavyzdys: 256 × 256 paveikslėlis, kurio pikselis 24 bitų, užima 256 · 256 · 24 / 8 / 1024 = 192 KiB.