8. seminář - Bitové operace

Jak již víme, jazyk Python, stejně jako většina jiných vysokoúrovňových programovacích jazyků̊, programátory odstiňuje od řady nízkoúrovňových záležitostí. Jednou z výjimek jsou bitové operace, jež umožňují manipulaci s daty na úrovni jednotlivých bitů, kterým se budeme věnovat v této kapitole. Veškerá data v počítači jsou uložena ve formě jedniček a nul. Pokud například vytvoříme proměnnou obsahující celé číslo, je toto číslo uloženo v paměti v binární podobě. Nejmenší adresovatelnou jednotkou paměti je jeden bajt (8 bitů̊). Uvažme následující příklad.

    a = 42
    
    # Hodnota 42 se uloží do paměti do 1B
    | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |

Bitové operátory

V jazyce Python je pro manipulaci s jednotlivými bity k dispozici šest bitových operátorů, které jsou shrnuty v níže. Tyto operátory pracují s binární reprezentací celých čísel a znaků. Bitové operace jsou obvykle podporovány přímo procesorem počítače. V důsledku toho je výpočet výsledků těchto operací velice rychlý.

• & - bitový součin (AND)
• | - bitový součet (OR)
• ^ - bitový exklusivní součet (XOR, znak stříška)
• ~ - bitová negace (NOT, znak tilda)
• << - bitový posun vlevo
• >> - bitový posun vpravo

Bitový součin

Při operaci bitového součinu se provede logický součin (AND) mezi korespondujícími bity.

    # bitový součin
    print(10 & 7) # vypíše: 2
    
    # Jak probíhá výpočet
    
    10 = 0 0 0 0 1 0 1 0
                       &
    7  = 0 0 0 0 0 1 1 1
    ____________________
    2  = 0 0 0 0 0 0 1 0

Bitový součet

Při operaci bitového součinu se provede logický součet (OR) mezi korespondujícími bity.

    # bitový součet
    print(10 | 7) # vypíše: 15
    
    # Jak probíhá výpočet
    
    10 = 0 0 0 0 1 0 1 0
                       |
    7  = 0 0 0 0 0 1 1 1
    ____________________
    15 = 0 0 0 0 1 1 1 1

Exklusivní bitový součet

Při operaci bitového součinu se provede logický součet (XOR) mezi korespondujícími bity.

    # exklusivní bitový součet
    print(10 ^ 7) # vypíše: 13
    
    # Jak probíhá výpočet
    
    10 = 0 0 0 0 1 0 1 0
                       ^
    7  = 0 0 0 0 0 1 1 1
    ____________________
    13 = 0 0 0 0 1 1 0 1

Bitová negace

Bitová negace je unární operátor. Při operaci bitové negace je každý bit invertován (bit s hodnotou jedna je přepsán na hodnotu nula a naopak). Formálně je tato operace pro číslo a definována následovně: ~a = -(a + 1).

    # bitová negace
    print(~10) # vypíše: -11
    
    # Jak probíhá výpočet
    
    10 = 0 0 0 0 1 0 1 0 -> 1 1 1 1 0 1 0 1 = -11

Přestože je bitová negace jednoduchou operací, výsledek vyhodnocení výrazu ~10 nemusí být na první pohled zřejmý. Důvodem je dvojkový doplňkový kód, který je použit pro reprezentaci záporných čísel v paměti počítače. Výsledná hodnota -11 = 11110101 je výsledkem bitové negace čísla 10 = 00001010.

Bitový posun vlevo

Při operaci bitového posunu vlevo jsou bity v paměti počítače posunuty o zadaný počet bitů směrem doleva a zprava doplněny nulami

    # bitový posun vlevo
    print(10 << 2) # vypíše: 40
    
    10 = 1010 -> 101000 = 40
    
    # Bitový posun vlevo je možné použít k velmi rychlému násobení mocninou čísla dva.
    42 << 1 # 84 = 42 * (2**1)
    42 << 2 # 168 = 42 * (2**2)
    42 << 3 # 336 = 42 * (2**3)

Bitový posun vpravo

Při operaci bitového posunu vpravo jsou bity v paměti počítače posunuty o zadaný počet bitů směrem doprava (bity se ztrácí) a zleva doplněny nulami.

    # bitový posun vpravo
    print(10 >> 2) # vypíše: 2
    
    10 = 1010 -> 0010 = 2
    
    # Bitový posun vlevo je možné použít k velmi rychlému dělění mocninou čísla dva.
     48 >> 1 # 24 = 48 / (2**1) 
     48 >> 2 # 12 = 48 / (2**2) 
     48 >> 3 # 6 = 48 / (2**3)

Priorita operátorů

Bitové operátory, stejně jako ty aritmetické, mají svoji prioritu, která určuje pořadí jejich vyhodnocování ve výrazu. Priority všech operátorů jsou shrnuty v tabulce. Připomeňme, že ve složitějších výrazech je lepší explicitně určit pořadí vyhodnocování jednotlivých operátorů pomocí závorek.

Praktické použití

Pomocí bitových operátorů ̊můžeme adresovat jednotlivé bity a dále s nimi pracovat. V následující ukázce jsou implementovány funkce set_bit() a delete_bit().

    def set_bit(number, bit):
        mask = 1 << bit
        return number | mask
    
    def delete_bit(number, bit):
        mask = ~(1 << bit)
        return number & mask
    
    # použít funkce set_bit()
    set_bit(0, 0) # vrací: 1 (0b1)
    set_bit(0, 7) # vrací: 128 (0b10000000)
    
    # použít funkce delete_bit()
    delete_bit(255, 0) # vrací: 254 (0b11111110)
    delete_bit(255, 2) # vrací: 251 (0b11111011)

Bitové operátory nám umožňují efektivnější uložení informací. Následující příklad implementuje klasický učebnicový příklad reprezentace data (den, měsíc, rok) pomocí čísel. Při vhodném nastavení je možné datum reprezentovat jako dvoubajtové číslo.

    BEGIN = 2020
    BITS_PER_DAY = 5
    BITS_PER_MONTH = 4
    BITS_PER_YEAR = 7
    
    def convert_date_to_number(day, month, year):
        date = day
        date <<= BITS_PER_MONTH
        date |= month
        date <<= BITS_PER_YEAR
        date |= (year - BEGIN)
        return date
        
    def convert_number_to_date(date):
        year = BEGIN + (date & 2**BITS_PER_YEAR - 1) # rok
        month = (date >> BITS_PER_YEAR) & 2**BITS_PER_MONTH - 1 # měsíc
        day = (date >> (BITS_PER_MONTH + BITS_PER_YEAR)) & 2**BITS_PER_DAY - 1 # den
        print(f"{day}. {month}. {year}")
    
    date = convert_date_to_number(4, 8, 2112)
    convert_number_to_date(date)
    print(date) # vypíše: 9308
    print(bin(date)) # vypíše: 0b10010001011100

Úkoly