Uživatelské nástroje

Nástroje pro tento web


prog:bitop

Další rysy jazyka

V následujícím popíšeme některé možnosti jazyka, na které se v dosavadním výkladu nenalezl vhodný prostor, přesto jsou nezřídka využívány.

Bitové operace

Návrh počítačů je založen na elektronických obvodech pracujících se dvěma stavy - logická jednička a logická nula, které jsou realizovány přítomností či nepřítomností elektrického napětí v obvodu. Proto jsou veškeré datové typy vnitřně reprezentovány hodnotami ve dvojkové soustavě, tj. skládají se z dvojkových (binárních) číslic - bitů. Např. pro číslo 26 máme

26 = 16 + 8 + 2 = 1.24 + 1.23 + 0.22 + 1.21 + 0.20 = 11010b,

tedy není obtížné reprezentovat nezáporné celé číslo ve dvojkové soustavě.

:-)  Na světě je 10 druhů lidí: ti, co znají dvojkovou soustavu, a ti ostatní.

Pomocí řetězcové metody format umíme číslo ve dvojkové soustavě i zobrazit. Celočíselné konstanty je možné i zadávat přímo v binárním tvaru pomocí prefixu 0b (podobně v osmičkové soustavě pomocí 0o nebo v šestnáctkové soustavě pomocí 0x).

0b11010                              # => 26
0o755                                # => 493
0x2517                               # => 9495

Logické operace po bitech

Z předchozích hodin už umíme pracovat s logickými hodnotami a pomocí logických operátorů not (negace), and (logický součin), or (logický součet) a xor (úplná disjunkce tj. opak ekvivalence) vytvářet i složitější logické výrazy.

Python (stejně jako další programovací jazyky) nám dává možnost provádět některé operace tzv. bit po bitu. Například binární operátor (tj. operátor s dvěma operandy) & pro logický součin po bitech poskytuje výsledek, kde nejnižší bit je logickým součinem nejnižších bitů obou operandů a analogicky pro další bity.1)

0b11010 & 0b111                      # => 2 (tj. 0b10)

Pro lepší pochopení si lze operaci rozepsat následovně:

   1  1  0  1  0
&  0  0  1  1  1
   -------------
   0  0  0  1  0  => 0b10 => 2

Podobně máme operátory | pro logický součet po bitech a ^ pro úplnou disjunkci po bitech. Oba operandy musí být typu int.

0b11010 | 0b111                      # => 31 (tj. 0b11111)
0b11010 ^ 0b111                      # => 29 (tj. 0b11101)

Příklad použití

Následující funkce určí, zda parametr (nezáporné celé číslo) je mocninou 2 nebo nikoliv.

def je_mocnina2(n):
    return not(n & (n - 1))

Proč tento na první pohled trochu tajemný kód funguje? Mocnina 2 má ve dvojkové soustavě zápis skládající se z úvodní jedničky a samých nul. Číslo o 1 menší se pak skládá ze samých jedniček a má o 1 binární číslici méně. Logický součin po bitech pak na každém místě znamená 0, nakonec výsledná 0 interpretovaná jako logická hodnota znamená False, která po negaci pomocí operátoru not dává návratovou hodnotu funkce jako True. Konkrétně pro 32 (což je 25)

32 & (32 - 1) => 32 & 31 => 0b10000 & 0b1111 => 0b0 => False
not(False) => True

Pro číslo, které není mocninou 2, má operace & vždy nenulový výsledek2), což je interpretováno v logickém kontextu jako True. Po negaci je návratová hodnota funkce False, např. pro 12 máme

12 & (12 - 1) => 12 & 11 => 0b1100 & 0b1011 => 0b1000 => True
not(True) => False

Bitový posun

Při práci s daty na bitové úrovni se poměrně často potřebují operace bitového posunu vlevo či vpravo. K tomu máme binární operátory << (posun vlevo, zprava vkládáme 0) a >> (posun vpravo, číslice nejnižšího řádu je zahozena). Pravý operand (nezáporné celé číslo) udává, o kolik pozic se mají bity posunout.

