Email byl přidán do databáze

Přihlášení k odběru novinek

Emailem budete informováni v případě publikování nového článku.

Napište mi

Tutoriál jazyka C/C++

Základní pojmy

Vytisknout
-
+

Ještě před tím, než se pustíme do samotného programování, tak bychom se měli podívat trochu hlouběji k vnitřním principům a fungování výpočetních strojů. Pokud se o tuto problematiku alespoň trochu zajímáte, nepřijde Vám toto téma příliš důležité, ale i tak je vhodné pro zopakování. V této kapitole si, na první pohled obskurním způsobem, vysvětlíme základní pojmy, také se podíváme na číselné soustavy a další informace bez kterých se na vyšší úrovni programování již neobejdeme.

Prosím, nelekněte se obsáhlosti článku. Okolo programování je strašně velké množství informací, které jsou důležité. I přes to si zde objasníme pouze takový "vrchol ledovce".
Pochopení principu fungování aritmetiky číselných soustav v této kapitole věnujte zvýšené úsilí, bude se Vám to hodit v následujících lekcích.

Algoritmus

Grafické znázornění Fibonacciho algoritmu<br>zlatý řez

Algoritmus je předem definovaný postup pro řešení nějakého konkrétního problému, který je definovaný pomocí konečného množství kroků. V dnešní době je tento termín výhradně spojen s informačními technologiemi, to však není jediný obor, který algoritmy používá. Vezměme si například kuchařku. Když si prohlédneme libovolný recept, zjistíme že nám popisuje přesný postup, jak dané jídlo připravit a to krok za krokem. Pokud budeme chtít jídlo připravit správně, měli bychom dodržet tento přesný postup, tak jak je napsaný. To samé platí i v informatice, pokud budeme chtít vyřešit nějaký konkrétní problém, vytvoříme si na to co možná nejjednodušší algoritmus.

Základní vlastnosti algoritmů

Pokud vezmeme každý jednotlivý algoritmus a dopodrobna si ho prohlédneme, měli bychom si vždy všimnout pěti vlastností, které musí vždy splňovat:

  1. Konečnost – každý algoritmus musí skončit v konečném počtu kroků. Tento počet může být libovolně velký, avšak vždy musí být konečný. Existují i algoritmy s nejednoznačně definovaným počtem kroků, v tomto případě se jedná se o tzv. výpočetní metody, které nejsou přesným vyjádřením algoritmu.
  2. Obecnost – algoritmus neřeší jeden konkrétní problém, ale snaží se řešit celou škálu obdobných problémů. Například celočíselné dělení dvou libovolných přirozených čísel.
  3. Determinovanost – každý krok algoritmu musí být jednoznačně a přesně definován. Vždy musí být naprosto zřejmé, co a jak se má provádět a co bude dalším krokem. To znamená že pro stejné vstupy vždy dostaneme stejný výstup. Některé algoritmy ale determinované nejsou, jedná se například o různé pravděpodobnostní či heuristické algoritmy, které v sobě mají zahrnutou nějakou náhodu.
  4. Resultativnost – algoritmus nějakým způsobem komunikuje se svým okolím. Tvoří odpověď na vstup. Když algoritmu pošleme vstup, může nám odpovědět různými způsoby. Asi nejzákladnějším způsobem odpovědi je, vrácení výsledku nebo sdělení, že se postup nezdařil.
  5. Elementárnost – algoritmus se skládá z konečného počtu jednoduchých kroků.

Algoritmus se navrhuje několika možnými způsoby:

  1. Shora dolů – postup řešení rozkládáme na jednodušší operace, až dospějeme k elementárním krokům.
  2. Zdola nahoru – z elementárních kroků vytváříme prostředky, které nakonec umožní zvládnout požadovaný problém.
  3. Kombinace obou – obvyklý postup shora dolů doplníme "částečným krokem" zdola nahoru tím, že se například použijí knihovny funkcí, vyšší programovací jazyk, atp...

Druhy algoritmů

Algoritmy můžeme rozdělit na několik důležitých typů:

  1. Rekurzivní – využívají (volají) samy sebe.
  2. Pravděpodobnostní (někdy též probabilistické) - provádějí některá rozhodnutí náhodně či pseudonáhodně.
  3. Paralelní – v případě, že máme k dispozici více počítačů, můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji.
  4. Genetické – pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení.
  5. Heuristické – za cíl si nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení. Používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).

Přitom jeden algoritmus může patřit zároveň do více skupin. Například může být rekurzivní a genetický a paralelní zároveň.

Počítač

