Informace

Pokud se chcete naučit základy číslicových soustav, počítání s nimi a úvod do Booleovy algebry, pak jste na správné stránce.

Tento text jsem sepsal v druhém ročníku na střední škole, byl jsem tehdy okouzlen programováním v assembleru a na českém trhu mi chyběla učebnice, která by ho srozumitelným způsobem vysvětlila hezky od začátku. Základy assembleru jsem se naučil v jednom volitelném předmětu na základní škole a rozhodl jsem se své znalosti předat dál. Měl jsem hodně volného času, a tak jsem v duchu tutorialů, kterých na internetu najdete mraky, začal psát jeden vlastní. Tak, aby byl k dispozici pro všechny a zadarmo. Stejně, jako jsem se já dozvěděl zadarmo mnoho užitečných informací od jiných lidí z internetu. Po čase mě to ale přestalo bavit, takže jsem se ani k vlastnímu assembleru v textu nedostal :-)

Některé věty jsou napsány poněkud kostrbatě, to však odpovídá věku, ve kterém jsem text psal. Dokonce si tak trochu matně vybavuji, že něco jsem formuloval schválně vtipně, abych tím odlehčil tíži vlastních informací, které jsem se čtenářovi snažil předat. Byl bych velice rád, kdyby i v dnešní době mohl tento úvod do číslicové techniky někomu posloužit.

Učebnice


                      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

* 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ý :-)

Verze

Verze tohoto textu pochází z roku 2001, kdy jsem studoval druhý ročník SPŠSE.