0b1011 << 1                          # => 22 (tj. 0b10110)
0b1011 << 4                          # => 176 (tj. 0b10110000)
 
0b1011 >> 1                          # => 5 (tj. 0b101)
0b1011 >> 3                          # => 1 (tj. 0b1)

Posun o jednu pozici vlevo má význam násobení 2, o 4 pozice vlevo pak násobení 16 (tj. 24). Naopak posun vpravo o jednu pozici odpovídá celočíselnému dělení 2, o 3 pozice vpravo celočíselnému dělení 8 (tj. 23). Uvědomte si, že v naší běžné desítkové soustavě to funguje naprosto obdobně - připsání nuly na konec čísla znamená vynásobení 10, škrtnutí poslední číslice pak celočíselné dělení 10.

Příklad použití

Ukážeme si funkci s jedním celočíselným parametrem, která vytvoří číslo složené z bitů zadaného čísla v obráceném pořadí.

def bity_pozpatku(n):
    vysledek = 0 # začneme s prázdným výsledkem
    while n != 0: # dokud je na vstupu nějaký jedničkový bit
        vysledek = vysledek << 1 # posuneme výsledek o jedno místo doleva
        bit = n & 0b1 # nejnižší bit ze vstupu
        vysledek = vysledek | bit # vložíme na nejnižší řád výsledku
        n = n >> 1 # zahodíme nejnižší bit vstupu a pokračujeme v cyklu
    return vysledek

Pro úplné pochopení dodejme, že výsledek operace n & 0b1 je právě hodnota nejnižšího bitu n (někdy hovoříme o vymaskování bitu), tj. 0 nebo 1. Pomocí operace | je tato hodnota vložena do nejnižšího bitu výsledku. Postupně v cyklu ze vstupní hodnoty odebíráme bity od nejnižšího k nejvyššímu a vkládáme je do výsledku tak, že první vložený se posune na nejvyšší místo, atd.

Podmíněný výraz

V programech se poměrně často vyskytuje konstrukce, kdy proměnné na základě nějaké podmínky přiřadíme jednu ze dvou možných hodnot, např.

if cislo >= 0:
    druh = "nezáporné číslo"
else
    druh = "záporné číslo"

Pro zkrácení takového zápisu je možné použít i formu

druh = "nezáporné číslo" if cislo >= 0 else "záporné číslo"

Výsledek i výpočetní náročnost jsou naprosto shodné, užití záleží na vaší osobní preferenci.

Rozšířené přiřazení

Zvýšením přehlednosti a odstraněním nutnosti opakovat identifikátor proměnné je motivováno i zavedení rozšířeného přiřazovacího příkazu. Často se i v našich programech objevuje konstrukce typu

krok = krok + 1

(například pro inkrementaci řídicí proměnné cyklu), kterou můžeme zapsat i jako

krok += 1

bez jakékoliv změny významu. Toto rozšířené přiřazení je mimo součtu += možno použít i pro odčítání -=, násobení *=, reálné /= i celočíselné //= dělení, operaci zbytku po celočíselném dělení %= a také pro právě představené bitové operace &=, |= a ^= stejně jako bitové posuny <<= a >>=. Na levé straně samozřejmě jako u každého přiřazovacího příkazu musí stát identifikátor proměnné, na pravé straně může být konstanta, proměnná, volání funkce či nějaký složitější výraz správného typu.

Funkci pro výpočet faktoriálu bychom tak mohli přepsat do tvaru

def faktorial(n):
    if n == 0:
        return 1
    for i in range(2, n):
        n *= i # stejné jako n = n * i
    return n

a ve výše uvedené funkci bity_pozpatku bychom mohli použít rozšířená přiřazení s posunem a logickým součtem po bitech.

1)
Pro připomenutí uvádíme tabulku pro základní logické binární operátory.

a b a & b a | b a ^ b
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0
2)
nejvyšší jedničkový bit obou čísel je na stejné pozici
prog/bitop.txt · Poslední úprava: 05.03.2018 17:32 autor: Ivana Stefanová

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki