DSA Interview Prep · Урок

Единственное число и свойства XOR

Урок 2 из 413 шагов

«Единственное число и свойства XOR» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Задача «Одиночное число»

В задаче «Одиночное число» (LeetCode 136) дан массив, в котором каждый элемент встречается ровно два раза, кроме одного. Требуется найти элемент, встречающийся только один раз. Ограничения по времени O(n) и памяти O(1) исключают хеш-таблицы (O(n) памяти) и сортировку (O(n log n) времени или O(n) памяти для сортировки).

Элегантное решение использует XOR. Последовательно примените XOR ко всем элементам. Одинаковые элементы сокращаются (a ^ a = 0), а благодаря коммутативности и ассоциативности XOR все парные элементы исчезают, оставляя только единственный элемент. Это одно из самых изящных решений за O(n) времени и O(1) памяти во всём спортивном программировании.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

# All pairs cancel, leaving the lone element
print(single_number([2, 2, 1]))              # 1
print(single_number([4, 1, 2, 1, 2]))        # 4
print(single_number([1]))                    # 1
print(single_number([7, 3, 5, 3, 7]))        # 5

# Even more concise with functools.reduce
from functools import reduce
from operator import xor
print(reduce(xor, [2, 2, 1]))  # 1

Почему работает XOR: три ключевых свойства

Сила XOR основана на совместном действии трёх алгебраических свойств:

Самообратимость: a ^ a = 0 — одинаковые значения сокращают друг друга
Нейтральный элемент: a ^ 0 = a — XOR с нулём не изменяет значения
Коммутативность и ассоциативность: порядок не имеет значения, как и группировка элементов

Вместе эти три свойства означают, что применение XOR к мультимножеству сводит все элементы, встречающиеся чётное число раз, к 0, оставляя только элементы, встречающиеся нечётное число раз. В задаче «Одиночное число I» ровно один элемент встречается один раз, то есть нечётное число раз, поэтому он и является результатом XOR.

# Demonstrating the three XOR properties
print('Self-inverse: a ^ a = 0')
for a in [5, 13, 255, 0]:
    print(f'  {a} ^ {a} = {a ^ a}')

print('Identity: a ^ 0 = a')
for a in [5, 13, 0, 1024]:
    print(f'  {a} ^ 0 = {a ^ 0}')

print('Commutativity and Associativity:')
a, b, c = 3, 5, 7
print(f'  a^b^c = {a^b^c}')
print(f'  c^a^b = {c^a^b}')  # same result
print(f'  (a^b)^c = {(a^b)^c}')
print(f'  a^(b^c) = {a^(b^c)}')  # same result

Пошаговый разбор «Одиночного числа»