Pokud programujeme, měli bychom vědět i nějaké základy fungování výpočetních strojů. Počítač je velmi komplikované zařízení, které zpracovává data pomocí předem vytvořených programů. Jedná se o elektronický stroj skládající se z hardwaru (procesor, klávesnice, …), který představuje jednotlivé fyzické části a softwaru (operační systém a programy), jež simuluje řekněme psychickou část. Počítač je vždy ovládám nějakým vnějším činitelem, který mu poskytuje vstupní data, která jsou pak automaticky zpracována a výsledky počítač prezentuje na výstupních zařízeních, na monitorech tiskárnách a nebo je posílá opět jako vstupy dalšímu počítači v pořadí. V současnosti jsou počítače využívány téměř ve všech oborech lidské činnosti. Zařízení jako jsou notebooky, stolní počítače nebo i chytré telefony jsou dnes řazeny na špici technologického pokroku. Avšak, i když se Vám to možná nebude příliš zdát, počítač dnes již logicky najdeme ve většině nových aut, hodinkách, robotických domácích pomocnících ... novinkou je pro mě například i chytrá žárovka...

Tímto poněkud delším úvodem jsme se konečně dostali přesně tam, kam jsme potřebovali. Podívejme se tedy podrobněji na počítač, který funguje díky elektrické energii. Pro elektrickou energii reprezentující data jsou přípustné pouze dva stavy, tedy vodič je pod napětím – 1 a vodič není pod napětím – 0 (popravdě tento popsaný princip není zcela pravdivý, ale to tady rozebírat nebudeme). Tím získáme dvě základní hodnoty, díky kterým funguje veškerá digitální technologie. Logické stavy 1 - true - yes - on a 0 - false - no - off, ve zkratce Ano/Ne. Mnozí jistě již tuší nebo dokonce vědí, kam se tímto snažím dostat.

Číselné soustavy

Binární soustava

Právě jsme se narazili na úplně nové odvětví matematiky, něž které všichni známe ze základní školy. Nově pro nás totiž bude platit:

1 + 1 = 2      1 + 1 = 10

Pro ty méně znalé, si celou tuto situaci objasníme. Dostali jsem se do dvojkové neboli binární číselné soustavy. Tato soustava se na rozdíl od té naší desítkové ( 1 + 1 = 2 ; 5 + 5 = 10 ), kterou všichni známe, vyznačuje tím, že jí tvoří právě 2 znaky, čili 0 a 1. Například číslo 819 můžeme snadno převést z desítkové do dvojkové soustavy a bude mít podobu: 1100110011. Binární soustava je poziční soustava se základem 2, proto každá číslice odpovídá n-té mocnině čísla dva, kde n je pozice dané číslice v zapsaném binární sekvenci. Pozice počítáme od 0 a počítáme zprava doleva (blíže si to objasníme za chvilku). Dvojková soustava se používá ve všech moderních digitálních počítačích, neboť její dvě číslice (0 a 1) odpovídají dvěma jednoduše rozdělitelným stavům elektrického obvodu (vypnuto a zapnuto), popřípadě nepravdivosti či pravdivosti výroku.

Převod z desítkové do binární soustavy

Celý algoritmus převodu se skládá z několika málo kroků, které stále dokola opakujeme. Předvedeme si ho na našem čísle 819. Ale prvně teoretický princip. Budeme dělit číslo stále dokola dvojkou, dokud se nedostaneme na 1. Vždy nás bude zajímat právě zbytek po celočíselném dělení. U binární soustavy je to jednoduché, pokud číslo vydělíme dvěma a výsledek bude s desetinou částí, zapíšeme si jedničku. Dále vezmeme číslo zaokrouhlené dolu (celou část bez desetinné) a celý postup opakujeme. Když se dostaneme do fáze, kdy bychom měli dělit jedničku dvěma, již dělení neprovádíme a jedničku pouze připisujeme do naší posloupnosti. Na závěr celé binární číslo přepíšeme ve směru od oné poslední jedničky, kterou jsme si připsali (už jsme jí nedělili) až po první číslici kterou jsme si zapsali. A máme číslo převedené do binární soustavy.

Teď znovu a prakticky. Mějme tedy číslo 819 a vydělíme ho dvěma. Vyjde nám 409,5. V čísle máme desetinnou část a zapisujeme si stranou 1. Dále pokračujeme s číslem 409 a dělíme ho dvěma. To je 204,5. Desetinná část, tedy připisujeme si 1. Vydělíme 204 dvěma a máme 102. To je bez desetinné čísti, zapisujeme 0. Dělíme 102 dvěma, 51. Bez desetinné části, čili 0. Vydělíme 51 dvěma dostaneme 25,5. Máme desetinnou část, píšeme 1. Dělíme 25 dostaneme 12,5. Desetinná část, píšeme 1. Dělíme 12, to je 6, píšeme 0. Dělíme 6, to je 3, píšeme 0. Dělíme 3, to je 1,5. Píšeme 1. Teď bychom měli vydělit 1, můžeme tak učinit, vznikne nám 0,5. Tedy zapíšeme si jedna a nadále bychom již pokračovali s 0 a dostávali jenom 0, což nás nezajímá. Jednoduše, když máme dělit jedničku, tak jí opíšeme a končíme. Na závěr celé číslo které jsme se stranou složili přepíšeme od konce a dostaneme 1100110011(2) = 819(10)

Rozpis výpočtu
819/2409,51
204/2204,50
102/21020
51/2511
25/225,51
12/212,50
6/260
3/231
1/201

Převod z binární do desítkové soustavy

