Исключающее «или»

У исключающего «или» есть свойства, которых нет у «и» и «или», и из-за них оно встречается в задачах гораздо чаще.

свойство	запись
само себе обратно	$a \oplus b \oplus b = a$
коммутативно	$a \oplus b = b \oplus a$
ассоциативно	$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
нейтральный элемент	$a \oplus 0 = a$
каждый элемент обратен себе	$a \oplus a = 0$

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

Напарник определён однозначно

Из обратимости: если $a \oplus b = k$, то $b = a \oplus k$. Значит, задача «найти пары с заданным XOR» — это не перебор пар, а поиск:

long long answer = 0;
std::unordered_map<int, int> seen;
for (int x : a) { answer += seen[x ^ k]; seen[x]++; }

Тот же приём: «найти единственный элемент, встречающийся один раз, когда все остальные по два» — это XOR всего массива. И «найти пропущенное число» — XOR всех чисел от 1 до n с XOR массива.

Связь со сложением

$$a + b = (a \oplus b) + 2(a ;\&; b).$$

Сложение отличается от исключающего «или» ровно переносами, а переносы порождаются общими битами. Из этого тождества выводится половина задач про XOR.

Например, уравнение $a - (a \oplus x) - x = 0$ равносильно $a \oplus x = a - x$; подставив тождество, получаем $x = a ;\&; x$, то есть $x$ — подмаска $a$. Решений ровно $2^{\mathrm{popcount}(a)}$.

Ещё следствие: $a \oplus b \le a + b$ всегда, и равенство достигается тогда и только тогда, когда у чисел нет общих битов.

Жадность по старшему биту

Старший бит важнее всех младших вместе взятых: $2^k > 2^{k-1} + \ldots + 1$. Поэтому задачи «максимизировать XOR» решаются жадно сверху вниз: если очередной бит можно сделать единицей, это надо сделать.

Проверка «можно ли» делается множеством префиксов или бором по битам:

int node = root, answer = 0;
for (int bit = 29; bit >= 0; bit--) {
    int want = ((x >> bit) & 1) ^ 1;             // хотим противоположный бит
    if (child[node][want]) { answer |= 1 << bit; node = child[node][want]; }
    else node = child[node][want ^ 1];
}

Важно: жадность с младшего бита неверна. Проверено перебором: на 120 000 случайных наборов из нескольких чисел до шести битов такая жадность разошлась с настоящим максимумом в 35 934 случаях. Например, на наборе $0, 1, 3, 0, 0, 5$ она даёт 3 вместо 6.

Смежное

• Линейный базис по XOR;
• Код Грея;
• Ним и функция Гранди.