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

TEACHINGZPC2

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

Napište funkci int bits_count(int number), která vrátí počet bitů potřebných pro reprezentaci celého čísla number.
Napište funkci char convert(char letter), která pomocí bitových operací převede znak na velké písmeno A–Z, pokud je znak malé písmeno a–z, nebo znak převede na malé písmeno a–z, pokud je znak velké písmeno A–Z.

Nápověda: velká a malá písmena se liší v pátém bitu.

Napište funkci int rotate_right(int number, int count), která posune číslo number o count bitů doprava a tyto posunuté bity jsou přidány na začátek v pořadí, ve kterém byly odsunuty. Například rotate_right(147 (10010011), 2) vrátí 228 (11100100).