Pro převod čísel z dvojkové soustavy do desítkové existuje více metod výpočtu. My se nadále budeme zabývat pouze metodou převodu pomocí mocnin čísla dva. Pro začátek zde vypíši prvních pár mocnin, aby bylo hned jasné, co mám na mysli. Tedy 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096. Jedná se o číselnou řadu tvořenou pomocí matematického zápisu:

$$f(x)=2^{x}, x \in \mathbb{N}_{0}^{+}$$

čili: 20, 21, 22, 23, … (pozor 20 je 1). Nyní máme dostatečné znalosti, abychom zvládli binární číslo převést.

Rozpis výpočtu
10001011
2021222324252627

Budeme tedy převádět číslo 11010001. Ukážeme si tedy nejjednodušší metodu. Přepíšeme převrácené číslo do tabulky a pod každá znak vložíme mocninu dvojky. Mocniny, nad kterými je jednička jednoduše sečteme a vyjde nám výsledné desítkové číslo.

Z tabulky tedy dostáváme součet 20 + 24 + 26 + 27 = 1 + 16 + 64 + 128 = 209

Binární soustava je zvláštní v tom, že zde existují pouze dvě násobnosti tedy násobnost jedničky a nuly. U převodů z a do ostatních soustav je postup velice podobný, ale jsou tam drobné detaily, které si ukážeme dále.

Oktetová soustava

Oktetová soustava funguje přesně na stejném principu jako binární soustava. Jediným rozdílem je, že soustava používá právě osm znaků. Oněmi znaky jsou právě: 0, 1, 2, 3, 4, 5, 6, 7. A to je celý rozdíl.

Co se týče převodu z desítkové soustavy, princip je velice podobný, jenom nás vždy bude zajímat zbytek po celočíselném dělení číslem 8. Zbytek po celočíselném dělení je možná poněkud nový pojem. Ale není to nic složitého. Používali jsme to už na základní škole, když jsme se učili dělit. Dvacet děleno šesti je tři a zbytek dva. Ukážeme si to tedy na krátkém příkladu.

Začneme procvičením celočíselného dělení. Mějme číslo 2 a chceme ho celočíselně vydělit číslem 8. výsledkem je 0 se zbytkem 2. Pro celočíselné dělení čísla 14 číslem osm dostaneme výsledek 1 a zbytek je 6. Právě tyto zbytky jsou jednotlivými ciframi našeho oktetového čísla, které nakonec musíme opět převrátit.

Pokud jde o převod čísla z osmičkové do desítkové soustavy, princip je opět stejný, jenom součet mocnin, tentokrát osmičky, budeme násobit jejich násobností (hodnota).

KAŽDÉ OKTETOVÉ ČÍSLO SE ZAPISUJE VE TVARU 0# (např. 01547), KDE 0 JE PŘEDPONA ČÍSLA URČUJÍCÍ PRÁVĚ TO, ŽE SE JEDNÁ O OSMIČKOVÉ ČÍSLO.

Převod z desítkové do osmičkové soustavy

Převedeme si tedy číslo 275

Rozpis výpočtu
275/8 = 34275 - 34*8 = 33
34/8 = 434 - 4*8 = 22
4/8 = 04 - 8*0 = 44

Dostáváme tedy číslo 0423

Převod z osmičkové do desítkové soustavy

Teď naopak, převedeme si osmičkové číslo do desítkové. Vezmeme číslo 0423.

Rozpis výpočtu
324
808182
1864

Výsledné číslo tedy je 3*80 + 2*81 + 4*82 = 3*1 + 2*8 + 4*64 = 275

Hexadecimální soustava

Další velmi zajímavou a také asi nejpoužívanější soustavou hned po dvojkové a desítkové je právě hexadecimální soustava. Opět funguje na stejném principu, jako všechny soustavy které známe. Je velmi úsporná pro zápis hodnot. Tato soustava se používá například v indexaci paměti, nebo v barevném modelu RBG, kde se pomocí šesti pozic dá vyjádřit až 16 777 216 různých barev. Šestnáctková soustava využívá, jak je z názvu patrné, právě šestnáct znaků.

KAŽDÉ HEXADECIMÁLNÍ ČÍSLO SE ZAPISUJE VE TVARU 0x# (např. 0xFFF), KDE 0x JE PŘEDPONA ČÍSLA URČUJÍCÍ PRÁVĚ TO, ŽE SE JEDNÁ O ŠESTNÁCTKOVÉ ČÍSLO.

Znaky hexadecimální soustavy
0 - 9101112131415
ABCDEF

Znaky na dolním řádku se využívají k zápisu čísel, kdežto váhy se horním řádku se využívají k výpočtům.

Nebudeme zde dlouho otálet a ukážeme si opět převody na krátkém příkladu.

Převod z desítkové do šestnáctkové soustavy

Převedeme si číslo 15 487 do šestnáctkové soustavy. Budeme postupovat přesně stejným postupem, jako u osmičkové soustavy, kde nás bude vždy zajímat zbytek po celočíselném dělení.

