Tanga

Bitové operátory

Obsah

• Úvod
• Bitové operácie
• Operácia not
• Operácie and, or
• Operácie shl, shr
• Operácia xor

1. Úvod

K napísaniu tohoto návodu ma inšpiroval tento príspevok z roku 2012, ktorý podľa môjho názoru má k dnešnej úrovni našich návodov celkom nízku kvalitu a tiež v ňom chýbajú určité informácie. Niektoré body z neho som podobne použil aj ja.

V príspevku budú tiež cvičenia, ktoré kým spravíte, rozhodne budete bitovým operáciám rozumieť. Nejaký čas nad cvičeniami určite strávite.

V praxi majú tieto operácie veľký význam, predsalen, ak jeden bit môže mať hodnotu 0, alebo 1, tak so znalosťami bitových operátorov je možné do jedného 32-bitového čísla (klasická premenná v Pawn) uložiť 32 true/false hodnôt.

Do úvodu však ešte uvediem, že síce dokážu neuveriteľne šetriť pamäť (v prípadne jednej bool hodnoty až 32násobná úspornosť), tak každá operácia trvá určitý čas a z úmyslu ušetriť pamäť by výsledok mohol byť až strata rýchlosti.

Ak potrebujete pracovať s binárnymi číslami, Windows kalkulačka je najvhodnejší nástroj (Štart->calc.exe->Možnosti->Programátorská). Otázky sa môžete pýtať v komentároch.

Veľa šťastia a nových vedomostí.

2. Bitové operácie

