Vnitřní reprezentace datových typů

Celá čísla se znaménkem

• Existují 3 způsoby ukládání čísel se znaménkem (přímý, inverzení a doplňkový kód).

• V praxi se však již používá jen doplňkový kód .

• Pro každé kódování platí, že nejvýznamnější bit je rezervován pro znaménko (0 ... plus, 1 ... minus).

Přímý kód

• Nejvýznamnější bit (ten na prvním místě) udává znaménko (0 ... plus, 1 ... minus), zbytek bitů se použije na klasický binární zápis daného čísla.

• Kladná čísla: například číslo 5 (v desítkové soustavě) je v binární formě 00000101 (pokud má číslo 8 bitů).

• U záporných čísel je na prvním místě 1, tj. číslo -5 je reprezentováno jako 10000101.

Nevýhody přímého kódu

Přímý kód je jednoduchý a intuitivní, ale má dvě zásadní omezení:

• Aritmetické operace: Sčítání a odčítání čísel v přímém kódu vyžaduje různé postupy pro různé kombinace znamének operandů, což je v počítačových operacích nepraktické.

  • Při sčítání dvou kladných nebo dvou záporných čísel je postup jednoduchý, ale při sčítání kladného a záporného čísla musíte vzít v úvahu bit znaménka, což komplikuje výpočet.

  • Například, při sčítání +5 (0000101) a -3 (1000011) v přímém kódu musíme zapřemýšlet, co udělat se znaménkovým bitem.

• Dvě nuly: Existují dvě reprezentace nuly : +0 (00000000) a -0 (10000000), což je neefektivní a může vést k nejednoznačnosti.

Inverzní kód

• Stejně jako u přímého binárního kódu je nejvýznamnější bit určen pro znaménko (0 ... plus, 1 ... minus).

• Kladná čísla:

  • Kladná čísla jsou reprezentována stejně jako v přímém binárním kódu.

• Záporná čísla:

  • Pro získání záporného čísla invertujeme všechny bity jeho kladného ekvivalentu.

  • Například, máme-li zapsat -5 a použijeme 8bitový formát, nejprve zapíšeme +5 jako 00000101, a pak invertujeme všechny bity, což dá 11111010.

Vlastnosti inverzního kódu

• Existují dvě reprezentace nuly: +0 a -0. Pro 8-bitový formát +0 je 00000000 a -0 je 11111111.

• Aritmetické operace:

  • Ačkoli sčítání v inverzním kódu je jednodušší než v přímém kódu, stále není tak efektivní jako ve doplňkovém kódu (viz níže). 

  • Př.: Sečteme čísla -5 (11111010) a +3 (00000011).

    • Binární součet je 11111101, což je opravdu -2.

  • End-Around Carry

    • Při sčítání dvou čísel může dojít k přenosu z nejvyššího bitu. Pokud se tak stane, tak se tento přenos musí přidat zpět do součtu na nejnižší bit.

    • Př.: sečeme -1 (11111110) a -1 (11111110), výsledkem je 11111100.  Ze znaménkového bitu však přenášíme 1, kterou musíme přičíst k nejnižšímu bitu, tj. dostáváme 11111101, což je -2.

Inverzní kód byl populární v raných počítačích, ale dnes je většinou nahrazen doplňkovým kódem kvůli jeho efektivitě a jednodušší implementaci aritmetických operací, zejména sčítání.

Doplňkový kód

Doplňkový kód, známý také jako two's complement, je standardní metoda používaná v počítačových systémech pro reprezentaci záporných čísel. 

Kladná čísla:

• Kladná čísla jsou reprezentována stejně jako v přímém binárním kódu.

Záporná čísla:

• Pro získání doplňkového kódu záporného čísla nejprve najdeme binární reprezentaci jeho absolutní hodnoty.

• Poté invertujeme všechny bity (převedeme 0 na 1 a 1 na 0).

• Nakonec přičteme k invertovanému číslu 1.

• Např. reprezentace -5 v 8bitovém doplňkovém kódu:

  • |-5| = 5, v binárním kódu je to 00000101.

  • Invertujeme všechny bity: 11111010.

  • Přičteme 1: 11111011, což je -5 v doplňkovém kódu.

Vlastnosti doplňkového kódu:

• Doplňkový kód umožňuje použití stejných aritmetických operací pro kladná i záporná čísla.

  • Můžeme použít stejný postup pro sčítání či odčítání bez ohledu na to, zda jsou čísla kladná nebo záporná. Například sčítání 5 a -3 nevyžaduje žádný speciální postup; stačí sčítat binární reprezentace obou čísel.

• Na rozdíl od inverzního a přímého kódu, doplňkový kód má pouze jednu reprezentaci pro nulu.

• Pokud uvažujeme číslo zapsané na 8 bitech, tak záporných čísel je o jedna více než kladných čísel, tj. čísla nabývají hodnot od -128 do + 127.

Čísla s pohyblivou desetinnou čárkou