Rozpis výpočtu
15487/16 = 96715487 - 967*16 = 1515F
967/16 = 60967 - 60*16 = 777
60/16 = 360 - 3*16 = 1212C
3/16 = 03 - 0*16 = 333

Naším výsledným číslem tedy je 0x3C7F.

Převod z šestnáctkové do desítkové soustavy

V dalším kroku si číslo 0x3C7F převedeme zpět do desítkové soustavy.

Rozpis výpočtu
F7C3
160161162163
1162564096

Výsledné číslo je F*160 + 7*161 + C*162 + 3*163 = 15*1 + 7*16 + 12*256 + 3*4096 = 15487

Tím bychom putování soustavami již opustili a vrhneme se na další zajímavá témata. Je dobré podotknout, že převody mezi touto trojicí soustav (dvojková, desítková, šestnáctková) je vhodné držet v paměti. Ve světě výpočetní techniky a to právě i při programování se s těmito převody poměrně často setkáme.

Binární struktura dat

Bit

Bit (z anglického binary digit - dvojková číslice) je základní a současně nejmenší jednotkou informace. 1 bit reprezentuje informaci, získanou odpovědí na jednu otázku typu ano/ne, u které je pravděpodobnost obou odpovědí stejná (jinými slovy, u které nemáme žádnou předchozí informaci, která by jednu z odpovědí favorizovala). Tyto odpovědi můžeme označit binárními číslicemi 0 a 1. Bit se v praxi nejčastěji objevuje jako základní jednotka kapacity paměti, tzn. jednotka množství informace, která může být v jednom okamžiku v paměti uložena.

Byte

Skupina 8 bitů (tzn. osmiciferné binární číslo) se nazývá Byte. Značí se velkým písmenem B. Jde o jednotku množství dat v informatice. Jeden byte je obvykle nejmenší objem dat, se kterým dokáže počítač (resp. procesor) přímo pracovat. Může reprezentovat 28 = 256 různých hodnot, například celé číslo od 0 do 255 (hexadecimálně 00 až FF) nebo jeden znak.

Reprezentace znaků

Do bytu lze uložit 256 různých hodnot, což bohatě stačí pro rozlišení velkých i malých písmen anglické abecedy včetně číslic a základních interpunkčních znamének. Byte proto zpočátku mohl sloužit pro uložení jednoho znaku textu. Způsob kódování znaku na číselnou hodnotu, kterou bylo možno uložit do bytu, popisoval například kód ASCII. Tento kód však vůbec neobsahuje znaky s diakritickými znaménky používané v jiných jazycích. Rozšířené verze kódu pak přidávají různé znaky užívané v evropských zemích. Postupně vzniklo několik takových kódování, označovaných jako znakové sady, přičemž všechny byly nevyhnutelně vzájemně nekompatibilní. 256 možností je totiž příliš málo pro rozlišení všech znaků používaných v jazycích píšících latinkou, nemluvě o dalších abecedách (jako např. čínština, japonština či korejština).

Z toho důvodu vzniklo více bytové kódování znaků, ve kterých však jeden znak už neodpovídá jednomu bytu. Dnes používaná tabulka znaků Unicode používá nejčastěji dvou až čtyř-bytová kódování s pevnou délkou (tzv. UCS‑2UCS‑4) či kódování s proměnlivou délkou, u kterých různé znaky zabírají různé počty bajtů (UTF‑8UTF‑16). Nadále budeme využívat pouze základní ASCII tabulku znaků.

Endianita

Endianita je v informatice způsob uložení čísel v operační paměti počítače, který definuje, v jakém pořadí se uloží jednotlivé byty číselného datového typu. Jde tedy o to, v jakém pořadí jsou v operační paměti uloženy jednotlivé řády čísel, které zabírají více než jeden byte.

Endianita je jedním ze základních zdrojů nekompatibility při ukládání a výměně dat v digitální podobě. Je nutné brát ji v úvahu při přenášení binárních souborů nebo při síťové komunikaci mezi různými platformami. Tento problém pramení z toho, že stejný zdrojový kód zkompilovaný pro počítače s různými procesory může kvůli jejich různé endianitě produkovat při ukládání nebo přenosu různá binární data. Nejrozšířenějším kódováním vícebytových dat je v současnosti little-endian, což je dané masovým rozšířením architektury Intel x86.

Zdrojem zmatků může být rovněž specifikace IEEE 754, která nedefinuje, v jakém pořadí bajtů se mají ukládat čísla v plovoucí řádové čárce. Endianita může způsobovat problémy i při práci s texty v kódování unicode, proto je rozumné tyto texty ukládat v kódování UTF-8, které je nezávislé na architektuře počítače.

Označení Little Endian a Big Endian pochází z románu Gulliverovy cesty od Jonathana Swifta. V tomto románu se těmito pojmy označovaly dva znepřátelené národy z Liliputu, jež vedly spor o správnosti způsobu rozbíjení vajíček (zdali je rozbíjet z tenkého či tlustého konce).

Little-endian

<b>Little-Endian</b> interpretace paměti pro bezznaménkové číslo <b>2 864 434 397</b> (<b>0xAABBCCDD</b>)

Little Endian označuje způsob ukládání čísel v operační paměti počítače, při kterém je nejméně významný bajt (LSB) na první pozici. Jedná se o nejpoužívanější typ kódování. Hlavním představitelem této technologie je například společnost Intel, inc.

Na obrázku příklad uložení do paměti na adresu 100 pro dekadické bezznaménkové číslo 2 864 434 397 (0xAABBCCDD) metodou little-endian.

Big-endian

<b>Big-Endian</b> interpretace paměti pro bezznaménkové číslo <b>2 864 434 397</b> (<b>0xAABBCCDD</b>)

U Big Endian paměťové místo s nejnižší adresou obsadí nejvíce významný bajt (MSB). Následně se ukládá další bajt až po nejméně významný bajt (LSB). Mezi čipy uplatňující tento model patří například Motorola 68000 nebo produktové řady procesorů založených na technologii RISC.

Na obrázku příklad uložení do paměti na adresu 100 pro dekadické bezznaménkové číslo 2 864 434 397 (0xAABBCCDD) metodou big-endian.

Middle-endian

2 alternativy <b>Middle-Endian</b> interpretace paměti pro bezznaménkové číslo <b>2 864 434 397</b> (<b>0xAABBCCDD</b>)

Některé architektury označované middle-endian (nebo někdy mixed-endian) užívají složitější způsob pro určení pořadí jednotlivých bajtů, který je dán kombinací obou výše zmíněných způsobů. Mezi takovéto architektury patří např. rodina procesorů PDP-11. Tento formát je také použit pro ukládání čísel s pohyblivou řádovou čárkou a dvojitou přesností v systémech VAX a ARM.

Na obrázku 2 alternativní příklady uložení do paměti na adresu 100 pro dekadické bezznaménkové číslo 2 864 434 397 (0xAABBCCDD) metodou middle-endian.

Reprezentace čísel

Pro ukládání, přenos a zpracování záporných binárních čísel v počítači existuje mnoho možností, nejčastěji se používá kódování pomocí dvojkového doplňku.

Přímé kódy

Přímý kód je jednoduchým způsobem vyjádření záporného čísla tak, že je nejvyšší bit vyhrazen znaménku. Tento jednoduchý způsob je však vyvážen nevýhodou komplikovaného algoritmu zpracování čísel a navíc, tento způsob vytváří dvě možné reprezentace čísla 0 (nula). Kladné číslo je na nejvyšším bitu indikováno stavem 0, stavem 1 pak záporné číslo. Ostatní bity pak nesou hodnotu daného čísla. Nejvyšší znaménkový bit je tučně zvýrazněn.

Přímý kód na osmi bitech je možné využít pro kódování čísel z intervalu <-127 ; 127> vč. kladné a záporné nuly.

Bin - přímýDec
000000000
100000000
11111111-127
01111111127
10101001-41
0010100141

Inverzní kódy

Inverzní kód, někdy též jedničkový doplněk, využívá principu přímého kódu pro reprezentaci kladných čísel, naopak záporná čísla se vyjadřují binární negací čísla(záměnou všech 1 za 0 a všech 0 za 1). Podle nejvyššího bitu lze opět poznat znaménko čísla. Nevýhody kódu jsou stejné jako u přímého kódu, např má stále dvě reprezentace čísla nula. Nejvyšší znaménkový bit je tučně zvýrazněn.

Inverzní kód na osmi bitech je možné využít pro kódování čísel z intervalu <-127 ; 127> vč. kladné a záporné nuly.

Bin - inverzníDec
000000000
111111110
10000000-127
01111111127
10101001-86
0101011086
0010100141
11010110-41

Doplňkové kódy

Doplňkový kód slouží pro zápis záporných čísel, kladná zůstávají nezměněná. Stejně jako v přímém a inverzním kódu slouží 1 na nejvyšším bitu pro identifikaci záporného čísla. Výhodou této reprezentace je, že existuje pouze jeden tvar pro reprezentaci nuly (v přímém je i záporná nula, např. 10000000), nevýhodou je naopak fakt, že zobrazený interval je nesymetrický (např. -128127 v případě osmibitových čísel nebo -3276832767 v případě šestnáctibitových)

Doplňkový kód na osmi bitech je možné využít pro kódování čísel z intervalu <-128 ; 127>.

Postup kódování již není stejně triviální jako například u přímého kódu a je rozdělen do dvou kroků. Pokud má číslo na nejvyšším znaménkovém bitu hodnotu 0, potom se s číslem nic zvláštního neprovádí a je rovnou převedeno do desítkové reprezentace. Naopak pokud znaménkový bit obsahuje jedničku, výpočet se malinko komplikuje. V prvním kroku je s takovým čísel potřeba zacházet jako s inverzním kódem, tedy celé číslo binárně znegujeme. Tímto bychom si ostatně ale moc nepomohli, proto je dále potřeba k číslu přičíst na nejnižším bitu ještě jedničku. Výsledkem je číslo, které nám signalizuje absolutní hodnotu našeho záporného čísla a nám již stačí před číslo přidat mínus, ostatně původně začínalo jednotkou.

