Česky 
EnglishInformation
I wrote this text when I was in the second degree of The Secondary technical school in Liberec (SPŠSE), I was fascinated by programming in assembler and I missed a good book on Czech market, which teaches everything simply from beginning. I learned the basics of assembler in an optional subject on my basic school and I wanted to pass on my knowledge to other people. I had a lot of free time, so I decided (in a spirit of plenty of tutorials which you can find on internet) to make my own tutorial. Available to everyone for free. In the same way as I have learned a lot of things on internet from another people for free. But after some time it stopped be interesting for me so I did not write neither one assembler instruction in my tutorial, only the basics of number bases, calculating with them and boolean algebra :-)
I will be happy if even in this time this tutorial is useful for somebody as an introduction into the digital systems's theory. The only problem is that it is in Czech language and I do not plan to translate it.
^Tutorial
Sorry, in Czech language only.
T A S M T U T O R I A L 1 . 0
Tomáš Bořil 2001
borilt@gmail.com
OBSAH
1. Základy všeobecných programátorských znalostí
1.1. Číselné soustavy
1.1.1. Převod z libovolné soustavy do desítkové
1.1.2. Převod z desítkové soustavy do libovolné
1.1.3. Převod z libovolné soustavy do libovolné
1.1.4. Aritmetické operace s čísly
1.1.4.1. Sčítání
1.1.4.2. Odčítání
1.1.4.3. Násobení
1.1.4.4. Dělení
1.1.5. Bit, byte, word a další cizí slova
1.2. Booleova algebra
1.2.1. Základní funkce
1.2.2. Použití základních funkcí
1.2.3. Základní pravidla Booleovy algebry
... nedokončeno ...
1. Základy všeobecných programátorských znalostí Tak vy se chcete učit v assembleru? No dobře, nejdřív ale, než sednete k počítači a uděláte si svůj první program, musím vás naučit nějaké základní teoretické znalosti. Neříkám, že úplně všechny potom při programování využijete, ale je dobré vědět, jak to vlastně všechno funguje. Vyplatí se věnovat jim ten čas a opravdu to pořádně pochopit. Nejdříve vám prozradím (pokud už to ze školy nevíte), že ne vždy se počítá v desítkové soustavě, kde máme k dispozici znaky 0-9 (tedy počet peněz do 9 zapisujeme jednou číslicí, do 99 dvěma, do 999 třemi atd.). Třeba zrovna počítač zná uvnitř ve svých obvodech jen 0 a 1 a tak všechna čísla převádí na shluky těchto jedniček a nul. No, a pak vás naučím s těmi soustavami počítat. Až to pochopíte, nebude pro vás později problém si s počítačem popovídat :-) Je to hodně textu, proto moc nespěchejte a dokud nepochopíte úplně jasně jednu kapitolu, nechoďte na další. Když vám nebude něco jasného, zkuste si to přečíst ještě jednou, ty příklady si sami zkuste udělat na papír, tak to nejlépe pochopíte. Až si to vytrpíte, tak se už vrhneme na to programování.
1.1. Číselné soustavy Pro nás je nejběžnější desítková soustava, neboť ji používáme již od 1. třídy. Pro zapsání čísla používáme znaky 0 - 9 a záleží, na jaké pozici se v zápisu nachází. Tuto pozici označujeme jako řád (tedy řád jednotek, desítek, stovek, ale také desetin, setin, tisícin...). Tento druh zápisu nazýváme 'poziční číselný systém'. Naproti tomu existuje např. římský způsob zápisu čísel. Vedle desítkové soustavy existuje nekonečně mnoho jiných soustav (dvojková, trojková...). Obecně n-ková. Pro n-kovou číselnou soustavu při pozičním číselném zápisu je potřeba 'n' různých znaků. Počítače pracují ve dvojkové soustavě (tzv. binární), která má dva stavy, 0 a 1. Je to pro něj výhodné, protože přiřadí stavu 0 napětí např. 0V a stavu 1 5V a tak je odolný proti rušení. Když tam bude 4.5V nebo 5.5V bude to furt 1. Kdyby počítače používali desítkovou soustavu, bylo by potřeba udělat deset napěťových úrovní a tak by se hranice mezi jednotlivými stavy podstatně zúžily a systém by byl náchylnější k chybám (ono už takto docela stačí, že jsou chyby v softwaru ;-) Pro programování v assembleru budeme potřebovat umět dvojkovou soustavu, neboť je nutná pro pochopení a používání některých záležitostí a bude se nám také hodit soustava šestnáctková (tzv. hexadecimální), protože je blízká soustavě binární a zápis je hezčí (1895h se pamatuje lépe než 1010110011000b.) Tak to byl takový hezký úvod, nyní si ukážeme, jak se mezi jednotlivými soustavami čísla převádějí a jak se s nimi pracuje. Dvojková (binární) soustava je jednoduchá - máme jen čísla 0 a 1. V šestnáctkové soustavě je 16 znaků - 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Přičemž 0-9 mají normální hodnotu a A-F mají hodnoty 10-15. V programech v assembleru se čísla ve dvojkové soustavě odlišují od čísel v desítkové tím, že se za ně napíše písmeno 'b', jako binární (např. 101b). Za šestnáctková čísla se píše 'h', jako hexadecimální. V případě, že by číslo začínalo písmenkem, napíšeme před něj ještě '0', aby se to odlišilo od názvu nějaké proměnné nebo instrukce. Tedy např. 0BAFh znamená BAF v šestnáctkové.
1.1.1. Převod z libovolné soustavy do desítkové
Jak tento převod funguje si vysvětlíme na převodu z desítkové do desítkové
(srandovní, že? - ale na tom se to nejlíp pochopí, fakt!)
Zkusíme si převést například číslo 917.56. Základ soustavy z = 10
*z^2 *z^1 *z^0 | *z^-1 *z^-2 -\
*10^2 *10^1 *10^0| *10^-1 *10^-2 > řády
*100 *10 *1 | *0.1 *0.01 -/
|
9 1 7 . 5 6 - hodnoty řádů (číslice)
= = = = =
900 + 10 + 7 + .5 + .06 = 917.56
Takže to funguje. Prostě první řád (nalevo od des. tečky) má hodnotu 1,
řády směrem doleva vždy násobíme základem (1, 10, 100, 1000...) a směrem
doprava dělíme základem (0.1, 0.01, 0.001...). Danou číslici vynásobíme daným
řádem a tyto výsledky sečteme. Předchozí příklad by se dal zapsat také jako
9*100 + 1*10 + 7*1 + 5*0.1 + 6*0.01 = 917.56
Nyní zkusme převést číslo 1101.10111 z dvojkové do desítkové (tedy z=2).
*z^3 *z^2 *z^1 *z^0 | *z^-1 *z^-2 *z^-3 *z^-4 *z^-5
*2^3 *2^2 *2^1 *2^0 | *2^-1 *2^-2 *2^-3 *2^-4 *2^-5
*8 *4 *2 *1 | *0.5 *0.25 *0.125 *0.0625 *0.03125
|
1 1 0 1 . 1 0 1 1 1
= = = = = = = = =
8 + 4 + 0 + 1 + 0.5 + 0 + 0.125 + 0.0625 + 0.03125
= 13.71875
A ještě jeden příklad nakonec. Číslo -2BC.D z šestnáctkové do desítkové.
Znaménko '-' znamená stejně jako v desítkové číslo záporné. Připomeňme, že
B = 11, C = 12 a D = 13.
*z^2 *z^1 *z^0 | *z^-1
*16^2 *16^1 *16^0| *16^-1
*256 *16 *1 | *0.0625
|
- 2 B C . D
= = = =
- ( 512 + 176 + 12 + 0.8125 ) = -700.8125
Všimněte si, že čím má soustava větší základ, tím je potřeba kratší zápis
čísla. Další důležitou vlastností je to, že součin cifra*řád nemůže být
nalevo nikdy menší než u cifer směrem doprava, kromě případu, že by cifra
byla 0. Například v tomto příkladu 512 > 176 > 12 > 0.8125
Ještě vám dám pár příkladů, abyste si to vyzkoušeli. V hranatých závorkách
je správný výsledek.
1) z dvojkové do desítkové:
11111111 [255] 100000000 [256] -101.1 [-5.5]
2) z trojkové do desítkové:
-210 [-21] 1.102 [1.407...] - vidíte, že čísla v jedné soustavě
neperiodická mohou být v jiné periodická
3) z šestnáctkové do desítkové:
BAF [2991] 123 [291] -EE.A [-238.625]
Vyšlo vám to všechno? No tak bezva, běžte se proběhnout, projet na kole, ať
mně z toho hned po první kapitole nezblbnete. Ať se ty nově nabyté informace
hezky uleží... Zítra vás naučím převádět tato čísla v desítkové soustavě
zpátky do jiných soustav.
1.1.2. Převod z desítkové soustavy do libovolné
Dané číslo v desítkové soustavě si rozdělíme na celou část (před des.
tečkou) a na desetinou část (za des. tečkou).
Celou část převádíme tak, že desítkové číslo dělíme základem cílové
soustavy a zbytky zapisujeme zprava do leva.
Pak uděláme vpravo desetinnou tečku a převádíme desetinnou část tak, že
desítkové desetinné číslo násobíme základem a co přeleze přes desetinnou
tečku zapíšeme směrem zleva do prava za des. tečku. To, co přelezlo,
uříznem. Když nic nepřelezlo, zapíšem jednoduše jako '0'.
Tak jsem to vysvětlil jak nějakému řezníkovi, ale nechtělo se mi vymýšlet
žádné matematické definice. Celý postup si zase nejdříve ukážeme na převodu
z desítkové do desítkové (vidíte, teď je to naopak než v předchozí
podkapitole :-)
Zkusme zase číslo 917.56, základ cílové soustavy je z = 10.
Celá část: 917
917 : z (10) = 91, zbytek 7 - píšeme 7
_____________|
\|/
91 : 10 = 9, zbytek 1 - nalevo od 7 píšeme 1, máme tedy již 17
9 : 10 = 0, zbytek 9 - teď už máme 917
mohli bychom pokračovat dále, ale 000000917 = 917, takže toho necháme ;-]
Desetinná část: 0.56
Ještě to jednou radši zopakuju: násobíme *z (tedy *10), co přeleze, uříznem
a zapíšem.
0.56 * z (10) = 5.6 - přelezlo 5, zapíšem napravo od '.', máme už 971.5
0.6 * 10 = 6.0 - přelezlo 6, zapíšem napravo 6, máme 971.56
už není co násobit, končíme (971.5600000 = 971.56)
Takže to zase funguje (jinak bych to tady ani nepsal ;-> Ještě dám radši
jeden jednoduchej příklad (10 -> 10), aby bylo vidět, jak se to dělá, když
nic nepřeleze:
0.403 * 10 = 4.03 - přelezlo 4, uříznem a zapíšem 0.4
0.03 * 10 = 0.3 - nic nepřelezlo, ale je tam '0', takže píšem 0.40
(0.43 není 0.403)
0.3 * 10 = 3 - přelezlo 3, a je to vše -> 0.403
Tak to bylo triviální, zkusme tedy již něco naostro. Třeba zase to naše
číslo 13.71875 (viz minulá podkapitola) převedeme do dvojkové soustavy. Mělo
by vyjít 1101.10111 (jestli jsme to před tím spočítali dobře).
Takže, celá čast: 13
13 / 2 = 6, zbytek 1 - zapíšem 1
6 / 2 = 3, zbytek 0 - zapášem vlevo 0, máme 01.
3 / 2 = 1, zbytek 1 - zapíšem vlevo 1, máme 101.
1 / 2 = 0, zbytek 1 - zapíšem vlevo 1, máme 1101.
a už není co dělit...
desetinná část: 0.71875
0.71875 * 2 = 1.4375, přelezlo 1 - napíšem napravo 1, tedy 1101.1
0.4375 * 2 = 0.875, nic nepřelezlo - napíšem 0, tedy 1101.10
0.875 * 2 = 1.75, přelezlo 1 - napíšem 1, tedy 1101.101
0.75 * 2 = 1.5, přelezlo 1 - napíšem 1, tedy 1101.1011
0.5 * 2 = 1, přelezlo 1 - napíšem 1, tedy 1101.10111
a je to, vyšlo 1101.10111 - funguje, hurá!
A ještě jeden příklad, 13.71875 do šestnáctkové.
Celá část: 13
13 / 16 = 0, zbytek 13 - zapíšem D
tak to byla rychlovka
Desetinná část:
0.71875 * 16 = 11.5, přelezlo 11 - napíšem B, máme tedy D.B
0.5 * 16 = 8, přelezlo 8 - napíšem 8, máme D.B8
a je to vše.
Při převodech opět nezapomeňte, že číslo v jedné soustavě úplně krásně
normální může vyjít v jiné periodicky (tedy pokud už to bude trvat nějak
moc dlouho, nechte toho, protože byste tu mohli být do zítra :-)
Jiná metoda převádění z desítkové do jiné soustavy je ta, že si nakreslíte
dostatečně veliký počet řádů, potom vezmete číslo a zkoušíte, kolikrát se
vejde řád do toho čísla. To zapíšete do daného "chlívku" a zbytek zkusíte
o řád níž. A tak dále.
Např. 68 do binární soustavy:
256 128 64 32 16 8 4 2 1
^ ^ ^ ^ ^ ^ ^ ^ ^
68/256 = 0 --------------------| | | | | | | | |
68/128 = 0 ------------------------| | | | | | | |
68/64 = 1 ----------------------------- | | | | | |
4/32 = 0 -------------------------------- | | | | |
4/16 = 0 ----------------------------------- | | | |
4/8 = 0 ------------------------------------- | | |
4/4 = 1 --------------------------------------- | |
0/2 = 0 ----------------------------------------- |
0/1 = 0 -------------------------------------------
výsledek: 1000100b
Pro desetinná čísla je potřeba přidat chlívky desetinné (0.5, 0.25...)
Tak to je jenom tak pro úplnost, vyberte si sami, co je pro vás lepší. (No
lepší je samozřejmě ten první způsob, protože se nepřemýšlí nad tím, kolik
je potřeba řádů, ale zase tady ten druhý způsob se snadněji zapamatuje).
Příklady:
1) zkuste si všechny příklady z minulé podkapitoly převést v opačném směru,
tedy z desítkové do té dané soustavy, jestli to vyjde.
2) jestli vás to bude ještě bavit, vymýšlejte si libovolná další čísla
a zkuste si je převádět do libovolné soustavy a pak zase zpátky do
desítkové. Když už teď umíte převádět obousměrně, můžete si takto
sami zkontrolovat, jestli to vyšlo dobře.
3) Spočítejte 19994h - BABAh (výsledek chci opět hexadecimálně)
Návod: čísla převeďte do desítkové soustavy, odečtěte a pak převeďte
zpátky do šestnáctkové. Tady u toho vám výsledek dopředu neřeknu, protože
byste se již potom nepobavili...
1.1.3. Převod z libovolné soustavy do libovolné
No tak obecně je nejjednodušší převést to číslo z té soustavy do desítkové
a pak z desítkové do cílové soustavy.
Např. 1011 z dvojkové do trojkové:
1011b = 1*1 + 1*2 + 1*8 = 1+2+8 = 11 v desítkové
11/3 = 3, zbytek 2
3/3 = 1, zbytek 0
1/3 = 0, zbytek 1
Výsledek je 102.
Mnohem jednodušší je převádět z dvojkové do šestnáctkové a naopak.
Číslo ve dvojkové soustavě si rozdělíte na skupiny po čtyřech (zprava doleva)
a ty potom jednotlivě převedete do šestnáctkových (vždy tedy vyjde jeden
znak). Převod ze šestnáctkové soustavy do dvojkové se provádí naopak -
jednotlivé cifry rozepíšete na čtveřice dvojkových číslic.
Např. číslo 1011110110101010101 do hexa a pak naopak:
0101|1110|1101|0101|0101
\ | | / /
5 E D 5 5
5ED55
____/_/ | \ \_____
/ / | \ \
101|1110|1101|0101|0101
Podobně jednoduchý je převod dvojková - osmičková (skupiny po třech)
a dvojková - čtyřková (skupiny po dvou).
Příklady:
1) Tak si zkuste vymyslet něco sami, nějaké číslo "v bináru" převeďte
nejdříve standardně: do desítkové -> do šestnáctkové, pak naopak:
do desítkové -> do dvojkové. No, a teď zkuste udělat to samé tou
fintou přes skupiny po čtyřech. Vidíte, jak je to rychlejší. Právě
proto se v assembleru často místo dvojkových čísel píšou v hexa
- je to kratší a lépe se to pamatuje, navíc je otázkou pouze chvilky
převést si to.
1.1.4. Aritmetické operace s čísly
Stejně jako v desítkové soustavě můžeme počítat i v jiných soustavách.
Princip je vždy stejný.
1.1.4.1. Sčítání
Připomeňme si, jak se počítá písemně v desítkové soustavě. Čísla napíšeme
pod sebe (desetinné tečky přesně pod sebe) a jedem - zprava doleva. Sečteme
vždy příslušné dvě cifry. Pokud nám vyjde dvojciferný výsledek, tak zapíšem
jen tu poslední cifru a tu cifru, kterou nezapisujem, přičteme k cifrám
nalevo. Ukažme si to na příkladu 456.21 + 73.68
456.21
73.68
______
529.89
||| |\__ 1 + 8 = 9, nic přenášíme
||| \___ 2 + 6 = 8, nic přenášíme
||\_____ 3 + 6 = 9, nic přenášíme
|\______ 7 + 5 = 12, zapíšeme 2, přeneseme 1
\_______ 4 + 0 + přenos 1 = 5
Tak teď jsme si to zopakovali, zkusme to aplikovat na dvojkovou soustavu.
Pro sčítání si můžeme jednotlivé cifry převést do desítkové soustavy (to ale
uplatníme až u šestnáctkové soustavy), ale hlavně výsledný součet cifer
musíme zapsat v dané soustavě (tady ve dvojkové), abychom mohli oddělit
správně přenos. Když tedy budeme sčítat 1 + 1 = 2, ale v dvojkové soustavě to
je 10. Zapíšeme tedy 0 a přenos je 1. Když nastane situace 1 + 1 + 1 = 3,
v bináru to je 11, zapíšeme 1 a přenos je 1. Když bychom sčítali třeba 5
čísel najednou, může třeba nastat 1 + 1 + 1 + 1 = 4, v bináru 100 -> zapíšem
0 a přenos bude 10 dvojkově, desítkově 2.
Zkusme takovýto příklad: sečtěte ve dvojkové soustavě 111010.11 + 10011.101
111010.11
10011.101
___________
1001110.011
||||||| ||\__ 0 + 1 = 1, nic přenášíme
||||||| |\___ 1 + 0 = 1, nic přenášíme
||||||| \____ 1 + 1 = 10, zapíšeme 0, přeneseme 1
||||||\______ 0 + 1 + přenos 1 = 10, zapíšeme 0, přeneseme 1
|||||\_______ 1 + 1 + přenos 1 = 11, zapíšeme 1, přeneseme 1
||||\________ 0 + 0 + přenos 1 = 1, nic přenášíme
|||\_________ 1 + 0 = 1, nic přenášíme
||\__________ 1 + 1 = 10, zapíšeme 0, přeneseme 1
|\___________ 1 + 0 + přenos 1 = 10, zapíšeme 0, přeneseme 1
\____________ 0 + 0 + přenos 1 = 1, nic nepřenášíme
Zkusme sečíst čísla v šestnáctkové soustavě D19 + FF2
D19
FF2
___
1D0B
|||\__ 9 + 2 = 11, v hexa to je B, tedy žádný přenos
||\___ 1 + F = 1 + 15 = 16, v hexa 10, zapíšeme 0, přenos 1
|\____ D + F + přenos 1 = 13 + 15 + 1 = 29 (1Dh), zapíšeme D, přenos 1
\_____ 0 + 0 + 1 = 1, přenos není
Nic víc na tom sčítání není, pro zkoušku si můžete vždy dané čísla převést
do desítkové soustavy, sečíst to normálně a pak výsledek převíst zpět do dané
soustavy.
Příklady:
1) Už jste na takové úrovni, že byste si měli umět vymýšlet příklady sami.
Vymyslete dvě (nebo pokud vám to připadá moc jednoduché, tak třeba i tři)
čísla, zkuste si jě sečíst normálně, pak je převeďte do desítkové, sečtěte
a převeďte zpátky - pro zkoušku.
2) Pokud vás dneska nic nenapadá, tak tady máte něco:
110101.001b + 100111.11b [1011100.111b]
110101.001h + 100111.11h [210212.111h]
FAB.BAFh + 9254.001h [0A1FF.BB0h]
1022 + 122.1 (v trojkové soustavě) [1221.1]
1.1.4.2. Odčítání
Opět připomeňme desítkovou soustavu:
157
-82
___
75
||\__ Dva a kolik je sedm? A pět je sedm...
|\___ Osm a kolik je pět? - blbost, přidáme základ ssoustavy, tedy
| osm a kolik je patnáct (5+10)? A sedm, máme tu přenos 1.
\____ Jedna a kolik je jedna? A nula je jedna..
Pokud by snad první číslo bylo menší než druhé, tak je prohodíme
a odečteme, u výsledku pak změníme znaménko na záporné, neboť A-B = - (B-A)
82 - 157 = - (157-82) = -75
Zkusme spočítat před časem zadaný příklad (viz 1.1.2 příklad 3) přímým
výpočtem bez převodů soustav.
19994h
-BABAh
______
DEDAh
||||\___ 14h - Ah = Ah, přenos (kvůli té čtrnáctce) je 1
|||\____ 19h - (Bh + přenos 1) = 19h - Ch = 25 - 12 = 13 = Dh, přenos 1
||\_____ 19h - (Ah + přenos 1) = 19h - Bh = 25 - 11 = 14 = Eh, přenos 1
|\______ 19h - (Bh + přenos 1) = 19h - Ch = 25 - 12 = 13 = Dh, přenos 1
\_______ 1 - přenos 1 = 0
Příklady:
1) 23h - Fh [14h] 101011b - 1011.1b [11111.1b] 835h-914h [-0DFh]
1.1.4.3. Násobení
Zase to je stejné jako v desítkové soustavě. Násobení ve dvojkové soustavě
je triviální, v ostastních je to ale kvůli velkému množství prováděných úkonů
(převádění mezi soustavami, sčítání, násobení) dosti náročnou věcí a vlastně
to ani nepotřebujeme. Proto vám ukáži jen to v té dvojkové soustavě. Ti z vás,
kterým to bude připadat moc jednoduché, si můžou vyzkoušet i jiné soustavy
(výsledky si můžou ověřit opět převedením čísel do desítkové soustavy.)
110101101b
*10011b
__________
110101101
110101101 jak vidíte, buďto pouze opíšete první číslo, nebo píšete
000000000 nuly - je to opravdu jednoduché. Akorát to potom musíte
000000000 umět sečíst. Že to je jednodušší než v desítkové soustavě?
110101101
_______________
1111111010111b
Pokud čísla obsahují desetinné čárky (tečky), tak se při písemném násobení
odstraní a výsledek má potom počet desetinných míst roven součtu desetinných
míst v zadání. Např. 1. číslo bude mít 3 des. místa, 2. má 4 des. místa.
Výsledek tedy bude míž 7 des. míst.
K násobení bych ještě mohl zmínit jeden zajímavý jev:
stejně jako v desítkové soustavě násobením *10 se přidá napravo jedna '0'
a násobením *100 se přidají dvě '0', tak ve dvojkové soustavě násobením *2
se přidá jedna '0' a násobením *4 se přidají dvě '0'. Prostě v číselné
soustavě se základem Z se násobením *Z^n přidá n nul. Abych to upřesnil,
tímto násobením se posouvá desetinná tečka (12.34 * 10 = 123.4). Při dělení
je tomu samozřejmě naopak.
Příklady:
1) 1101b * 1001b [1110101b] 111.0101b * 11101.11b [11011001.100011b]
1.1.4.4. Dělení No zase se to dělá stejně, ale problém je v tom, že mně písemné dělení více než jednociferným součtem nikdy moc nešlo. No, a stejně jsem měl vždycky jedničku z matematiky, takže vidíte, že to není nic důležitého :-) Jestli však někdo touží vědět, jak se to dělá, nechť si to nastuduje v rámci domácí přípravy... 1.1.5. Bit, byte, word a další cizí slova Doufám, že vás z toho nerozbolela hlava. Po pravdě, pochybuji, že budete někdy při programování potřebovat sečíst dvě binární čísla - počítač je umí sčítat sám. Předchozí kapitoly o aritmetických operacích jsem zařadil spíše pro úplnost, kdyby to někoho zajímalo. Následující kapitoly jsou již ale důležité, proto jim věnujte patřičnou pozornost. V počítači se počítá, jak jsem se již zmínil, ve dvojkové (binární) soustavě. Nejmenší jednotkou informace tu je tzv. BIT (zkratka z BInary digiT, tj. dvojková číslice). Představuje tedy jednu číslici dvojkového čísla, tedy stav jedna nebo nula. Jeden BIT je tedy schopen uchovat dva stavy - 1 nebo 0, zapnuto vypnuto, atd. Do takového bitu se vejde například informace o tom, zda je rozsvícena indikace NumLocku. Když budete trpěliví, za nedlouho už budete umět sami tento indikátor rozsvěcet a zhášet pomocí programu. Bit je ale hodně malá věc, takové číslo, třeba například osmnáct, to by se už do něj nevešlo. A tak je tu BYTE [bajt]. Byte je složen z osmi bitů, může v sobě uchovat 256 různých stavů, například čísla 0 - 255, nebo informaci o zapnutí nebo vypnutí osmi různých zařízení. Je to prostě normální osmimístné dvojkové číslo, např. 01101011 je jeden byte. Teď už konečně víte, co to znamená, když má počítač pamět 256 MB. Někomu by ale nestačilo počítat do 255, a tak tu máme také tzv. WORD, jsou to vlastně dva byty, neboli 16 bitů. Zde může být uchováno 2^16 = 65536 různých stavů. Složením dvou wordů vznikne třicetidvoubitový long word, a tak bychom mohli pokračovat dále.
1.2. Booleova algebra 1.2.1. Základní funkce Je to neuvěřitelné, ale základem elektronických počítačů jsou jen tři jednoduché logické funkce. Z těchto tří funkcí se dá odvodit jakákoliv další složitá funkce a třeba vyrobit celý počítač. Při programování se nám tyto funkce a některé další, odvozené, budou často hodit. Ve svém každodenním životě se velmi často setkáváme se situací, kdy se musíme rozhodnout na základě nějakých podmínek. Je-li podmínka jen jedna, vzniká poměrně jednoduchá situace, protože mohou nastat pouze dva případy: podmínka buď je, anebo není splněna (dva stavy - nepřipomíná vám to dvojkovou soustavu? Teď konečně uvidíte, k čemu nám bude). Jako příklad takové podmínky můžeme uvést větu: bude-li odpoledne pršet, půjdu do kina. Jestliže odpoledne prší, jdu do kina, a když neprší, do kina nejdu. Složitější situace může nastat, je-li podmínek několik, stačí již dvě. Můžeme například říci: "Bude-li odpoledne pršet a budou-li hrát zajímavý film, půjdu do kina." V tomto případě tedy vyhodnocujeme dvě podmínky, které na sobě nezávisejí (počasí nemá nic společného s programy kin). Každá z nich může být buď splněna nebo nesplněna, což přehledně můžeme zapsat do tabulky. V této tabulce vyjádříme splnění podmínky jedničkou a nesplnění nulou. +----------Đ-------------------------+ ¦odpoledne ¦ film je ¦ jdu do ¦ ¦ prší ¦ zajímavý ¦ kina ¦ ă----------+--------------Î----------Â ¦ 0 ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 0 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ 1 ¦ +----------¤-------------------------+ První řádek tedy budeme číst takto: odpoledne neprší a film, který hrají v kině, není zajímavý. Je zřejmé, že v takovém případě nás do kina nic netáhne, takže i ve třetím sloupečku je nula. Ve druhém a třetím řádku je sice splněna vždy jedna podmínka (buď hrají zajímavý film nebo prší), ale to samo nás k návštěvě kina také nepohne. Teprve ve čtvrtém řádku je zapsána situace, která nás přivede do kina, protože prší a současně v kině dávají zajímavý film. Tato současnost byla v naší podmínce vyjádřena spojkou a. Vědní disciplína, zabývající se zákony, podle nichž lze řešit úlohy podobné naší úloze "kdy půjdu do kina?" se nazývá logika. Je stará několik tisíciletí, ale teprv v 19. století přišel irský matematik George Boole [Džordž Búl] na myšlenku zapisovat takovéto úlohy matematicky a také je matematickými prostředky řešit. Po něm nese soustava pravidel pro formální zápis a vyhodnocení složených podmínek (říkáme jim též výroky) název Booleova algebra. Zde se nebudu zabývat všemi jejími zákony, pro naše účely nám postačí tři základní logické funkce: AND, OR a NOT, dále pak jedna složená z těchto tří: XOR. Každou logickou funkci lze zapsat do tzv. pravdivostní tabulky. V levé části tabulky jsou všechny možné stavy vstupů logické funkce. V pravé části je pak výstup logické funkce, který vrátí pro danou kombinaci vstupů.
AND - tato funkce se vyjadřuje spojkami a, i, a současně. Seznámili jsme se s ní už v úloze "Bude-li odpoledne pršet a budou-li hrát zajímavý film, půjdu do kina." Její hodnota je jednička pouze pokud všechny její vstupy jsou jednotkové. Nazývá se logický součin (konjunkce), protože její výstup je roven vlastně vynásobení vstupů (0*0 = 0, 0*1 = 0, 1*0 = 0, 1*1 = 1). Zde je její pravdivostní tabulka: +-Đ---------+ ¦a¦b¦a AND b¦ ă-+-Î-------Â ¦0¦0¦ 0 ¦ ¦0¦1¦ 0 ¦ ¦1¦0¦ 0 ¦ ¦1¦1¦ 1 ¦ +-¤---------+ OR - tuto funkci vyjadřujeme spojkou nebo. Jako příklad si uvedeme výrok: "Jestliže pro mně přijde Aleš nebo Bořek, půjdu na výlet." Jestliže pro mě nepřijde ani jeden, tak na výlet nepůjdu. Stačí ale, aby pro mě přišel jen jeden z nich a na výlet půjdu. V tom se OR liší od AND. Jestliže pro mě přijdou oba, na výlet se půjde taky (tady je čeština trochu záludná - spojka nebo je chápána spíše jako jen jedna z možností - venku je hezky nebo ošklivo, zároveň to je nesmysl. V logice ale mohou platit obě podmínky současně.) K tomu, aby OR vracelo hodnotu pravda (1), musí být alespoň jeden ze vstupů jednička. Tato funkce se nazývá logický součet (disjunkce), jelikož výstup je roven součtu vstupů (0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 2, ale takovou hodnotu Booleova algebra nezná, a tak 1+1 = 1 (ale jen v Booleově algebře, jinak by z tohoto paní učitelka neměla radost!)) +-Đ--------+ ¦a¦b¦a OR b¦ ă-+-Î------Â ¦0¦0¦ 0 ¦ ¦0¦1¦ 1 ¦ ¦1¦0¦ 1 ¦ ¦1¦1¦ 1 ¦ +-¤--------+
NOT - tato funkce je velice jednoduchá, protože má jediný vstup. Celá její
funkce je to, že vrátí opak. Spočítá vlastně VÝSTUP = 1 - VSTUP. Tuto funkci
si můžeme představit například na výroku "Nebude-li hezky, půjdu do kina."
Když bude hezky (1), tak do kina nepůjdu (0). Když nebude hezky (0), do kina
půjdu (1). Této funkci se také říká negace.
+-------+
¦a¦NOT a¦
ă-Î-----Â
¦0¦ 1 ¦
¦1¦ 0 ¦
+-------+
XOR - tato funkce je složená z předchozích funkcí, proto již nepatří mezi
základní. Tato funkce má hodnotu 1 pouze, pokud je právě jeden ze vstupů 1. Pokud
jsou oba jednotkové, výstup už je zase 0. V tomto jediném řádku se XOR liší
od OR. Jinými slovy nás XOR informuje o tom, že jeho vstupy jsou různé. Pokud
jsou stejné, vrací 0.
+-Đ---------+
¦a¦b¦a XOR b¦
ă-+-Î-------Â
¦0¦0¦ 0 ¦
¦0¦1¦ 1 ¦
¦1¦0¦ 1 ¦
¦1¦1¦ 0 ¦
+-¤---------+
Příklady:
1) Můžete si ověřit, že hodnota XOR je rovna:
a XOR b = ((NOT a) AND b) OR (a AND (NOT b))
Pomůcka: vyplňujte postupně sloupečky v této tabulce:
+-Đ-Đ---------Đ-----------Đ---------Đ------------------+
¦a¦b¦c = NOT a¦d = c AND b¦e = NOT b¦f = a AND e¦d OR f¦
ă-+-+---------+-----------+---------+-----------Î------Ż
¦0¦0¦ ¦ ¦ ¦ ¦ ¦
¦0¦1¦ ¦ ¦ ¦ ¦ ¦
¦1¦0¦ ¦ ¦ ¦ ¦ ¦
¦1¦1¦ ¦ ¦ ¦ ¦ ¦
+-¤-¤---------¤-----------¤---------¤------------------+
[výsledek: vyjde to, poslední sloupeček by měl být roven a XOR b]
[pokud jste udělali někde chybu, tak tady máte vždy daný sloupeček napsaný:]
[c = NOT a: {1, 1, 0, 0} ]
[d = c AND b: {0, 1, 0, 0}]
[e = NOT b: {1, 0, 1, 0} ]
[f = a AND e: {0, 0, 1, 0}]
[d OR f: {0, 1, 1, 0} ]
1.2.2. Použití Booleovy algebry Jestli jste pochopili, jak se s Booleovou algebrou počítá, tak vám nyní napíši ke každé funkci pár dalších příkladů, k čemu se může kromě základního významu ještě hodit. V assembleru máme k dispozici instrukce, které počítají s byty nebo i většími celky. Jak to ale funguje? Logické funkce přeci mají jako vstup jen bity. Je to jednoduché - instrukce provede logickou operaci vždy s příslušnými bity na stejné pozici v proměnné - tedy první s prvním, druhý s druhým atd. Výsledky funkcí ukládá do výsledné proměnné opět na stejnou pozici. Je velice časté, že se do jednoho bytu ukládá mnoho informací o nějaké věci, říká se tomu tzv. stavový byte. Například atributy souborů - první bit znamená například, jestli je soubor určen jen pro čtení, druhý bit může znamenat, jestli je soubor skrytý atd. Do jednoho bytu se nám tak vejde 8 různých vlastností, které můžou mít hodnotu 1 nebo 0 - ano nebo ne. Z bytu si pak můžeme pomocí logických funkcí vytáhnout jen ty informace, které nás zajímají, nebo naopak jen určité informace nastavovat, aniž bychom ovlivnili nastavení ostatních informací. AND * nulování daných bitů Mějme byte a = 10110110. Potřebujeme vynulovat první, třetí a pátý bit zprava. Vynásobíme tedy proměnnou 'a' bytem, který má samé jedničky, jen na pozicích, které chceme nulovat, jsou nuly. Hodnoty na ostatních pozicích tak zůstanou zachovány. a AND 11101010 = 10100010 * test jen určitých bitů Potřebujeme otestovat, jestli první čtyři bity zprava jsou rovny 0110. Ostatní bity nás nezajímají. Vynásobíme tedy proměnnou bytem, který má samé nuly, jen na pozicích, které nás zajímají, dáme jedničky. A výsledek porovnáme s tím, co chceme zjistit. 10110110 AND 00001111 = 0110 pravda 11000110 AND 00001111 = 0110 pravda (opravdu nezáleží na 4 bitech zleva) 10110010 AND 00001111 = 0110 není pravda
OR * nastavení na jedničku daných bitů Mějme byte a = 10110110. Potřebujeme nastavit na jedničku první, třetí a pátý bit zprava. Sečteme tedy proměnnou 'a' s bytem, který má samé nuly, jen na pozicích, které chceme nastavit na jedničku, jsou jedničky. Hodnoty na ostatních pozicích tak zůstanou zachovány. a OR 00010101 = 10110111 XOR * negovaní (invertování) daných bitů Mějme byte a = 10110110. Potřebujeme invertovat první, třetí a pátý bit zprava. Provedeme operaci XOR na proměnnou 'a' a byte, který má samé nuly, jen na pozicích, které chceme invertovat, jsou jedničky. Hodnoty na ostatních pozicích tak zůstanou zachovány. a XOR 00010101 = 10100011 * vynulování proměnné Pokud provdedeme operaci a XOR a, výsledek bude vždy nula, ať je 'a' jakékoliv. V některých starých procesorech byla operace XOR rychlejší než nastavování hodnoty proměnné, a proto někteří programátoři nulovali proměnné tímto způsobem pomocí funkce XOR. V dnešní době je to již přežitek, ale je dobré, abyste to věděli, protože se s tímto zápisem můžete setkat. * kontrolní CRC součet (sčítá se, ale nepřeteče) Pokud si vzpomenete, jak jsme sčítali čísla ve dvojkové soustavě, uvidíte, že operace XOR přesně sčítá dva bity, akorát neřeší přenos do vyššího řádu. To se může hodit například pro kontrolní CRC součty - pokud funkcí XOR postupně "sečteme" všechny byty v souboru, dostaneme opět jen jeden výsledný kontrolní byte. Kdykoliv pak můžeme s dost vysokou pravděpodobností ověřit, zda byl soubor změněn (poškozen), či ne. * kódování daným klíčem Vzhledem k tomu, že operace XOR vlastně invertuje požadované bity, můžeme ji použít i k jednoduchému kódování souborů. Zvolíme si jednobytový kód (klíč). Zakódování: zakódovaný_byte = původní_byte XOR klíč Rozkódování: původní_byte = zakódovaný_byte XOR klíč Platí totiž (snadno si to ověříte z funkční tabulky XOR): a = (a XOR b) XOR b, ať je b jakékoliv (prostě se dvakrát na stejném místě provede negace, čímž dostaneme původní bit). Ale jen ten, kdo zná klíč, ví, na kterých místech má invertovat.
* Záchranná disketa V době, kdy se ještě hojně používaly k přenosu dat diskety, jsem měl program, který uměl zabezpečit přenos dat tzv. záchrannou disketou. Diskety totiž byly poměrně dost nespolehlivé a často se stalo, že některá disketa již nešla přečíst. Princip spočíval v tom, že jsem pro přenos dat potřeboval například deset disket. Když jsem na ně nahrál data, spustil jsem program pro vytvoření záchranné diskety, který postupně všechny diskety načetl do paměti a provedl mezi nimi operaci XOR. Vznikla tak nová (jedenáctá) disketa, která byla výsledkem operace XOR všech předchozích disket. Zajímavé je, že když pak libovolná disketa nešla přečíst (ovšem vždy maximálně jedna), šla pak pomocí zbylých funkčních disket a záchranné diskety úplně přesně zrekonstruovat. Stačilo opět pouze provést operaci XOR mezi funkčními disketami a onou záchrannou. Je to velice zajímavé a když si vezmete dejme tomu tři byty a zkusíte si k nim udělat "záchranný" čtvrtý byte, a pak jeden z nich označíte za ztracený, tak můžete onen ztracený pomocí XOR všech ostatních zrekonstruovat. Vyzkoušejte si to, uvidíte, že to funguje. Je přitom úplně jedno, který z bytu "ztratíte". Vždy však může být maximálně jeden.
* Záměna dvou proměnných bez potřeby třetí proměnné
Mnoho programátorů vám bez rozmyšlení řekne, že jedinou cestou, jak prohodit obsah
dvou proměnných, je využít třetí proměnné. K tomu je však potřeba více paměti a je to zbytečné.
A = 3, B = 4
prohození:
do C ulož A
do A ulož B
do B ulož C
A je prohozeno, ale bylo zapotřebí další proměnné c.
Toto jde vyřešit i jinak, podívejte:
do B ulož A + B
do A ulož B - A (v A je teď hodnota původního B)
do B ulož B - A (v B je teď hodnota původního A)
To je sice šikovné, již nepotřebujeme třetí proměnnou, nicméně proměnná B musí mít dvojnásobnou
kapacitu než čísla, která chceme prohazovat. Takže tímto způsobem paměť také neušetříme.
Existuje však řešení, funkce XOR. Jak si vzpomínáte, je to funkce, která sčítá, ale nepřenáší přenos.
Provedeme operace stejné jako v předchozím postupu, jen místo sčítání a odčítání použijeme XOR.
Do proměnné se tak "otiskne" (zakóduje) druhá proměnná, aniž by byla potřeba pamět navíc.
do B ulož A XOR B
do A ulož A XOR B (v A je teď hodnota původního B)
do B ulož A XOR B (v B je teď hodnota původního A)
Moc pěkné, jak to funguje? Tak si to rozepišme:
A je A XOR (A XOR B). A XOR A jsou samé nuly. A samé nuly XOR B je přeci B.
B je A XOR (A XOR B) XOR (A XOR B). První část jsme se shodli, že je rovna B,
takže B XOR (A XOR B), což je zase B XOR B XOR A, takže samé
nuly XOR A, takže je výsledek A.
Zkuste si to na příkladu a zkonzultujte to s tabulkou XOR, uvidíte, že to pochopíte.
1.2.3. Základní pravidla Booleovy algebry Je dobré znát základní pravidla, která platí v Booleově algebře. Jejich uplatnění nalezneme spíše v číslicové technice než při samotném programování. Pro přehledný zápis používám + pro OR, * pro AND a čárku _ nad proměnnou pro NOT. * Zákony agresivnosti hodnot 0 a 1 a + 1 = 1 a * 0 = 0 * Zákony neutrálnosti hodnot 0 a 1 a + 0 = a a * 1 = a * Zákony komutativní Poznámka: tato dvě pravidla vetšinou bereme jako samozřejmost, ale například u maticového násobení v lineární algebře komutativnost násobení neplatí. Buďme proto rádi, že to, co bereme jako samozřejmost, platí i v Booleově algebře :-) a + b = b + a a * b = b * a
* Zákony asociativní
a + (b + c) = (a + b) + c
a * (b * c) = (a * b) * c
* Zákony distributivní
a * (b + c) = a * b + a * c
* Zákon dvojité negace
=
a = a
* Zákon o vyloučeném třetím
_
a + a = 1
_
a * a = 0
* Zákony absorpce
a + a = a
a * a = a
a + ab = a
a * (a + b) = a
* Zákony absorpce negace
_
a + a * b = a + b
_ _
a + a * b = a + b
_
a * (a + b) = a * b
_ _
a * (a + b) = a * b
* Zákony o vytvoření negace (zákony de Morganovy)
_____ _ _
a + b = a * b
_____ _ _
a * b = a + b
Pomocí tabulek jednotlivých logických funkcí si můžete sami ověřit, že jednotlivé zákony
opravdu platí. Důkazy zákonů logických funkcí jsou totiž velice jednoduché (narozdíl od důkazů
například s funkcemi reálných čísel). U logických funkcí stačí prostě vyzkoušet všechny možnosti
a ověřit, že ve všech případech se obě části rovnice shodují. Toto by u reálných čísel možné
nebylo, protože tam je počet všech možností nekonečný :-)
^
Version
This version of tutorial is from 2001, when I studied the second year on Secondary technical school in Liberec (SPŠSE).