bitwise XOR (tsz. bitwise XORs)
^) egy bitenkénti kizáró VAGY (exclusive OR, XOR) művelet, amely az alábbi szabály szerint működik:Ez az operátor különösen hasznos titkosításnál, bitmaskok kezelésénél, és két szám gyors cseréjénél.
Példa két bináris szám XOR műveletére:
0101 (5 decimálisan) ^ 0011 (3 decimálisan) ------------ 0110 (6 decimálisan)
🔹 Ahol a két bit különbözik (0 és 1 vagy 1 és 0), ott az eredmény 1.
🔹 Ahol a két bit megegyezik (0 és 0 vagy 1 és 1), ott az eredmény 0.
#include <iostream>
int main() {
int a = 5; // 0101 binárisan
int b = 3; // 0011 binárisan
int c = a ^ b; // XOR művelet
std::cout << c << std::endl; // Kiírja: 6
return 0;
}
Eredmény:
0101 (5) ^ 0011 (3) ------------ 0110 (6)
A XOR operátor segítségével két számot extra változó nélkül cserélhetünk fel:
#include <iostream>
int main() {
int a = 5, b = 3;
a = a ^ b;
b = a ^ b;
a = a ^ b;
std::cout << "a: " << a << ", b: " << b << std::endl;
return 0;
}
Hogyan működik?
1. a = a ^ b → a = 5 ^ 3 → a = 6 2. b = a ^ b → b = 6 ^ 3 → b = 5 3. a = a ^ b → a = 6 ^ 5 → a = 3
Ez egy memóriahatékony trükk, mivel nem használ extra változót!
Ha egy tömbben minden szám párban szerepel, kivéve egyet, akkor az egyedi szám megtalálható XOR segítségével:
#include <iostream>
int findUnique(int arr, int size) {
int unique = 0;
for (int i = 0; i < size; i++) {
unique ^= arr; // Minden számot XOR-olunk
}
return unique;
}
int main() {
int arr = {1, 2, 3, 2, 1};
int size = sizeof(arr) / sizeof(arr);
std::cout << "Egyedi szám: " << findUnique(arr, size) << std::endl;
return 0;
}
Hogyan működik?
- Az XOR törli az ismétlődő értékeket, mert x ^ x = 0.
- Így csak az egyedi szám marad meg.
XOR segítségével egy adott bit állapotát invertálhatjuk:
int flags = 0b1010; // Kezdeti állapot: 1010
flags ^= 0b0100; // Megváltoztatjuk a 3. bitet
std::cout << std::bitset<4>(flags) << std::endl; // Kiírja: 1110
🔹 Ha egy bit 1 volt, 0 lesz.
🔹 Ha egy bit 0 volt, 1 lesz.
A bitwise XOR (^) azokat a biteket állítja 1-re, ahol a két szám különbözik.
Hasznos változók cseréjére, egyedi értékek keresésére, titkosításra és bitmaskok kezelésére.
Matematikailag igaz, hogy:
x ^ x = 0 // Ha ugyanazt az értéket XOR-oljuk önmagával, mindig 0-t kapunk x ^ 0 = x // XOR 0-val nem változtat semmit
A XOR egy erőteljes bitművelet, amely sok optimalizált algoritmus alapja!