12. seminář - Bitové operátory a bitová pole

Binární soustava

Hodnoty v paměti jsou uloženy v binárním tvaru. Číslo v desítkové soustavě můžeme zapsat v binární soustavě:

    157 = 10011101
    20  = 10100

Bitové operátory

V jazyce C 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
    printf("%i", 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
    printf("%i", 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
    printf("%i", 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
    printf("%i", ~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

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
    printf("%i", 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
    printf("%i", 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)

Množiny

Pomocí bitových operátorů lze reprezentovat množinu. Mějme množinu čísel od 0 do 7 (univerzum). Libovolnou podmnožinu bychom mohli reprezentovat jako bitový vektor. 1 = obsahuje prvek na dané pozici, 0 = neobsahuje. Uvažujme následující množiny:

A = {1,2,7}, B = {5,6,7}, C = {0,1,2,3,4,5,6,7}, D = ∅

    // Reprezentace mnozin v pameti
    
        7   6   5   4   3   2   1   0    
    A = 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 
    B = 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 
    C = 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 
    D = 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

Tato reprezentace nám umožní velice jednoduše a hlavně rychle vypočítat průnik dvou množin. Poslouží nám k tomu operace & (bitový součin).

Příklad

    A ∩ B = {1,2,7} ∩ {5,6,7} = {7}
    
    // Prunik pomoci bitoveho soucinu
    1 0 0 0 0 1 1 0
                  &
    1 1 1 0 0 0 0 0
    ---------------
    1 0 0 0 0 0 0 0

Můžeme tedy reprezentovat množinu která obsahuje hodnoty od 0 do 7 můžeme reprezentovat hodnotou typu char.

    char set_a = 134, set_b = 224;
    char intersection = set_a & set_b; // 128

Množina jako pole čísel

Pokud pro množinu použijeme typ int, jsme omezeni jeho velikostí. Pokud má int 4 bajty, můžeme ho použít pro uložení max 32prvkové množiny. Řešením je použít pole int/char.

    // set = {1, 3, 6, 10, 12, 15}
    unsigned char set_a[] = {74, 148};
    // Protoze 
    //01001010 = 74 a 10010100 = 148 a spojenim ziskame mnozinu
    
    15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0
    1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0

Průnik této množiny pak provádíme po složkách (prvcich pole) pokud bychom měli definovanou ještě množinu set_b, tak průnik set_a a set_b provedeme následovně:

    #define WORD_COUNT = 2 // Počet prvků v poli
    char set_a[] = ...
    char ser_b[] = ...
    char intersection[WORD_COUNT];
    
    for (int i = 0; i < WORD_COUNT; i += 1) {
        intersection[i] = set_a[i] & set_b[i];
    }

Bitové pole

Bitové pole je podobné struktuře, jen místo typů specifikujeme počet bitů.

    typedef struct {
        unsigned day : 5;
        unsigned month : 4;
        unsigned year : 7;
    } Date;

Člen den má velikost 5 bitů, takže do něj můžeme uložit číslo v rozmezí 0–(25 − 1), tedy 0 − 31. Celkový součet bitů nesmí přesáhnout hodnotu sizeof(int). Položky mohou být buď celé znaménkové (signed), nebo celé neznaménkové (unsigned). Práce s bitovým polem probíhá stejně jako se strukturou.

    #define BEGIN_OF_TIME 1980

    Date today = {23, 4, 2008 - BEGIN_OF_TIME};
    Date tomorrow = today;
    tomorrow.day += 1;
    today.month = 6;
    today.year = 2009 - BEGIN_OF_TIME;

Úkoly