XOR. Побитовые операции в олимпиадном программировании.

Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, у меня возникли трудности при работе с побитовой операцией XOR. Я сделал вывод, что мне нужно освежить свои знания по теме побитовых операций, т. к. эта тема часто встречается в задачах и нуждается в глубоком понимании.

Чтобы понять эту тему, я зашёл на LeetCode, где зашёл в список задач и вбил XOR. Задача решить 3 задачи Easy и 1 Medium.

Теория

Побитовые операции - это операции над числами в двоичной системе счисления, где мы поочередно работаем с каждым битом.

Операции:

• Побитовое отрицание (НЕ). Каждый бит меняет значение. Применяется для одного числа. Число 101001011 станет 010110100.
• Побитовое "И" (AND). Операция для двух чисел. Единичка ставится только в том случае, если у каждого из чисел стоит 1. Во всех остальных случаях 0.
• Побитовое "ИЛИ" (OR). Операция для двух чисел. Единичка ставится в случае, если у нас есть хотя бы одна 1. Если две единицы, то пишется 1.
• Побитовое исключающее "ИЛИ" (XOR). Самая сложная и часто встречающаяся в задачах побитовая операция. Единичка ставится только в том случае, когда числа разные. Если 0 0 или 1 1, то ставится 0, если 1 0 или 0 1, то ставится 1.
• "Анти XOR" (XNOR). По большому счёту это операция XOR, на результат которой применили операцию НЕ.

Таблица с наглядной демонстацией вышенаписанного

У XOR есть некоторые свойства, которые мы будем применять в ходе решения задач:

• a XOR 1 = НЕ a
• a XOR a = 0
• a XOR b = b XOR a
• (a XOR b) XOR c = a XOR (b XOR c)
• (a XOR b) XOR b = a
• Если a XOR b = c, то a XOR c = b (Очень непопулярное, но определённо точно очень полезное)

В языке программирования Python и C++

a XOR b можно записать как a ^ b

Теперь можно перейти к решению задач.

1486. XOR Operation in an Array

Условие задачи можете посмотреть по ссылке.

Чтобы найти XOR массива, то нам нужно просто найти XOR всех его элементов поочередно.

Т. е. у нас есть массив a = [a1, a2 ... ai] и XOR массива мы можем посчитать так:

Запись XOR ^= a[i] аналогична записи XOR = XOR ^ a[i]

В рамках нашей задачи нам даже не обязательно создавать массив. Изначально XOR будет равен start, при этом a[i] = start + 2 * i.

Таким образом мы и решим эту задачу.

1720. Decode XORed Array

При решении этой задачи нам пригодится одно из свойств XOR, а именно тот факт, что если a XOR b = c, то a XOR c = b.

Таким образом выглядит моё решение на LeetCode.

Зная это свойство, задача становится очень простой.

1863. Sum of All Subset XOR Totals

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

Функция получилась рекурсивная.

2429. Minimize XOR

Переходим к задаче уровня Medium

 Здесь уже не получится обойтись одной лишь операцией ^, придётся залезать в двоичную систему счисления.

В первую очередь нам нужно понять из каких чисел состоит nums2. Для этого мы встроенной функцией переведём его в двоичную систему счисления, после чего из двоичного числа сделаем строку и вырежем первые два символа. Потом мы посчитаем количество нулей и единиц в двоичной записи второго числа.

Первое число мы аналогично переводим в двоичную систему счисления. Затем мы каждой единице у нас должна соответствовать единица, а нулю - ноль. Могут закончится числа и это будет обидно. Тогда просто вставляем то, что осталось. Задача на самом деле достаточно простая.

На этом всё. Спасибо за прочтение.