FAV-ZCU/KIV PPA1/18. Zobrazení dat v počítači.md

Zobrazení dat v počítači

• Všechna data uložená v počítači jsou uložena jako posloupnost binárních číslic (bitů) uspořádaná po bytech (8 bitů)
• Způsob uložení dat se nazývá kódování
  • Je dán datovým typem dat
    • Určuje, jaký mají význam jednotlivé bity a byty
• Rozsahy hodnot jednotlivých datových typů a počet bytů, které zabírají v paměti, byly zmíněny v Kap. 3.2
• Jakým způsobem jsou jednotlivé datové typy uloženy (jaké kódování je použito), je popsáno v následujících podkapitolách

Převod čísel mezi soustavami

• Nativní číselná soustava počítače, odpovídající uspořádání fyzické paměti, je dvojková (binární)
  • Ruční zápis binárních čísel je však dlouhý, proto se pro zápis binárních čísel často používá šestnáctková (hexadecimální) soustava, která pro stejné číslo potřebuje 4x méně číslic
    • Na jeden byte stačí 2 hexadecimální číslice, ale 8 binárních číslic
• V běžném životě se většinou počítá v desítkové (dekadické) soustavě
• Čísla lze mezi jednotlivými soustavami převádět pomocí kalkulačky či jiných programů (přepočet je dostupný např. v PSPadu)
• Algoritmy pro ruční převod čísel mezi dvojkovou, desítkovou a šestnáctkovou soustavou jsou v následujících podkapitolách

Převod z desítkové do dvojkové soustavy (univerzální postup)

• Celou a desetinnou část řešíme zvlášť
• Celá část
  • Celou část dělíme 2, píšeme si zbytky po dělení
  • Poslední číslice výsledku (0 nebo 1) a zbytky přečtené odzadu dají celou část binárního čísla
• Desetinná část
  • Desetinnou část násobíme 2, píšeme si číslici vlevo od desetinné čárky (v celé části)
  • Číslice přečtené popředu dají desetinnou část binárního čísla

Převod z desítkové do dvojkové soustavy („intuitivní“)

• „Intuitivní“ postup pro celá čísla
• Napsat si vyčíslené mocniny 2, nalézt největší menší nebo stejnou mocninu 2, zapsat pod ní 1 a odečíst ji od převáděného čísla
• Opakovat, dokud z čísla nezbude 0
• Příklad převodu 69 na jeho reprezentaci v binární soustavě
  • Odečtu 64, protože 64 < 69, pod 64 zapíšu 1, zbude 5
  • Odečtu 4, protože 4 < 5, pod 4 zapíšu 1, zbude 1
  • Odečtu 1, protože 1 = 1, pod 1 zapíšu 1, zbude 0
  • Zbytek pozic doplním 0

Převod z dvojkové do desítkové soustavy

• Převod z dvojkové soustavy do desítkové (pro celá i reálná čísla)
  • Každou číslici označit zprava doleva jako zvyšující se mocninu 2
  • Mocniny u číslic 1 vyčíslit a sečíst

Převod z dvojkové do šestnáctkové soustavy

• Převod z dvojkové soustavy do šestnáctkové (pro celá i reálná čísla)
  • Rozdělit číslo na čtveřice od desetinné čárky (na obě strany)
  • Každá čtveřice je jedna číslice šestnáctkové soustavy (0 až F)
    • Vyčíslit hodnotu čtyř binárních číslic jako při převodu do desítkové soustavy

Převod z šestnáctkové do dvojkové soustavy

• Převod z šestnáctkové do dvojkové soustavy (pro celá i reálná čísla)
  • Každou šestnáctkovou číslici převést do desítkové soustavy
  • Použít pro každou číslici intuitivní postup pro převod z desítkové do dvojkové soustavy

Kódy pro uložení celočíselných datových typů

• Pro uložení celočíselných datových typů existuje několik kódů
  • Bezznaménkové
  • Znaménkové
    • Přímý kód
    • Inverzní kód
    • Doplňkový kód
    • Kód s posunutou nulou

Uložení celých čísel bez znaménka

• Zápis ve dvojkové soustavě zarovnaný na násobky bytů
• Pouze pro nezáporná čísla
• Např. 131 je 1000 0011, 3 je 0000 0011

Přímý kód

• Kladná čísla stejná jako u bezznaménkového kódování
• Znaménko určeno v MSB (Most Significant Bit – ten nejvíce vlevo)
• Např. -3 je 1000 0011
• Nevýhody
  • Dvojí nula – 1000 0000 (záporná) a 0000 0000 (kladná)
• Používá se pro zobrazení mantisy u reálných čísel

Inverzní kód

