Если ты когда-либо слышал: "Реши эту задачу без дополнительной памяти", "Найди уникальный элемент, остальные встречаются дважды", "А ты знаешь, что XOR – это магия?" — добро пожаловать. Эта статья для тебя.
🧪 Немного теории: зачем нужен XOR?
Операция XOR (исключающего ИЛИ) обладает тремя магическими свойствами:
- a ^ a = 0 — число уничтожает само себя.
- a ^ 0 = a — число остаётся неизменным.
- a ^ b ^ a = b — ну… сам посмотри, a уничтожилось.
А теперь — 10 классических, подлых и интересных задач с разбором.
1. 🔎 Найти единственный элемент, встречающийся один раз
Условие:
В массиве каждый элемент повторяется дважды, кроме одного. Найди его.
Решение:
public class SingleNumber {
public static int findSingle(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num; // поочередно применяем XOR
}
return result;
}
public static void main(String[] args) {
System.out.println(findSingle(new int[]{2, 3, 2, 4, 4})); // 3
}
}
🧠 2 ^ 2 = 0, 4 ^ 4 = 0, 0 ^ 3 = 3 — магия!
2. 🎭 Найти два уникальных числа, остальные повторяются дважды
Условие:
Найти два числа, которые встречаются по одному разу. Остальные — по два.
Решение:
public class TwoUniqueNumbers {
public static int[] findTwo(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
// получаем младший разряд, где числа отличаются
int diffBit = xor & -xor;
int a = 0, b = 0;
for (int num : nums) {
if ((num & diffBit) == 0)
a ^= num;
else
b ^= num;
}
return new int[]{a, b};
}
public static void main(String[] args) {
int[] result = findTwo(new int[]{1, 2, 3, 2, 1, 4});
System.out.println(result[0] + ", " + result[1]); // 3, 4
}
}
💡 Разделяем по биту, где числа различаются — и применяем магию XOR в обеих группах.
3. 🔄 Поменять местами два числа без третьей переменной
int a = 5, b = 10;
a ^= b;
b ^= a;
a ^= b;
System.out.println("a = " + a + ", b = " + b); // a = 10, b = 5
🤹 Это как фокус с монетками. Только в коде.
4. 🧩 Проверить, имеют ли два числа противоположные знаки
public class OppositeSigns {
public static boolean hasOppositeSigns(int x, int y) {
return (x ^ y) < 0;
}
public static void main(String[] args) {
System.out.println(hasOppositeSigns(4, -5)); // true
}
}
🧠 Разные знаки → старший бит (знак) будет различаться → XOR даст отрицательное число.
5. 🎚 Проверить, является ли число степенью двойки
public class PowerOfTwo {
public static boolean isPowerOfTwo(int x) {
return x > 0 && (x & (x - 1)) == 0;
}
public static void main(String[] args) {
System.out.println(isPowerOfTwo(16)); // true
System.out.println(isPowerOfTwo(18)); // false
}
}
💡 Только у степеней двойки один бит установлен → x & (x-1) == 0
6. 🧮 Подсчитать количество установленных битов (единиц) в числе
public class CountBits {
public static int countBits(int x) {
int count = 0;
while (x != 0) {
x &= (x - 1); // сбрасываем младший установленный бит
count++;
}
return count;
}
public static void main(String[] args) {
System.out.println(countBits(15)); // 4 (1111)
}
}
🧠 Каждый x & (x-1) удаляет одну единичку. Удобно и быстро.
7. 🔁 Циклический XOR от 1 до N
Задача:
Найти 1 ^ 2 ^ ... ^ n за O(1)
public class XORFrom1ToN {
public static int xorUpto(int n) {
switch (n % 4) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
case 3: return 0;
}
return -1; // теоретически unreachable
}
public static void main(String[] args) {
System.out.println(xorUpto(5)); // 1
}
}
📈 Это известный трюк: XOR всех чисел от 1 до N повторяется с периодом 4.
8. 🎰 XOR подмассива в массиве от i до j
public class RangeXOR {
public static int rangeXor(int[] prefixXor, int i, int j) {
return i == 0 ? prefixXor[j] : prefixXor[j] ^ prefixXor[i - 1];
}
public static void main(String[] args) {
int[] nums = {3, 8, 2, 6};
int[] prefix = new int[nums.length];
prefix[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] ^ nums[i];
}
System.out.println(rangeXor(prefix, 1, 3)); // 8 ^ 2 ^ 6 = 12
}
}
📦 Префиксные XOR-ы — наше всё. Готовься к задачам на интервалы.
9. 🧊 Перестановка массива в XOR стиле
Задача:
Имея массив [a1 ^ a2, a2 ^ a3, ..., a(n-1) ^ a(n)], и одно из чисел, восстанови все остальные.
Пример:
// Исходный массив: [a1=5, a2=7, a3=9]
// XOR массив: [5^7=2, 7^9=14]
public class RestoreArray {
public static int[] restore(int[] xorArr, int knownValue) {
int[] original = new int[xorArr.length + 1];
original[0] = knownValue;
for (int i = 1; i < original.length; i++) {
original[i] = xorArr[i - 1] ^ original[i - 1];
}
return original;
}
public static void main(String[] args) {
int[] result = restore(new int[]{2, 14}, 5);
for (int x : result) System.out.print(x + " "); // 5 7 9
}
}
🧙 Просто идём по цепочке: a2 = a1 ^ x1, a3 = a2 ^ x2...
10. 🎉 Найти отсутствующее число в массиве от 0 до n
public class MissingNumber {
public static int findMissing(int[] nums) {
int n = nums.length;
int xor = 0;
for (int i = 0; i < n; i++) {
xor ^= i ^ nums[i];
}
return xor ^ n;
}
public static void main(String[] args) {
System.out.println(findMissing(new int[]{0, 1, 3})); // 2
}
}
📌 Если 0^1^2^3 = x, а у нас 0^1^3, то x ^ actual = missing.
🧾 Заключение
XOR — это швейцарский нож в арсенале программиста. Он помогает:
- Сравнивать без сравнений
- Менять местами без временных переменных
- Искать уникальные элементы без лишней памяти
- Делать магию в интервальных задачах
- Поражать воображение интервьюеров (и коллег)
Вот краткая шпаргалка по применению XOR из этой статьи:
👨🏫 Что спросить на собеседовании с XOR?
Если ты интервьюер (или хочешь его удивить), вот несколько каверзных вопросов:
- Почему a ^ a == 0 работает только с побитовым XOR, но не с ^ в некоторых языках?
- Можно ли использовать XOR для проверки палиндрома?
- Как XOR применим в хешировании?
- В чём подвох при использовании XOR на отрицательных числах?
⚙️ Практика и ещё практика
На этом всё! Но если хочешь закрепить:
- Попробуй решить все эти задачи без подсказок.
- Напиши юнит-тесты к каждому случаю.
- Реализуй всё на другом языке (например, Kotlin или Python).
🧩 Помни: XOR — это как нож — в умелых руках режет код и ускоряет алгоритмы. А в неумелых — просто непонятные циферки.
Удачи на собеседованиях и да прибудет с тобой битовая магия!