ARCHIV

C/C++ (19) - Příkaz switch a bitové operátory

V minulých dvou dílech jsme poněkud odbočili, dnes se vrátíme k základní syntaxi, konkrétně k větvení programu příkazem switch. Naučíme se také přistupovat k jednotlivým bitům a ukážeme si i praktické příklady využití bitových operátorů.

4.5.2005 07:00 | Jan Němec | Články autora | přečteno 95368×

Příkaz switch

Z dílu o základní syntaxi dobře známe větvení programu pomocí if a else, umíme také využívat podmíněný výraz. Poměrně často je třeba rozdělit výpočet programu na větší počet větví. I zde si vystačíme s if a else, ale vzniklý kód nepůsobí příliš přirozeně.

if (i == 1) {
  /* Blok 1 */
} else if (i == 2) {
    /* Blok 2 */
  } else if (i == 3) {
      /* Blok 3 */
    } else {
       /* Blok default */
      }

Mnohem lepší je použít klíčové slovo switch.

int i;

switch (i) {
  case 1:
   /* Blok 1 */
    break;
  case 2:
    /* Blok 2 */
    break;
  case 3:
    /* Blok 3 */
    break;
  default:
    /* Blok default */
    break;
}

Příkazy break je třeba uvádět, v opačném případě by totiž program po provedení příkazů aktuálního bloku přešel na blok následující a pokud by ani ten neobsahoval kód zajišťující opuštění switche, vykonával by program postupně i následující větve switche. V poslední větvi nazvané default je break pouze pro ozdobu, ale je obvyklé jej psát i tam. Alternativním způsobem ukončení switche je opuštění nadřízené řídící struktury nebo její iterace, tedy příkazy return (opuštění funkce) a u switch vnořeného do cyklu i continue (následující iterace cyklu), použít se dá také goto.

Určitým omezením switche je, že jednotlivé větve mohou být charakterizovány pouze konstantním celočíselným výrazem, switch tedy nelze použít pro větvení podle hodnoty řetězce, ani podle hodnot, které nejsou známé v době překladu.

Bitové operátory

Celá nezáporná čísla mají ve světě počítačů díky dvojkové soustavě (téměř) jednotnou implementaci, jazyk C proto nabízí operátory, které usnadňují přístup k číslu jako k poli bitů.

Operátor A vrací jedničku právě tehdy, když oba operandy jsou nenulové. Operátoru NEBO stačí, když není nula alespoň jeden z nich a XOR vyžaduje, aby byla nenula právě jeden z operandů. Negace dělá z nuly nenulu na naopak. Logické verze operátorů už známe. Bitové varianty se od nich liší pouze tím, že nepracují s číslem jako s celkem, ale příslušnou operaci počítají po jednotlivých bitech. Například třetí bit výsledku operace a | b bude mít hodnotu (třetí bit a) || (třetí bit b).

Je trochu nelogické, že C nenabízí logické XOR, operátor ^^ tedy neexistuje. Za zmínku také stojí, že bitová negace, operátor ~ závisí na platformě, přesněji řečeno na velikosti číselného typu, v němž se počítá. Je to pochopitelné, neboť bitová negace udělá jedničky z nul v celé šířce příslušného typu a jednobytové číslo naplněné jedničkami bude mít jistě jinou hodnotu než stejným způsobem vyplněné číslo čtyřbytové. V tabulce je výsledek uveden pro čtyřbytové číslo, neboť to je v současnosti nejčastější velikost základního typu pro bitové operace - unsigned int. Přes tuto nepříjemnou vlastnost má bitová negace místo i v přenositelných programech, jak si ukážeme na příkladech.

Další důležitou skupinou operátorů tvoří bitové posuny, operátory << a >>. První posouvá všechny bity prvního operandu doleva o druhý operand bitů a zprava je doplňuje nulami. Bity posunuté mimo rozsah číselného typu se ztrácí. Druhý operátor provádí analogickou akci, jediným rozdílem je, že posunuje bity doprava.

Všechny bitové operátory v kombinaci s přiřazením umožňují zkrácený zápis. Následující dva příkazy jsou tedy ekvivalentní.

a = a | b;
a |= b;

Příklady bitových operací

Nejjednodušším příkladem je asi celočíselné násobení mocninou dvojky. Místo

a *= 2;

můžeme psát

a <<= 1;

a při použití špatně optimalizujícího překladače bude druhý způsob rychlejší. Občas potřebujeme získat maximální sudé číslo, které není větší než hodnota nějaké proměnné.

sude = (a >> 1) << 1;

 /* Nebo jednodušeji */

sude = a & ~1;

Všimněte si, že ačkoli hodnota ~1 závisí na velikosti typu, ve kterém se výpočet provede, výsledek celého výrazu a & ~1 již na platformě nezávisí, neboť úvodní jedničky z ~1 se vynulují operátorem &.