Bin - doplňkovýDec
01111111127
01111110126
0101011187
0010101042
000000102
000000011
000000000
11111111-1
11010110-42
10101001-87
10000010-126
10000001-127
10000000-128

Aditivní kódy

Aditivní kód, též kód s posunutou nulou, nemá přímo vyhrazený bit pro znaménko a pracuje na principu posunutí nuly, tedy k binárně kódované hodnotě je při dekódování přičítána známá hodnota odpovídající polovině možných kombinací vyjádřených na daném počtu bitů, například na 8 bitech je tato hodnota 128 (2^8/2), při tomto kódování nejvyšší bit vyjadřuje kladné číslo stavem 1 na nejvyšším bitu, stavem 0 pak záporné číslo, odstraňuje možnost dvojitého zobrazování nuly jako kladné i záporné. Tento kód se běžně používá pro exponent v reprezentaci desetinných čísel pomocí pohyblivé řádové čárky.

Výpočet není nijak složitý, navíc existuje několik obdobných způsobů výpočtu. Nás bude zajímat právě ten s přičítáním poloviny intervalu (128). Aditivní kódování na osmi bitech je možné využít pro kódování čísel z intervalu <-128 ; 127>. Pokud číslo převádíme do binární podoby, přičteme k jeho dekadické reprezentaci právě polovinu intervalu (128) a výsledek převedeme do binární podoby. Naopak, pokud číslo převádíme z aditivního kódu, číslo převedeme do dekadické podoby a odečteme od něj onu polovinu intervalu (128).

Bin - aditivníDec
11111111127
1101011187
100000011
100000000
01111111-1
00101001-87
00000000-128

Základní aritmetické operace

Sčítání

Přímé kódy

Sčítání je velice triviální, ukážeme si to na příkladu, jen pozor na přenos a přetečení. Pokud nastane přenos (1+1=0 & přenos, alternativou je že v předchozím kroce nastal přenos a nyní tedy: 1+1+přenos=1 & nový přenos), je bezpodmínečně nutné ho zachytit ve vyšším bitu.

Touto metodou lze sčítat pouze dvě kladná čísla..

5+4≠-1 | 298+726=1024 | 999740367+1003682284=2003422651 ------------------------------------------------------------------------- 0101 | 0001 0010 1010 | 00111011 10010110 11010011 11001111 +0100 | +0010 1101 0110 | +00111011 11010010 11111001 11101100 ------- | ----------------- | --------------------------------------- 1001 | 0100 0000 0000 | 01110111 01101001 11001101 10111011 FAIL - došlo ke změně znaménka | 2. a 3. příklad správně

Pokud dojde k přenosu do znaménkového bitu, došlo k přetečení a výsledek je neplatný.
pracujeme-li na 8 bitech, potom 64 + 64 = -128, což je principielně správně, avšak matematicky nikoliv. Tudíž, když dojde při sčítání kladných čísel v přímém kódu k přenosu do znaménkového bitu je výsledek neplatný a je zahozen.

Doplňkové kódy

Sčítat je možné i v doplňkovém kódu. Výsledek pak bude na stejném počtu bitů jako vstup, i když by přenos způsobil přetečení. Pro detekci přetečení se používá XOR dvou nejlevějších bitů přenosu - pokud vyjde XOR 1, jde o chybu. Z toho plyne, že buď musí přenos nastat do nejvyššího bitu a zároveň musí dojít k přetečení, nebo nesmí dojít ani k přetečení ani k přenosu do nejvyššího (znaménkového) bitu, potom je výsledek správný.

Touto metodou lze sčítat pouze dvě kladná čísla..

7+1≠-8 | 68+59=127 | 23446+15314≠-26776 | 9581+23186=32767 ---------------------------------------------------------------------------- 0111 | 0100 0100 | 01011011 10010110 | 00100101 01101101 +0001 | +0011 1011 | +00111011 11010010 | +01011010 10010010 ------- | ------------ | -------------------- | -------------------- 1000 | 0111 1111 | 10010111 01101000 | 01111111 11111111 FAIL Správně FAIL | Správně

Odčítání

Podobné jako sčítání je i odčítání, ale pokud od 0 odečteme 1, výsledek je 1 a musíme odečíst 1 (vypůjčit si) i ze sloupečku vlevo.

Přímé kódy

Odčítání v přímém kódu je poměrně komplikované a proto si ho zde shrneme jen velice rychle. Můžeme odčítat pouze menší číslo od většího (nebo stejné), při odčítání si musíme hrát se znaménky a přizpůsobovat si tím výpočty. Například bez problému odečteme 2 kladná čísla, pokud budeme chtít sečíst kladné a záporné číslo, převedeme si to na odčítání. Nebudeme to zde složitě popisovat a ukážeme si pár základních příkladů.

7 7-1=6 | 8--5=13 | -60-30=-120 | 16-32=-16 ------------------------------------------------------- 0111 | 01000 | 00111100 | 00100000 -0001 | (-10101) | +00011110 | -00010000 ------- | +00101 | ----------- | ----------- 0110 | -------- | 01011010 | 00010000 | 01101 | 11011010 | 10010000