Najmenšia dátová jednotka na počítači je bit, ktorý patrí do množiny {0, 1}. Vždy nadobúda práve jednu hodnotu. Operácie prebiehajú v dvojkovej sústave. Desiatková sústava pozostáva z {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Jeden bajt má osem bitov. Keďže v Pawn sa používajú len 4-bajtové premenné, všetky bunky majú 32 bitov.

Množina {0, 1} sa dá zobraziť do množiny {false, true}. Premenná, ktorá môže nadobúdať iba hodnoty true a false máva typ "bool", po matematikovi Georgeovi Booleovi.

Pawn umožňuje vypisovať čísla v binárnom tvare na konzolu. Stačí do printf() dať namiesto "%d" (decimal - desiatková sústava) "%b" (binary - binárna sústava). Kód si spustite.

#include <a_samp>

main() {
  for (new i; i < 16; i++) {
    printf("%2d = 0b%04b", i, i);
  }
}

Cvičenie 1. V Pawn existujú kľúčové slová true a false. Keďže je to beztypový jazyk, je možné zamieňať typy premenných (vyskočí iba warning). Zistite k akým celočíselným hodnotám sa dajú priradiť výrazy true a false pomocou nasledujúceho kódu:

#include <a_samp>

main() {
  new a = ??;
  if (a) {
    ??
  }
}

3. Operácia not

Všetky bity naraz je možné znegovať operáciou not, ktorá má len 1 argument a značí sa '~'.

#include <a_samp>

main() {
  new a = 0b11001100;
  printf("%032b", a);
  printf("%032b", ~a);
}

4. Operácie and, or

Operácie and a or majú dva parametre a ich výsledkom je jedna premenná s rovnakým počtom bitov.

Operácie and a or sa v Pawn vykonávajú na všetkých bitoch premennej zaradom, akoby v cykle. Najprv sa vykoná operácia na prvých bitoch premnenných, potom na druhých bitoch premenných, atď.

Pawn obsahuje operátor '&' pre operáciu and, ktorá je tiež nazývaná "bitový súčin". Súčin preto, lebo výsledok tejto operácie je "1" iba v prípade, že obidva parametre sú "1".

Operáciu or (tiež nazývanú logický súčet) zapisujeme v Pawne operátorom '|'.

To, ako Pawn chápe '&' a '|', nám môže sám ukázať. Vašou úlohou je tieto operácie pochopiť priamo od neho. Výstup programu kvôli prehľadnosti pripomína mechanické sčitovanie "pod sebou na papieri".

#include <a_samp>

main() {
  new a = 0b1010,
      b = 0b1100;

  printf("0b%b\n0b%b &\n------\n0b%b\n\n", a, b, a & b);
  printf("0b%b\n0b%b |\n------\n0b%b\n\n", a, b, a | b);
}

Cvičenie 2. Pri prenose dát sa z kontrolných dôvodov pridáva k preneseným dátam jeden bit navyše, jedná sa o tzv. paritný bit. Prenáša sa 8 dátových bitov a jeden paritný - ten úplne naľavo je paritný. (tj. "100000101"). Vašou úlohou je naprogramovať detekciu hodnoty paritného bitu. Doplňte do nasledujúceho kódu operáciu binárneho súčinu, aby kód správne fungoval. Rada: Chcete detekovať, či bol daný bit nastavený na "1".

#include <a_samp>

main() {
  new number = 0b100101101;
  
  if (parityBitSet(number)) {
    print("Paritny bit je nastaveny na 1.");
  }
}

parityBitSet(number) {
  if (??) {
    return true;
  } else {
    return false;
  }
}

Cvičenie 3. V zastaralej databáze údajov, ktorá musela šetriť maximálny možný priestor, sú údaje o obyvateľoch uložené v bitoch. Napr. nultý bit (úplne vpravo) obsahuje pohlavie (0-muž/1-žena), ten vedľa neho obsahuje informáciu, či osoba poberá dávky v hmotnej núdzi, nasledujúci hovorí o zamestnanosti danej osoby, atď. Databáza používa celkovo 16 bitov, ostatné sú nedefinované. V novej verzii databázy sa zmenil význam piateho bitu a preto chceme bez zmeny ostatných informácií vynulovať daný bit každej osobe. Doplňte procedúru update() tak, aby databáza spĺňala nové požiadavky.

#include <a_samp>

new people[] = { 0b1100111100110101,
                 0b0011001101010101,
                 0b1111111001110111 };

main() {
  update();
  
  for (new i; i < sizeof(people); i++) {
    printf("%016b", people[i]);
  }
}

update() {
  for (new i; i < sizeof(people); i++) {
    ??
  }
}

5. Operácie shl a shr

Nasledujúce dve operácie vykonávajú aritmetické bitové posuny. Aritmetické znamená, že pri posune sa zachová (záporné), alebo vznikne (záporné) znamienko. SHL a SHR sú skratky pre shift left a shift right. Operátormi pre tieto operácie sú "<<" a ">>".

Argumentom bitového posunu je počet bitov, o ktoré chceme číslo posunúť. Pri operátore "<<" je novo-pridaný bit 0.

#include <a_samp>

main() {
  new a = 1;
  for (new i; i < 8; i++) {
    printf("%08b", a << i);
  }
  printf("");

  a <<= 3; // je mozne pouzit aj tuto syntax
  printf("%08b", a);
}

Na binárnej úrovni sa rozlišujú záporné a kladné čísla najvyšším bitom, tj. celková kapacita 4 bajtov je rozdelená na 2 polovice - kladnú a zápornú. U záporných čísel je 31. bit (ten úplne naľavo) vždy 1, pričom u kladných 0.

Aritmetický posun vpravo sa teda správa ináč než ten vľavo. Znamienko čísla sa zachováva pri operácii ">>". Operácia ">>" akoby preskočí bit, ktorý určuje zápornosť čísla a posúva všetky ostatné bity. Lepšiu predstavu o tomto procese získate spustením nasledujúceho kódu.

Existuje ešte tretí, logický operátor pre posun vpravo, ktorý (záporné) znamienko nezachováva ani nevytvára. Tento operátor je ">>>".

#include <a_samp>

main() {
  new a = -10;
  printf("%032b = %d", a, a);
  printf("%032b = %d", a >> 1, a >> 1);
  printf("%032b = %d", a >> 2, a >> 2);
  printf("%032b = %d", a >>> 1, a >>> 1);
  printf("%032b = %d", a >>> 2, a >>> 2);
}

Cvičenie 4. Majme v desiatkovej sústave číslo "65421". Toto číslo z hlavy vydeľte číslom "100", resp. "10^2". Zvyšok zanedbajte. Výsledok si overte.

Cvičenie 5. Majme v binárnej sústave číslo "1101010". Z hlavy vydeľte toto číslo číslom "4", resp. "2^2". Zvyšok zanedbajte. Výsledok si overte. Rovnakým spôsobom výsledok vynásobte číslom "4". Dostali ste pôvodné číslo?

Cvičenie 6. Doplňte riešenie cvičenia 2 tak, aby nie len kontrolovalo paritný bit, ale aby kontrolovalo, či je paritný bit správny. Skontrolujte hodnotu všetkých bitov a rozhodnite, či ich počet (či sú párne) sedí s informáciou z paritného bitu. Takáto kontrola sa v praxi používa pri prenose dát.

Cvičenie 7. Doplnením do kódu nižšie vygenerujte číslo s takýmto tvarom: "0b1010101010101010". Rada: použite okrem operácie na bitový posun aj bitový súčet (na nastavenie bitu) a bitový súčin (na overenie/zistenie hodnoty nejakého bitu).

#include <a_samp>

main() {
  new number = 0;
  
  for (new i; i < 15; i++) {
    if (!(??)) {
      ??
    }
    ??
  }

  printf("0b%016b", number);
}

6. Operácia xor

Ako aj v názve, tak aj vo funkcionalite sa podobá operácii or.

#include <a_samp>

main() {
  new a = 0b1010,
      b = 0b1100;

  printf("0b%b\n0b%b ^\n------\n0b%04b\n\n", a, b, a ^ b);
}

Cvičenie 8. Istý fanúšik jazyka assembler, Rendall Hide, má rád prácu s bitmi. Posledne o sebe tvrdí, že našiel vlastnosť, ktorá dokáže nastaviť zázračným spôsobom hodnotu akejkoľvek premennej na 0. Mnohí ho majú za blázna a nepočúvajú čo hovorí, ale je naozaj blázon, alebo len neodborná programátorská verejnosť nerozumie kráse jeho mágie? Tvrdí, že dokáže vynulovať premennú bez použitia iných konštánt ako "0" a bez operácií ako násobenie, odčítanie či and. Údajne je táto vlastnosť zapísaná tu:

n xor n = 0

Preskúmajte túto údajnú vlastnosť a overte, či Rendall Hide bol naozaj blázon, alebo majster majstrov.

Cvičenie 9. Nádejný programátor Peter "VlastneŠifrovanieJeNajlepšie" Skutočný si všimol neuveriteľnú a jedinečnú vlastnosť operácie xor. Nazdáva sa, že by možno odhalil niečo, čo by nazýval "symetrické šifrovanie", hoc názvom si ešte nie je istý. Prezrite a vylúštite na bitovej úrovni pozadie tejto operácie.

#include <a_samp>

const secret = 123456;

main() {
  new number = 9087324;

  number = encode(number);
  printf("My new hashed password is: %d", number);
  
  number = decode(number);
  printf("The real password is: %d", number);
}

encode(number) {
  return number ^ secret;
}

decode(number) {
  return number ^ secret;
}

Cvičenie 10. Alen During, známy hejter, si s obľubou prezerá internet a hľadá veci na kritiku. Po zlej noci počas ranného rituálu s telefónom našiel príspevok Petra Skutočného a jeho procedúry encode() a decode(). Nemal však chuť sa niečím takým zaoberať a tak mu zo svojho smartphone-u poslal jediný snippet bez slov. Čo ním asi chcel povedať?

#include <a_samp>

main() {
  new crackedSecret = gimmeSecret(9087324, 9128732);
  printf("%d", crackedSecret);
}

gimmeSecret(pass, hashedPass) {
  return pass ^ hashedPass;
}