Search the Community
Showing results for tags 'xor'.
-
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; }