A bináris logikai műveletek (AND, OR, XOR) fontos szerepet játszanak a bitek kezelésében, mint például a bitek beállítása, kikapcsolása, illetve megfordítása. Az alábbiakban bemutatjuk, hogyan lehet ezeket a műveleteket felhasználni gyakorlati feladatok megoldására.
Az AND művelet csak akkor ad 1-es eredményt, ha mindkét bemenet 1. A bitek “kikapcsolására” használhatjuk, mert a 0 hatására minden egyes bitet 0-ra állít.
Igazságtábla:
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Példa: Adott egy 8 bites számunk: 10101101. Ha csak az alsó négy bitet (jobbról négyet) akarjuk megtartani, akkor használjuk az AND műveletet:
10101101 & 00001111 -------- 00001101
Ez hasznos, ha egy adott bitcsoportot akarunk maszkolni, azaz megtartani a kívánt biteket, és lenullázni a többit.
Az OR művelet akkor ad 1-es eredményt, ha legalább az egyik bemenet 1. Ezt a bitek “bekapcsolására” használhatjuk, mert a 0 nem változtatja meg az eredményt, de a 1-es beállítja az adott bitet 1-re.
Igazságtábla:
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Példa: Ha egy bitek közül egyet be akarunk állítani (pl. jobbról a negyediket), és a többit érintetlenül hagyni, akkor használjuk az OR-t:
10101101 | 00001000 ---------- 10101101
Ez hasznos, ha egy konkrét bitet szeretnénk 1-re állítani anélkül, hogy a többi bitet megváltoztatnánk.
Az XOR (kizáró vagy) művelet akkor ad 1-et, ha a bemenetek eltérnek. Ezzel biteket kapcsolgathatunk, azaz ha egy bit értéke 1, akkor 0-ra vált, és fordítva.
Igazságtábla:
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Példa: Ha az alsó 4 bit értékét akarjuk megfordítani:
10101101 ^ 00001111 ---------- 10100010
Tegyük fel, hogy van egy 8 bites regiszterünk: R = 10101101.
Egy bit bekapcsolása (pl. 3. bit):
R = 10101101
Maszk legyen: 00000100
Megjegyzés: a maszkot a gyakorlatban a '«' biteltolás művelettel adják meg, az 1 « 2 művelet az első bitet kettővel balra tolja.
Művelet: R | Maszk
Eredmény:
10101001 | 00000100 ---------- 10101101 (a 3. bit 1 lett)
Egy bit kikapcsolása (pl. 4. bit):
R = 10101101
Maszk legyen: 11110111, a gyakorlatban ezzel adjuk meg: ~(1 « 3)
Megjegyzés: ~(1 « 3) művelet az első bitet kettővel a negyedik helyre (helyiértékre) tolja, majd a '~'-al negálja, azaz megfordítja biteket.
Művelet: R & Maszk
Eredmény:
10101101 & 11110111 ---------- 10100101 (a 4. bit 0 lett)
Maszk legyen: 00000001 (1 « 0)
Művelet: R ^ Maszk
Eredmény:
10101101 ^ 00000001 ---------- 10101100 (a 0. bit megfordult)
Újra alkalmazva ugyanezt a műveletet az új eredményen 10101100:
10101100 ^ 00000001 ---------- 10101101 (a 0. bit megfordult)
Az igazságtáblák és a fenti példák segítségével megérthető, hogyan manipulálhatók a bitek a logikai műveletek segítségével. Ez alapvető fontosságú az alacsony szintű programozásban és a digitális áramkörök tervezésében.
Az XOR műveletnek több hasznos tulajdonsága van:
A XOR 0 = A A XOR 1 = NOT A A XOR A = 0 (A XOR B) XOR B = A
Ezek jelentése:
Az utolsó tulajdonság teszi lehetővé, hogy az XOR műveletet egyszerű titkosításra is használjuk.
Az XOR segítségével könnyen megállapítható, hogy két bináris érték mely bitpozíciókban tér el egymástól.
Legyen a két érték:
10101101 ^ 10000111 ---------- 00101010
Az eredményben ott található 1-es, ahol a két eredeti érték bitjei különböznek. A fenti példában a két szám három bitpozícióban tér el egymástól.
Ez például két hardverregiszter, állapotjelző vagy adatcsomag összehasonlításakor lehet hasznos.
Legyen az üzenetet tartalmazó bájt:
Üzenet: 01000001 Kulcs: 00110110
Az üzenet titkosításához XOR műveletet végzünk:
01000001 üzenet ^ 00110110 kulcs ---------- 01110111 titkosított adat
A titkosított adat visszafejtéséhez ugyanazt a kulcsot ismét alkalmazzuk:
01110111 titkosított adat ^ 00110110 kulcs ---------- 01000001 eredeti üzenet
Ez azért működik, mert:
(Üzenet XOR Kulcs) XOR Kulcs = Üzenet
A kulcs kétszeri alkalmazása megszünteti annak hatását, mivel:
Kulcs XOR Kulcs = 0
és:
Üzenet XOR 0 = Üzenet
A számítógép a szöveg karaktereit is számokként tárolja. Például az A karakter ASCII-kódja 65, amely binárisan:
A = 65 = 01000001
Ha a titkosítási kulcs értéke 54:
Kulcs = 54 = 00110110
akkor a titkosított bájt:
01000001 A karakter ^ 00110110 kulcs ---------- 01110111 titkosított bájt
A visszafejtéskor ugyanezt a kulcsot használjuk:
01110111 ^ 00110110 ---------- 01000001 A karakter
Egy programban az eljárás elvi formája:
titkositott_adat = eredeti_adat ^ kulcs; visszafejtett_adat = titkositott_adat ^ kulcs;
Fontos, hogy az XOR művelet önmagában nem garantál biztonságos titkosítást. Ha rövid vagy könnyen kitalálható kulcsot használunk, illetve ugyanazt a kulcsot sokszor megismételjük, a titkosított üzenet feltörhető lehet.
Az XOR-ra épülő különleges titkosítási módszer a one-time pad, magyarul egyszer használatos kulcs.
A módszer akkor tekinthető tökéletesen biztonságosnak, ha:
A titkosítás:
Titkosított üzenet = Üzenet XOR Kulcs
A visszafejtés:
Üzenet = Titkosított üzenet XOR Kulcs
A gyakorlatban az egyszer használatos kulcs biztonságos továbbítása és tárolása nehéz, ezért a modern titkosítási eljárások általában nem közvetlenül ezt a módszert használják. A folyamtitkosítók azonban hasonló elven működnek: egy kulcsból előállított kulcsfolyamot XOR művelettel kapcsolnak össze az üzenettel.
Az alábbi C program minden karaktert ugyanazzal a kulccsal alakít át:
#include <stdio.h> int main() { char szoveg[] = "HELLO"; char kulcs = 42; for (int i = 0; szoveg[i] != '\0'; i++) { szoveg[i] = szoveg[i] ^ kulcs; } printf("Titkositott adat: "); for (int i = 0; szoveg[i] != '\0'; i++) { printf("%02X ", (unsigned char)szoveg[i]); } for (int i = 0; szoveg[i] != '\0'; i++) { szoveg[i] = szoveg[i] ^ kulcs; } printf("\nVisszafejtett szoveg: %s\n", szoveg); return 0; }
A titkosított adatot hexadecimális számokként jelenítjük meg, mert az XOR művelet eredményeként nem nyomtatható karakterek is keletkezhetnek.
Ez a program csak az XOR működését szemlélteti. Valódi adatok védelmére nem biztonságos, mert minden karakterhez ugyanazt az egybájtos kulcsot használja.
Érdekességként két egész szám értéke ideiglenes változó nélkül is felcserélhető:
a = a ^ b; b = a ^ b; a = a ^ b;
Például legyen:
a = 5 b = 3
Binárisan:
a = 0101 b = 0011
A műveletek:
a = 0101 XOR 0011 = 0110 b = 0110 XOR 0011 = 0101 a = 0110 XOR 0101 = 0011
Az eredmény:
a = 3 b = 5
A modern programokban azonban általában jobb ideiglenes változót vagy beépített felcserélő műveletet használni, mert az érthetőbb és kevésbé hibalehetőséges.
Az XOR művelet egyszerű hibafelismerésre is használható. Több adatbájt XOR műveletével egy ellenőrzőérték képezhető:
ellenorzoertek = adat1 XOR adat2 XOR adat3
Ha valamelyik adatbit megváltozik, általában az ellenőrzőérték is megváltozik. Ezért az XOR műveletet adatátviteli és adattárolási eljárásokban is alkalmazzák.