Когда кто-то впервые видит оператор ^ (XOR), обычно реакция такая:
“Эм… это что? Возведение в степень?” 😅
Спойлер: нет. Это побитовая операция "исключающего ИЛИ" (exclusive OR).
Что делает a ^ b?
- Если биты разные → 1
- Если одинаковые → 0
aba ^ b000101011110
Теперь — внимание: XOR обладает магическими свойствами, которые можно использовать, чтобы решать задачи:
🪄 Свойства XOR, которые решают задачи
- a ^ 0 = a — нейтральный элемент
- a ^ a = 0 — самоуничтожение
- Коммутативность: a ^ b = b ^ a
- Ассоциативность: (a ^ b) ^ c = a ^ (b ^ c)
Эти свойства — не просто математика. Это инструменты. Сейчас покажу, как с их помощью решать задачи, которые решают миллионы на LeetCode.
✅ Задача 1: Найти уникальное число в массиве
Условие:
В массиве каждый элемент встречается два раза, кроме одного. Найдите это уникальное число.
Пример:
nums = [4, 1, 2, 1, 2]
# Ответ: 4
Решение:
def single_number(nums):
result = 0
for num in nums:
result ^= num # Накопительный XOR
return result
Объяснение:
- Все пары сократятся: a ^ a = 0
- Уникальное число останется: 0 ^ x = x
💡 O(n) по времени и O(1) по памяти — мечта интервьюера.
✅ Задача 2: Проверка равенства без ==
Да, вы можете проверить a == b, не используя ==, !=, if и других удобств цивилизации.
def is_equal(a, b):
return (a ^ b) == 0 # если XOR даёт 0 — числа одинаковые
print(is_equal(10, 10)) # True
print(is_equal(10, 9)) # False
Объяснение:
- a ^ b == 0 только если a == b
- Можно даже использовать в low-level системах, где == запрещён
🛠 Иногда такой трюк дают на собеседовании, чтобы проверить мышление "внутри процессора".
✅ Задача 3: Найти два уникальных числа в массиве
Условие:
Каждое число в массиве встречается дважды, кроме двух уникальных. Найдите их.
Пример:
nums = [1, 2, 1, 3, 2, 5]
# Ответ: 3 и 5 (в любом порядке)
Решение:
def single_numbers(nums):
xor_all = 0
for num in nums:
xor_all ^= num # результат: a ^ b (два уникальных числа)
# найдём любой установленный бит, по которому они различаются
diff_bit = xor_all & -xor_all
a = 0
b = 0
for num in nums:
if num & diff_bit:
a ^= num # группа с этим битом
else:
b ^= num # группа без этого бита
return a, b
Пояснение:
- Все дубликаты уйдут, останется a ^ b
- Разделим по биту, в котором a и b различаются
- И в каждой группе снова применим XOR
🔍 Часто спрашивают в FAANG. На первый взгляд кажется магией, на деле — чёткий план.
✅ Задача 4: Проверка, является ли массив перестановкой
Условие:
Проверь, содержит ли массив все числа от 0 до n - 1 без повторов. Например:
nums = [2, 0, 1, 3] # -> True
nums = [1, 2, 2, 0] # -> False
Решение через XOR:
def is_permutation(nums):
n = len(nums)
xor_expected = 0
xor_actual = 0
for i in range(n):
xor_expected ^= i
xor_actual ^= nums[i]
return xor_expected == xor_actual
Почему это работает:
- Если массив — полная перестановка от 0 до n-1, их XOR будет одинаковым
- Если есть дубликаты или пропуски — XOR даст другое
📦 Альтернатива set(), но без доп.памяти. Важно: не отлавливает дубликаты и пропуски одновременно — нужен предварительный контроль.
✅ Задача 5: Найти единственное число, которое повторяется три раза, остальные — по одному
Легендарная задача, уже сложнее.
Пример:
nums = [2, 2, 3, 2]
# Ответ: 3
Решение сложное, но красивое: подсчитываем каждый бит по модулю 3.
def single_number(nums):
ones, twos = 0, 0
for num in nums:
ones = (ones ^ num) & ~twos # обновляем единицы
twos = (twos ^ num) & ~ones # обновляем двойки
return ones
Объяснение:
- ones содержит биты, встречающиеся 1 раз
- twos — биты, встречающиеся 2 раза
- при третьем повторе — всё обнуляется
🧠 Это уже уровень "Senior". Если вы такое объясните на собесе — скорее всего, вас сразу зовут в финал.
⚡ Почему XOR любят на собеседованиях
- Он лаконичен и эффективен
- Нет доп.структур — память O(1)
- Требует понимания битов и чисел
- Часто используется в криптографии, сетях и алгоритмах
💬 Заключение
XOR — как швейцарский нож в алгоритмах:
- Простая операция
- Решает сложные задачи
- Делает ваш код компактным и "магическим"
Понимание a ^ b — это почти как первый день после того, как ты научился кататься на велосипеде без рук:
"А что, так можно было?"