Bitové operátory pomáhají při práci s čísly, které reprezentují množinu. Běžně se například předává celá sada booleovských hodnot jako jediný parametr zejména knihovním funkcím. Například knihovna poskytující GUI může definovat

#define OKNO_VIDITELNE 1 
#define OKNO_TITULEK 2
#define OKNO_MAXIMALIZACE 4
#define OKNO_MINIMALIZACE 8
/* ... */

void VytvorOkno(unsigned priznaky);

a uživatel, který chce vytvořit viditelné okno s titulkem, ale bez tlačítek pro minimalizaci a maximalizaci, pak zavolá jen

VytvorOkno(OKNO_VIDITELNE | OKNO_TITULEK);

Známým algoritmem na generování všech prvočísel menších než zadaná konstanta N je Eratosthenovo síto. Nevýhodou algoritmu je jeho paměťová složitost, neboť pro prvních N přirozených čísel si musíme pamatovat, zda jsme již dokázali, že se nejedná o prvočíslo. Tuto informaci bychom mohli ukládat do proměnné typu char, ale osminásobné úspory paměti dosáhneme, pokud jednomu přirozenému číslu bude odpovídat jediný bit. Jednotlivé bity se z pole bytů mohou číst asi takhle:

#include <stdio.h>

int DejBit(const unsigned char *pole, unsigned offset) {
  /* bit na pozici offset je v bytu na pozici offset / 8,
     tedy  offset >> 3 */
  pole += (offset >> 3);
  /* v rámci zmíněného bytu je na pozici offset % 8, tedy offset & 7 */
  offset &= 7;
  /* spodní bity vynulujeme posunem doprava a horní konjunkcí s 1 */
  return (*pole >> offset) & 1;
}

void NastavBit(unsigned char *pole, unsigned offset, int hodnota) {
  
  pole += (offset >> 3);
  offset &= 7;
  if (hodnota)
    /* bit na pozici offset nastavíme na 1 */
    *pole |= 1 << offset;
  else
    /* bit na pozici offset nastavíme na 0 */
    *pole &= ~(1 << offset);
}

#define P 1000
#define N (P << 3)

unsigned char pole[P];

int main(void) {
  int i, j;

  /* zatím nevíme o žádném čísle, že není prvočíslo */
  for (i = 0; i < P; i++) {
    pole[i] = 0;
  }
  
  /* 0 ani 1 nejsou prvočísla */
  NastavBit(pole, 0, 1);
  NastavBit(pole, 1, 1);

  for (i = 2; i * i < N; i++) {
    /* složená čísla nás nezajímají */
    if (DejBit(pole, i)) continue;

    /* pro všechny násobky (stačí od i * i) */
    for (j = i * i; j < N; j += i) {
      /* označ je jako složená čísla */
      NastavBit(pole, j, 1);
    }
  }
  /* Vypiš prvočísla */
  for (i = 2; i < N; i++)
    if (!DejBit(pole, i))
      printf("%i ", i);
  return 0; 
}

Operátor ^, bitové XOR, se hodně používá v kryptografii, hashovacích funkcích, náhodných generátorech a podobně. Klíčovou vlastností operace je jednoduchý fakt

(a ^ b) ^ b == a

Tedy dvojnásobným vyxorováním libovolnou konstantou dostaneme původní číslo. Pokud Zarkáví vygeneruje dokonalou náhodnou posloupnost b_i a přenese ji bezpečnou cestou (například na CD) bin Ládinovi, mohou si posílat veřejnou sítí (odposlouchávanou CIA) zašifrované zprávy a_i o celkové délce vygenerované náhodné posloupnosti.

for (i = 0; i < N ; i++) {
  /* Šifrování - Zarkáví */
  c[i] = a[i] ^ b[i];
  odesli(c[i]);

  /* CIA odchytí c[i], ale a[i] nezíská */
  
  /* Dešifrování - bin Ládin */
  c[i] = prijmi();
  a[i] = c[i] ^ b[i];
}

Pokud nebudou posloupnost b_i používat opakovaně a b_i je opravdu náhodná, nelze tuto šifru žádným způsobem prolomit.

Pokračování příště

V příštím dílu se podíváme na dynamickou alokaci paměti.

Verze pro tisk

DISKUZE swap bez prostrednika pomoci operatoru ^ 4.5.2005 10:48 Zdenek Breitenbacher Re: swap bez prostrednika pomoci operatoru ^ 4.5.2005 11:50 Jan Němec Začátečnická otázka 6.5.2005 08:27 Jiří Král Re: Začátečnická otázka 6.5.2005 08:39 Jan Němec   Re: Začátečnická otázka 6.5.2005 09:11 Jiří Král poznamka 18.9.2006 19:26 Patejlik Zobrazit označené Zobrazit vše Příspívat do diskuze mohou pouze registrovaní uživatelé.