Jak si lze z příkladů všimnout, aritmetika v rámci přímého kódování je velmi komplikovaná, každý případ musí ošetřit jiný algoritmus, z toho důvodu dnes není téměř využívána.

Doplňkové kódy

V doplňkovém kódu se čísla normálně jednoduše sečtou.

9-5=4 | -4-4=-8 | -32+32=0 | -1+16=15 | 5-8=10 | -11-6≠15 -------------------------------------------------------------------------------------------------- 01001 | 11100 | 11100000 | 11111111 | 00101 | 10101 +11011 | +11100 | +00100000 | +00010000 | +11000 | +11010 Přenos: 11011 | 11100 | 11100000 | 11110000 | 00000 | 10000 -------- | -------- | ----------- | ----------- | -------- | -------- 00100 | 11000 | 00000000 | 00001111 | 11101 | 01111

Násobení

Násobení si ukážeme pouze obecně na krátkém příkladu. Násobení binárních čísel je na chlup stejné jako násobení dekadických čísel. Čili roznásobíme pod sebe, tak jak jsme zvyklí (máme tu výhodu že násobíme pouze 1 a 0, tedy buď první řádek opíšeme nebo dáme samé nuly) a následně pod sebou sečteme. POZOR: u větších binárních čísel bývá obtížné při sčítání si z hlavy pamatovat přenosy, když jich tam může být hned několik najednou viz 2. příklad

Pro zájemce existuje i Boothův algoritmus[11], který umí násobit i binární čísla v dvojkovém doplňku viz odkazy po článkem.

1001 11010110 ×1010 ×10110110 --------- ------------------ 0000 00000000 1001 11010110 0000 11010110 1001 00000000 --------- 11010110 1011010 11010110 00000000 11010110 ------------------ 1001100000100100

Reprezentace desetinných čísel

Na úvod bude vhodné říci, že binární číslo pro aritmetické účely není jedinou možnou podobou. Další formy symbolizují počítače a jejich způsoby ukládání binárních dat pro své vlastní účely.

Začneme obecně převodem čísla v desítkové soustavě pro další matematické využití. Konkrétně půjde o 10,62510. Oddělíme přitom od sebe celou a desetinnou část. Nyní se budeme věnovat pouze desetinné části 0,62510.

  • Mohu od 0,625 odečíst 1/2 bez toho, aby se dostal do záporných hodnot? ANO, učiním tak.
  • Mohu od 0,125 odečíst 1/4 bez toho, aby se dostal do záporných hodnot? NE
  • Vezměme opět 0,125. Mohu odečíst 1/8 bez toho, abych se dostal do záporných hodnot? ANO, učiním tak.
  • Zbývá nula, a proto převod končí. Pokud by se tak nestalo, pokračovali bychom dále s 1/16, 1/32, 1/64

Nyní nahradíme všechny odpovědi ANO jedničkou a tvrzení NE nulou. Výsledek zapisujeme směrem od horního údaje dolů. Získáváme tedy 1012. Přidáme-li 1010 v binární soustavě jako 10102, máme výsledek v podobě 1010,1012.

Nyní přichází na řadu reprezentace pro hardware počítače. Lze se vydat celkem dvěma cestami – pevnou nebo plovoucí desetinnou čárkou.

Pevná řádová čárka

Transformace do podoby s proměnlivou řadovou čárkou se řadí mezi složitější operace. V tomto zobrazení definujeme místa před a místa za řádovou čárkou. Dnes už se pro desetinná čísla téměř nepoužívá. Na klasická celá čísla se dá pohlížet jako na čísla s pevnou řádovou čárkou a 0 místy za čárkou.

Pro ukázku zkusíme reprezentovat číslo 10,625 pomocí pevné řádové čárky. Nejprve si zvolíme počet míst za celou částí čísla, jenž budeme uchovávat. V našem případě půjde o 3. Dále musíme znát základ soustavy, do které převádíme, tedy 2. Provedeme jednoduchý výpočet 23 a tímto mezivýsledkem vynásobíme vstupní číslo, -10,62510 (povšimněte si přidaného znamínka mínus, jenž nám zajistí zajímavější postup). Pochopitelně -10,625 x 8 = -85. Z tohoto dalšího mezivýsledku oddělíme celou část (tedy -85) a tu následně převedeme do binární podoby. Využít můžeme například doplňkový kód – 101010112.

Pohyblivá řádová čárka

Při použití pohyblivé řádové čárky se číslo definuje jako:

X YYYYYYYY ZZZZZZZZZZZZZZZZZZZZZZZ

X je znaménkový bit (1 znamená záporné), Y je exponent a Z je tzv. mantisa, která je desetinnou částí zlomku. Výsledné číslo se získá jako:

(-1)X * 2(exponent v kódu posunuté nuly) * (1.Z)

Existují některé speciální stavy:

  • e = 0, f = 0 → číslo = 0
  • e = max, f = 0 → číslo = nekonečno
  • e = max, f <> 0 → číslo = NaN (not a number)