V C++ jsou čísla s pohyblivou desetinnou čárkou (floating-point numbers) uložena v paměti podle standardu IEEE 754, který je nejrozšířenějším způsobem reprezentace těchto čísel v počítačích. Tento standard definuje, jak jsou čísla uložena a jak se provádějí aritmetické operace.

Formát IEEE 754

Standard IEEE 754 pro čísla s pohyblivou desetinnou čárkou zahrnuje několik různých formátů, ale nejběžnější jsou single-precision (32 bitů) a double-precision (64 bitů).

Single-Precision (32bit) – v C++ float:

• Znaménkový bit (Sign Bit): 1 bit, určuje, zda je číslo kladné (0) nebo záporné (1).

• Exponent: 8 bitů, udává velikost čísla (mocnina dvojky).

• Mantisa (Significand): 23 bitů, určuje vlastní číselnou hodnotu.

Double-Precision (64bit) – v C++ double:

• Znaménkový Bit: 1 bit.

• Exponent: 11 bitů.

• Mantisa: 52 bitů.

Jak to funguje

Znaménkový bit:

• Tento bit je 0 pro kladná čísla a 1 pro záporná čísla.

Exponent:

• Exponent je vyjádřen v tzv. "bias" formátu. 

• U 32bitových čísel je to 127 (2^(8-1)-1), což znamená, že exponent je uložen s přičtenou hodnotou 127. 

• Například exponent 2 je uložen jako 129 (2 + 127).

Mantisa:

• Mantisa představuje vlastní číslici a je normalizována. 

• První číslice před desetinnou čárkou (která je u normalizovaných čísel vždy 1) není uložena (takže máme k dispozici jeden bit navíc).

Příklad

Například číslo 0,15625 by bylo v single-precision formátu uloženo následovně:

1. Převedení do dvojkové soustavy:

   • Převedení čísla 0,15625 do dvojkové soustavy, viz https://www1.cuni.cz/~jilekm/lekce/binarycode.pdf.

   • Výsledkem je 0,00101.

2. Normalizace:

   • Normalizace čísla tak, aby mělo tvar 1,xxxxx * 2^y.

   • Tj. v našem příkladu bude 1,01 * 2^(-3) – desetinnou čárku jsme posunuli o tři místa doleva.

3. Uložení mantisy a exponentu:

   • Uložení normalizované mantisy (bez první jedničky) a exponentu (s biasem).

   • Tedy mantisa je 01000000000000000000000 (za jedničkou je 21 nul, neboť mantisa má celkem 23 bitů).

   • Exponent je -3, přičteme k němu bias, tj. 127, máme tedy -3+127 = 124, což je ve dvojkové soustavě 01111100 (exponent zabírá 8 bitů)

4. Znaménkový bit:

   • Jelikož je číslo kladné, znaménkový bit bude 0.

Číslo 0,15625 bude tedy uloženo jako 0|01111100|01000000000000000000000.

Chyby při aritmetických operacích v C++

Přetečení (Overflow)

• Přetečení nastává, když výsledek operace překročí maximální hodnotu, kterou lze uložit v daném datovém typu. To může vést k neočekávaným výsledkům.

• Příklady přetečení:

  • Celá čísla:

    • Například, pokud máme proměnnou typu int a pokusíme se do ní uložit hodnotu vyšší než maximální možnou hodnotu pro int, dojde k přetečení.

    • V C++ může přetečení u celých čísel vést k neočekávaným záporným hodnotám nebo nedefinovanému chování.

    • Např. INT_MAX+1 = -2147483648

    • Případně, INT_MIN-1 = 2147483647

  • Bezznaménková celá čísla (např. unsigned int):

    • U bezznaménkových typů dojde k "přetočení" zpět na nulu (např. UINT_MAX + 1 = 0).

    • Pokud je výsledkem aritmetické operace číslo větší než maximální možné uložitelné číslo, tak se za výsledek bere výsledek % 2^n, kde n je počet bitů, do kterých číslo ukládáme.

Podtečení (Underflow)

Výsledkem výpočtu je číslo s přesnější (absolutní) hodnotou, než jakou může počítač skutečně reprezentovat v paměti.

Příklady podtečení:

• Čísla s plovoucí čárkou:

  • Podtečení se často vyskytuje u typů s plovoucí čárkou, když je výsledek příliš malý na to, aby byl přesně reprezentován.

  • Např. následující kód vypíše nulu (výsledné číslo se tak bíží nule, až jej nejsme schopni uložit do proměnné typu float).

float x = 1e-30; // 1 * 10^(-30)

x /= 1e20; // 1 * 10^(20)

cout << x;

• • Pokud bychom ale změnili datový typ na double, tak obdržíme očekávaný výsledek 1e-50.

Řešení

• Použití větších nebo přesnějších datových typů:

  • Jedním z řešení může být použití datového typu s větším rozsahem hodnot.

• Pozor na aritmetické operace:

  • Buďte opatrní při provádění operací, které by mohly vést k přetečení nebo podtečení.

• Pro zájemce: https://belaycpp.com/2021/06/08/dealing-with-integer-overflows/