Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, у меня возникли трудности при работе с побитовой операцией 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 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]](https://avatars.dzeninfra.ru/get-zen_doc/1567436/pub_6370c0374fdcbe14d1ba0161_6370c5a9cbf5170d14d70257/scale_1200)
В рамках нашей задачи нам даже не обязательно создавать массив. Изначально XOR будет равен start, при этом a[i] = start + 2 * i.
Таким образом мы и решим эту задачу.
1720. Decode XORed Array
При решении этой задачи нам пригодится одно из свойств XOR, а именно тот факт, что если a XOR b = c, то a XOR c = b.
Зная это свойство, задача становится очень простой.
1863. Sum of All Subset XOR Totals
Эту задачу я решил с помощью бектрекинга. Как мы видим, максимальна длина массива равна 20 элементам, что очень немного. Поэтому такой метод вполне сойдёт. Мы тупо сгенерируем все возможные подмножества, для каждого посчитаем XOR и сложим их.
Функция получилась рекурсивная.
2429. Minimize XOR
Переходим к задаче уровня Medium
Здесь уже не получится обойтись одной лишь операцией ^, придётся залезать в двоичную систему счисления.
В первую очередь нам нужно понять из каких чисел состоит nums2. Для этого мы встроенной функцией переведём его в двоичную систему счисления, после чего из двоичного числа сделаем строку и вырежем первые два символа. Потом мы посчитаем количество нулей и единиц в двоичной записи второго числа.
Первое число мы аналогично переводим в двоичную систему счисления. Затем мы каждой единице у нас должна соответствовать единица, а нулю - ноль. Могут закончится числа и это будет обидно. Тогда просто вставляем то, что осталось. Задача на самом деле достаточно простая.
На этом всё. Спасибо за прочтение.