• Kladná čísla stejná jako u bezznaménkového kódování
• Pro záporná čísla se mění všechny 0 na 1 a 1 na 0
• Např. -3 je 1111 1100
• Nevýhody
  • Dvojí nula 1111 1111 (záporná) a 0000 0000 (kladná)
• Používá se v bitových operacích, případně jako mezikrok v doplňkovém kódu

Doplňkový kód (dvojkový doplněk)

• Matematická definice
  • D(x) = x pro x ≥ 0
  • D(x) = x + K pro x < 0, kde K = 2^{n} (kapacita soustavy)
• Kladná čísla stejná jako u bezznaménkového kódování
• Záporná čísla jsou uložena jako „inverzní kód + 1“
• Např. -3 je 1111 1101
• Používá se výhradně pro uložení celých znaménkových čísel
  • Např. typy byte, short, int, long v Javě
• Výhody
  • Pouze jedna nula – 0000 0000
  • Odečítání je přičítání záporného čísla
• Pozor na nesymetrický rozsah -128 až 127 (pro 1 byte)
  • Absolutní hodnota nejmenšího záporného čísla je mimo rozsah
• Přetečení
  • Nastává, když nám aritmetickými operacemi vyjde hodnota, která se nevejde do daného rozsahu
  • Např. 127 + 1 (pro 1 byte) = -128
    • MSB se přičtením 1 k maximálnímu číslu nastaví na 1, což indikuje záporné číslo, proto vyjde -128
  • Možné reakce na přetečení
    • Přerušení výpočtu jako reakce na chybu
    • Pokračování výpočtu s nesprávným výsledkem – používá Java
  • Zda přetečení nastane, závisí na vstupních číslech – někdy může program fungovat správně a někdy ne => špatně se hledá

Kód s posunutou nulou

• Lineární posun nuly po celočíselné ose
  • 0000 0000 je nejmenší (záporné) číslo
  • Nula je ve středu rozsahu, tedy 2^{n-1} – 1, např. 0111 1111
  • 1111 1111 je největší kladné číslo
• Podobně jako u doplňkového kódu je rozsah nesymetrický
• Nevýhoda
  • Kladná čísla jsou odlišná od bezznaménkového kódování
  • Např. 3 je 1000 0010
• Používá se pro uložení exponentu u reálných čísel

Kódy pro uložení reálných datových typů

• Aproximace reálných čísel
• Též nazýváno „zobrazení v pohyblivé řádové čárce“ (floating point)
• Dle normy IEEE 754 na 4 nebo 8 bytech (v Javě float – 4 byty a double – 8 bytů)
  • Kromě samotného kódování norma IEEE 754 definuje i standardní chování základních aritmetických operací (sčítání, odčítání, násobení, dělení, …)

IEEE 754 na 4 bytech

• Formát v pohyblivé řádové čárce s jednoduchou přesností (single-precision floatingpoint format)
• Používá 4 byty (32 bitů)
  • Rozsah v absolutní hodnotě cca 10-45 až 10+38
  • Přesnost na cca 6 až 7 (dekadických) desetinných míst
  • Rozdělení na znaménko, exponent a mantisu
• Znaménkový bit patří mantise (nikoliv exponentu)
  • 0 odpovídá +
  • 1 odpovídá -
• Mantisa (23 bitů)
  • Uložena v přímém kódu (znaménkový bit je oddělen exponentem)
  • Je normovaná
    • 1 ≤ mantisa < základ (tj. 2)
    • Její první bit v normovaném tvaru musí tedy být vždy 1 (1 před desetinou čárkou) a proto se neukládá
  • Určuje přesnost čísla
• Exponent (8 bitů)
  • Uložen v kódu s posunutou nulou, kde 0 je 0111 1111
  • Určuje rozsah čísla
• Hodnota 0 je uložena jako samé nuly
• Hodnota čísla se dá vypočítat
• Určení, jak bude vypadat zápis v IEEE 754 na 4 bytech pro číslo -258,125
• Přesnost uložených čísel je omezená
• Některá čísla jsou zaokrouhlená
• Pokud je hodnota čísla menší než minimum, číslo nelze zobrazit, zaokrouhluje se automaticky na 0 => podtečení
• Pokud je hodnota čísla v absolutní hodnotě větší než maximum, číslo nelze zobrazit, zaokrouhluje se automaticky na (kladné nebo záporné) nekonečno => přetečení
• NaN (Not a Number)
  • Definovaná hodnota při chybné operaci s reálným číslem (např. dělení nuly nulou)