Příklad: Máme reprezentaci pomocí čtyř bitů exponentu a osmi bitů mantisy. Chceme vyjádřit číslo -10,8. Nejdřív z tohoto čísla vyhodíme zápor a pak vyhaxujeme exponent, tedy vydělíme ho takovou mocninou 2, aby vzniklo číslo v rozsahu <1,2). 10,8/8 = 1,35. Odsekneme 1. (protože počítáme s tím, že tam vždycky je), takže nám jako mantisa vyjde 35. Výsledné číslo v této reprezentaci bude vypadat tedy takto:

1 1000 00100011 (znaménko exponent mantisa).

Pro zájemce, kteří by také chtěli vědět, jak přesně počítač pracuje s desetinnými čísli, mohou využít dole v odkazech tutorial[11], který se této problematice poměrně dopodrobna věnuje.

Seznam domácích úloh

  1. Převeďte tato čísla do dvojkové soustavy: 1, 45, 265.
  2. Převeďte tato čísla z dvojkové soustavy do desítkové: 1011012, 10100111012, 10101011012, 10102.
  3. Převeďte tato čísla do šestnáctkové soustavy: 5, 12, 26526.
  4. Převeďte tato čísla z šestnáctkové do desítkové soustavy: 0xABBA, 0xBABA, 0x1234567890ABCDEF.
  5. Převeďte tato čísla z dvojkové soustavy do šestnáctkové a osmičkové: 1011012, 10100111012, 10101011012, 10102.
  6. Převeďte tato čísla do osmičkové soustavy: 45, 8.
  7. Převeďte tato čísla z osmičkové do šestnáctkové a desítkové soustavy: 075, 045.
  8. Jaká je hodnota osmičkového čísla 078?
  9. Předpokládejme reprezentaci celých čísel se znaménkem pomocí osmi bitů. V přímém kódu reprezentujte čísla -50, -1, 0, 50 a číslo 200. Vzniklé kódy převeďte zpět do desítkové soustavy. Diskutujte reprezentaci hodnot 20, 200 a 2000.
  10. Jak se změní výsledky předchozího příkladu při použití 16 bitů?
  11. Předpokládejme reprezentaci celých čísel se znaménkem pomocí osmi bitů. V přímém kódu vypočítejte 20 + 12, -66 + -96. Výsledek převeďte do desítkové soustavy.
  12. Jak se změní výsledky předchozího příkladu při použití 16 bitů?
  13. Předpokládejme reprezentaci celých čísel se znaménkem pomocí osmi bitů. V doplňkovém kódu reprezentujte čísla -50, -1, 0, 50 a číslo 200. Vzniklé kódy převeďte zpět do desítkové soustavy. Diskutujte reprezentaci hodnot 20, 200 a 2000.
  14. Jak se změní výsledky předchozího příkladu při použití 16 bitů?
  15. Předpokládejme reprezentaci celých čísel se znaménkem pomocí osmi bitů. V doplňkovém kódu vypočítejte 20 + 12, -66 + -96. Výsledek převeďte do desítkové soustavy.
  16. Jak se změní výsledky předchozího příkladu při použití 16 bitů?
  17. Vynásobte binárně čísla 100×100, 1001×1101, 10001×10101, 10101010×10101010, 11111111×11111111 (neuvažujeme znaménkový bit).
  18. Převeďte desetinná čísla do binární reprezentace: 5.5, 18.515625, 31.96875, 32.015625, 3.1415926535, -10.5, -28.25 (uvažujme obecnou definici - celá část doplňkovým kódem, desetiná formou podílových mocnin)
Pokud budete chtít Vaše odpovědi zkontrolovat, neváhejte a zašlete mi je emailem.

Závěr

V další kapitole se podíváme na vývojová prostředí IDE, popíšeme si jejich funkce a připravíme si prostředí pro to abychom se konečně mohly vrhnout do světa jazyka C/C++, vlastně z počátku pouze do světa jazyka C. Jsem zastáncem názoru, že by programátor měl být schopen rozlišovat jazyk C a jeho nadstavbu C++. Ještě než tento díl skončím, dovolte mi v několika málo větách tento názor objasnit a obhájit.

Představte si, že vyhrajete zakázku na tvorbu programu pro kosmickou agenturu SpaceX, která vyžaduje, aby dodané kódy byly pokud možno bezchybné a co nejefektivnější. Právě této vysoké efektivity dosáhneme použitím čistého jazyka C, kdežto kdybychom použili jazyk C++, který má již mnoho funkcí (objektů, metod) předdefinovaných i s všelijakým, pro nás třeba nepotřebným, balastem tak by s největší pravděpodobností kód obsahoval i segmenty, které jsou pro projekt absolutně zbytečné a vykonávání kódu jenom zdržují.

Ať Vám každý říká co chce, pravda je jen jedna. Kód musí být efektivní. I pouze minimální prodleva nějaké zásadní často volané funkce, trvající byť 1 milisekundu, nám v konečném součtu může způsobit, že celé zpracování dat o objemu např 30 TiB se může protáhnout až o několik hodin a v horších případech i několik dní až měsíců.