Рассмотрим [4, 1, 2, 1, 2] по шагам, чтобы увидеть сокращение элементов. Применим XOR ко всем элементам: 4 ^ 1 ^ 2 ^ 1 ^ 2. Поскольку XOR коммутативен, переставим элементы: (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Пары сокращаются, и остаётся только 4.

В настоящем алгоритме мы ничего не переставляем, а применяем XOR слева направо. Но итог тот же, поскольку коммутативность и ассоциативность гарантируют, что порядок не влияет на результат. Вы можете мысленно сгруппировать пары в любом месте — все они сократятся.

nums = [4, 1, 2, 1, 2]
result = 0
print(f'Start: result = {result} ({bin(result)})')
for n in nums:
    prev = result
    result ^= n
    print(f'XOR {n:2d}: {bin(prev):8s} ^ {bin(n):6s} = {bin(result):8s} = {result}')
print(f'Final: {result}')  # 4

# Alternative: show pair cancellation
print('\nMath view:')
print('4 ^ 1 ^ 2 ^ 1 ^ 2')
print('= 4 ^ (1^1) ^ (2^2)')
print('= 4 ^  0   ^  0')
print('= 4')

«Одиночное число II»: каждый элемент встречается три раза

«Одиночное число II» (LeetCode 137): каждый элемент встречается три раза, кроме одного, который встречается один раз. Одного XOR недостаточно — пары больше не сокращаются, если элементов три. Вместо этого подсчитайте, сколько раз каждый бит встречается во всех числах. Если бит присутствует в искомом элементе, он вносит вклад 1; в элементах, встречающихся трижды, его вклад равен 3. Для каждого бита возьмите остаток от деления количества на 3, чтобы выделить биты искомого элемента.

Это можно имитировать с помощью двух целочисленных переменных ones и twos, которые работают как побитовый счётчик по модулю 3. Это подход цифровой логики: ones хранит биты, встречавшиеся нечётное число раз по модулю 2, а twos — биты, встречавшиеся дважды по модулю 3.

def single_number_II(nums):
    ones, twos = 0, 0
    for n in nums:
        ones = (ones ^ n) & ~twos   # bits seen 1 mod 3 times
        twos = (twos ^ n) & ~ones   # bits seen 2 mod 3 times
    return ones  # bits seen exactly once

print(single_number_II([2, 2, 3, 2]))    # 3
print(single_number_II([0, 1, 0, 1, 0, 1, 99]))  # 99

# Simpler but O(32) bit-by-bit approach
def single_number_II_simple(nums):
    result = 0
    for bit in range(32):
        total = sum((n >> bit) & 1 for n in nums)
        if total % 3 == 1:
            result |= (1 << bit)
    return result

print(single_number_II_simple([2, 2, 3, 2]))  # 3

«Одиночное число III»: два элемента встречаются по одному разу

«Одиночное число III» (LeetCode 260): два элемента встречаются по одному разу, а все остальные — дважды. Примените XOR ко всем элементам, чтобы получить a ^ b — XOR двух уникальных элементов. Поскольку a ≠ b, в a ^ b есть хотя бы один бит, равный 1. Найдите младший установленный бит числа a ^ b с помощью diff = xor_all & (-xor_all).

Этот бит равен 1 ровно в одном из чисел a и b. Разделите все числа на две группы в зависимости от того, установлен ли этот бит. Примените XOR отдельно к каждой группе: парные элементы сократятся, оставив a в одной группе и b в другой.

def single_number_III(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # xor_all = a ^ b

    diff = xor_all & (-xor_all)  # isolate lowest differing bit

    a = 0
    for n in nums:
        if n & diff:              # group 1: has the diff bit set
            a ^= n
    b = xor_all ^ a              # a ^ b ^ a = b
    return [a, b]

print(sorted(single_number_III([1, 2, 1, 3, 2, 5])))   # [3, 5]
print(sorted(single_number_III([-1, 0])))               # [-1, 0]
print(sorted(single_number_III([0, 1])))                # [0, 1]

Поиск пропущенного числа с помощью XOR

В задаче «Пропущенное число» (LeetCode 268) дан массив из n различных чисел от 0 до n. Требуется найти пропущенное число. Примените XOR ко всем числам массива и ко всем числам от 0 до n. Пары сократятся, и останется пропущенное число. Это даёт O(n) времени и O(1) памяти.

Другой вариант — использовать формулу арифметической суммы: expected = n*(n+1)//2, а затем вычесть фактическую сумму. Оба подхода требуют O(n) времени и O(1) памяти. XOR надёжнее, поскольку позволяет избежать возможного переполнения целого числа в языках с целыми числами фиксированной разрядности.

def missing_number_xor(nums):
    n = len(nums)
    result = n              # start with n (the last expected value)
    for i, num in enumerate(nums):
        result ^= i ^ num   # XOR with both index and value
    return result

def missing_number_sum(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

for nums, expected in [([3,0,1], 2), ([0,1], 2), ([9,6,4,2,3,5,7,0,1], 8)]:
    xor_ans = missing_number_xor(nums)
    sum_ans = missing_number_sum(nums)
    print(f'nums={nums}: XOR={xor_ans}, Sum={sum_ans}, expected={expected}')

Обмен значениями с помощью XOR без временной переменной

XOR позволяет обменять значения двух переменных без временной переменной. Секрет в том, что a ^ b ^ a = b и a ^ b ^ b = a. Выполните три присваивания с XOR: a ^= b, затем b ^= a, а затем a ^= b. После этого a хранит исходное значение b, а b — исходное значение a.

Важное ограничение: этот приём не работает, если a и b ссылаются на одну и ту же область памяти, то есть являются одной и той же переменной. В таком случае a ^= a устанавливает a в 0, и значение теряется. В Питоне распаковка кортежа (a, b = b, a) безопаснее и понятнее. Обмен с помощью XOR в основном полезен в контекстах языка C и встраиваемых систем, где нельзя выделить дополнительную память.

# XOR swap
a, b = 17, 42
print(f'Before: a={a}, b={b}')
a ^= b   # a = 17 ^ 42
b ^= a   # b = 42 ^ (17 ^ 42) = 17
a ^= b   # a = (17 ^ 42) ^ 17 = 42
print(f'After:  a={a}, b={b}')   # a=42, b=17

# The caveat: same variable/reference => broken
c = 99
# If a and b pointed to same value:
c ^= c   # c = 0  (destroyed!)
print(f'Same-variable XOR swap: c={c}')  # 0, not 99

# Pythonic swap: always prefer this
a, b = 17, 42
a, b = b, a   # safe, clear, handles aliases
print(f'Pythonic: a={a}, b={b}')

XOR в хешировании и контрольных суммах

XOR часто используется как строительный блок для контрольных сумм и проверок чётности. Вычисление XOR всех байтов блока данных создаёт однобайтовую контрольную сумму. Если при передаче изменится один бит, контрольная сумма изменится, что позволяет обнаружить ошибку. Это проще, чем CRC, но такой подход обнаруживает все ошибки, затрагивающие один бит.

XOR также используется для контрольной информации RAID-5: для трёх дисков на третьем хранится XOR данных двух других дисков. Если один диск выйдет из строя, применение XOR к оставшимся двум позволит восстановить потерянные данные. Это в точности логика «Одиночного числа», применённая в обратном направлении: диск с контрольной информацией — это «уникальный элемент», кодирующий то, что сокращается при применении XOR ко всем трём элементам.

# Simple XOR checksum
def xor_checksum(data):
    result = 0
    for byte in data:
        result ^= byte
    return result

data = [0x48, 0x65, 0x6C, 0x6C, 0x6F]  # 'Hello' in ASCII
checksum = xor_checksum(data)
print(f'Checksum: {hex(checksum)}')

# Detect corruption
corrupted = data[:]
corrupted[2] ^= 0xFF   # flip all bits of 3rd byte
new_checksum = xor_checksum(corrupted)
print(f'Original checksum: {hex(checksum)}')
print(f'Corrupted checksum: {hex(new_checksum)}')
print(f'Error detected: {checksum != new_checksum}')

# RAID-5 parity recovery
d1 = [1, 0, 1, 1]
d2 = [0, 1, 1, 0]
parity = [d1[i] ^ d2[i] for i in range(4)]
recovered = [parity[i] ^ d2[i] for i in range(4)]  # recover d1
print(f'd1={d1}, parity={parity}, recovered={recovered}')

XOR и задачи о подмножествах

XOR встречается в задачах о подмножествах, когда требуется вычислить XOR всех подмножеств. Важное наблюдение: для n элементов каждый элемент входит ровно в 2^(n-1) подмножеств. Если n > 1, каждый элемент входит в чётное число подмножеств, поэтому его вклад в XOR сокращается. XOR результатов XOR для всех подмножеств равен 0 при n > 1.

При n == 1 единственное непустое подмножество состоит из самого элемента, поэтому результатом XOR для всех подмножеств будет этот элемент. Подобные рассуждения, основанные на свойствах XOR и подсчёте, проверяются в продвинутых задачах на побитовые операции.

from itertools import combinations
from functools import reduce
from operator import xor

def xor_of_all_subsets(arr):
    n = len(arr)
    total_xor = 0
    for r in range(1, n + 1):
        for subset in combinations(arr, r):
            subset_xor = reduce(xor, subset)
            total_xor ^= subset_xor
    return total_xor

# For n > 1, each element appears 2^(n-1) times (even) => cancels
# Result is always 0 for n > 1
for arr in [[1,2,3], [5,7], [1], [1,2,3,4]]:
    result = xor_of_all_subsets(arr)
    predicted = arr[0] if len(arr) == 1 else 0
    print(f'arr={arr}: XOR of all subsets = {result}, predicted = {predicted}')

Шаблон для собеседований: XOR для поиска уникальности

Распознавайте шаблон применения XOR для поиска уникальности, когда в условии сказано: «каждый элемент встречается k раз, кроме одного, который встречается m раз, где остаток от деления m на k не равен 0». При k=2 и m=1 («Одиночное число I») примените XOR ко всем элементам. При k=3 и m=1 («Одиночное число II») подсчитайте биты по модулю 3. При k=2 и m=1, если уникальных элементов два («Одиночное число III»), примените XOR, а затем разделите элементы по младшему отличающемуся биту.

Общий подход для произвольного k состоит в подсчёте общего числа вхождений каждого бита и взятии остатка от деления на k. Если результат не равен нулю, этот бит принадлежит уникальному элементу. Для любого k это даёт алгоритм за O(32n) = O(n) времени и O(1) памяти.

def single_number_k_times(nums, k):
    '''Find the element that appears m times when all others appear k times.'''
    # Count each bit's occurrence and take mod k
    result = 0
    for bit in range(32):
        total = sum((n >> bit) & 1 for n in nums)
        if total % k != 0:
            result |= (1 << bit)
    # Handle negative 32-bit numbers
    if result >= (1 << 31):
        result -= (1 << 32)
    return result

# k=2, element appears once
print(single_number_k_times([2,2,1], 2))         # 1
# k=3, element appears once
print(single_number_k_times([2,2,3,2], 3))       # 3
# k=4, element appears once
print(single_number_k_times([1,1,1,1,7,2,2,2,2], 4))  # 7

Распространённые задачи на собеседованиях с XOR

Помимо семейства задач об одиночном числе, XOR встречается в следующих часто задаваемых задачах:

«Найти отличие» (LC 389): применить XOR ко всем символам обеих строк; лишний символ останется
«Расстояние Хэмминга» (LC 461): применить XOR к двум числам и подсчитать единичные биты в результате
«Общее расстояние Хэмминга» (LC 477): подсчитать нули и единицы в каждой битовой позиции по всем парам
«XOR-запросы для подмассива» (LC 1310): использовать массив префиксных XOR для запросов по диапазонам

В каждом случае свойство сокращения XOR устраняет избыточность и сокращает полный перебор O(n²) до O(n).

# Find the difference between two strings
def find_the_difference(s, t):
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

print(find_the_difference('abcd', 'abcde'))  # 'e'

# Hamming distance: count differing bits
def hamming_distance(x, y):
    diff = x ^ y
    count = 0
    while diff:
        count += diff & 1
        diff >>= 1
    return count
    # or: bin(x ^ y).count('1')

print(hamming_distance(1, 4))   # 2: 001 vs 100 differ in bits 0 and 2
print(hamming_distance(3, 1))   # 1: 011 vs 001 differ in bit 1

# Prefix XOR for range queries
def xor_queries(arr, queries):
    prefix = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        prefix[i+1] = prefix[i] ^ v
    return [prefix[r+1] ^ prefix[l] for l, r in queries]

print(xor_queries([1,3,4,8], [[0,1],[1,2],[0,3],[3,3]]))

Быстрая проверка

Проверьте, насколько хорошо Вы усвоили понятия из урока «Структуры данных и алгоритмы — подготовка к собеседованию по программированию».

Ответь в интерактивном уроке

Итоги урока

В этом уроке Вы узнали, что свойство самообратимости XOR (a ^ a = 0) приводит к сокращению парных элементов, оставляя только уникальный элемент при применении XOR ко всем числам, что в «Одиночном числе II» используется подсчёт битов по модулю 3, а в «Одиночном числе III» элементы разделяются по младшему отличающемуся биту, и что XOR также позволяет решать задачи о пропущенном числе, поиске отличия, расстоянии Хэмминга и XOR-запросах по диапазонам. Далее мы рассмотрим битовые маски для установки, сброса, инвертирования и проверки отдельных битов.

Можно начать бесплатно

Изучай Python с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы: 30
Уроки: 120

Начать учиться бесплатно Посмотреть полный курс

Часто задаваемые вопросы

Урок «Единственное число и свойства XOR» бесплатный?

Да — полный текст урока «Единственное число и свойства XOR» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Единственное число и свойства XOR»?

Используйте свойство сам обратимости XOR, чтобы найти единственный элемент, встречающийся один раз в списке, где все остальные встречаются дважды, а затем расширьте решение для задач «Единственное чи… Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Единственное число и свойства XOR»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Побитовые операторы: AND, OR, XOR, NOT и сдвиги
Единственное число и свойства XOR
Битовые маски: установить, очистить, инвертировать и проверить
Подсчёт битов, пропущенное число и разворот битов

← Назад к DSA Interview Prep