• Operace s reálnými čísly
  • Sčítání
    • Porovnáním exponentů se zjistí menší číslo, tomu se zvětší exponent na úroveň většího čísla => zmenšuje se přesnost (mantisa)
    • Pro exponentem hodně odlišná čísla se může v důsledku místo menšího čísla přičítat nula
  • Násobení
    • Exponenty se sečtou
    • Mantisy se vynásobí
• Obecně platí
  • Nepoužívat reálná čísla tam, kde stačí celá
    • Výpočty nemusí být přesné (zaokrouhlovací chyby)
    • Výpočty s celými čísly mohou být rychlejší
  • Nepoužívat pro reálná čísla porovnání na rovnost (operátor „==“)

IEEE 754 na 8 bytech

• Formát v pohyblivé řádové čárce s dvojitou přesností (double-precision floating-point format)
• Používá 8 bytů (64 bitů)
  • Přesnost na cca 15 (dekadických) desetinných míst
• Způsob uložení je úplně stejný jako u 4 bytů, jen se liší velikost exponentu a mantisy
  • Znaménko 1 bit
  • Mantisa 52 bitů
  • Exponent 11 bitů

Kódy pro uložení znaků a řetězců

Uložení znaků

• Přiřazují každému znaku zvolené abecedy nezáporné celé číslo
• Existuje mnoho kódů

Uložení řetězců

• Řetězec je složen z jednotlivých znaků (v daném kódování)
• Řetězec má délku udávanou v počtu znaků
• Způsob uložení v paměti závisí především na použitém programovacím jazyce
  • Java
    • String
      • Řetězec je neměnná (immutable) instance třídy
      • Znaky řetězce jsou v instanci uloženy jako pole znaků (char[])
      • Řetězec tak může mít libovolnou délku
    • StringBuilder/StringBuffer
      • Měnitelný řetězec
      • Kromě délky má i kapacitu (kolik znaků lze do řetězce uložit), která je rovněž proměnná
      • Znaky řetězce jsou v instanci rovněž uloženy jako pole znaků (char[])
      • Řetězec tak může mít libovolnou délku
  • C
    • Řetězec je pole bytů začínající indexem 0
    • Za posledním platným znakem řetězce je přidán znak s hodnotou 0 (tj. '\0' – nikoliv znak '0')
    • Řetězec tak může mít libovolnou délku
    • V řetězci se nesmí vyskytnout znak '\0'
  • Pascal
    • Řetězec je pole bytů, znaky jsou uloženy od indexu 1
    • Na indexu 0 je uložena délka řetězce, která je tak omezena na maximálně 255 znaků
    • Platí pro původní specifikaci jazyka Pascal
      • Jeho novější mutace (např. FreePascal) obsahují i další typy řetězců

Uložení logického datového typu (boolean)

• Též booleovský datový typ
• Ukládají se jen dvě hodnoty
  • true (pravda, logická 1)
  • false (nepravda, logická 0)
• Prakticky se realizují pomocí celočíselného bezznaménkového typu
• Některé jazyky specifický logický typ nemají a používají místo něj celočíselný typ
  • Např. C

Problém ukládání dat do fyzické paměti

• Týká se všech datových typů, jejichž hodnoty jsou uloženy na více než jednom bytu tj. většina)
  • Demonstrujeme na uložení neznaménkového čísla na 4 bytech (01A2B3C4)H počínaje adresou 1000
• Pokud má datový typ větší délku než jeden byte, pak jsou dvě možnosti, jak tyto byty uložit do fyzické paměti
  • Big Endian (BE) – „vyšší řády na nižší adrese“ – „přirozené“ uložení
    • Číslo bude uloženo jako 01 A2 B3 C4
      • Adresa 1000: 01
      • Adresa 1001: A2
      • Adresa 1002: B3
      • Adresa 1003: C4
  • Little Endian (LE) – „vyšší řády na vyšší adrese“ – „obrácené“ uložení
    • Číslo bude uloženo jako C4 B3 A2 01
      • Adresa 1000: C4
      • Adresa 1001: B3
      • Adresa 1002: A2
      • Adresa 1003: 01
• Obecně se nedá říct, s kterým způsobem se setkáme více
  • Je běžné, že se oba způsoby vyskytují na jednom počítači
• Může způsobit potíže při zápisu a následném čtení binárních souborů
  • Je potřeba vědět, zda je soubor zapsán jako LE nebo BE
• Způsob záleží na
  • Procesoru
    • Např. Intel LE, Motorola BE
  • Operačním systému
    • Windows LE
  • Programovacím jazyce
    • Java BE
      • Zaručuje přenositelnost binárních souborů
        • Pokud však byly zapsány i přečteny programem napsaným v Javě
    • V mnoha programovacích jazycích není určen a přebírá se způsob od operačního systému