Битовая маскировка, которую многие часто называют бит-магией, не так страшна, как многие думают.
Я наблюдал, как мои коллеги жалуются на повторяющиеся проблемы с TLE’S (превышение временного лимита) и проблемы с пространственной сложностью при запуске их кодов. Вот тут-то на помощь приходит Bit-Magic.
В этой серии из двух частей я поделюсь своими нынешними знаниями о битовой маскировке и о том, как она помогает оптимизировать алгоритмы (причина, по которой она также известна как Bit-Magic).
В этой части дается базовая интуиция, лежащая в основе побитового маскирования и как манипулировать различными битами, а в следующей части я буду обсуждать некоторые сложные проблемы, которые можно решить и оптимизировать с помощью битовой маскировки вместе с динамическим программированием.
В этой статье я буду обсуждать следующее:
· Биты и битовая маскировка: Введение.
· Побитовые операторы.
· Практическое побитовое маскирование.
На статью !!
Биты и битовая маскировка: введение.
Бит - это одно логическое значение (0 или 1), небольшой набор (а) которых составляет битовую маску. Бит считается установленным тогда и только тогда, когда он равен «1». Например: в 10011 установлены 1-й, 2-й и 5-й биты, а 3-й и 4-й - не .
«Маска» в битовой маске может пониматься как способ скрыть / показать некоторую информацию. Давайте рассмотрим базовый пример, чтобы понять это более тщательно. Предположим, у нас есть набор из 5 символов {‘a’, ‘b’, ‘c’, ‘d’, ‘e’}, и мы хотим сделать из них разные строки. Здесь мы создадим маску из 5 бит (_ _ _ _ _), где каждый бит сообщит нам, судим мы этого персонажа или нет. Проще говоря, 10011 будет представлять строку, эквивалентную «ade», 00000 будет представлять пустую строку, 11111 будет относиться к «abcde» и так далее.
Поняв, что такое биты и битовые маски, самое время погрузиться в некоторые операции, которые можно использовать для манипулирования битами.
Побитовые операторы
Оператор И (&): для двух битовых масок оператор «&» даст 1, если установлены оба бита.
Оператор ИЛИ (|): Для двух битовых масок оператор ‘|’ даст 1 всякий раз, когда установлен любой из двух битов.
Оператор XOR (^): для двух битовых масок оператор ‘^’ даст 1, если оба бита различны.
Здесь важно отметить, что XOR любых двух одинаковых чисел всегда будет 0, а XOR любого числа с 0 - это само число.
Можете ли вы вспомнить ситуации, в которых можно применить эту концепцию?
Если да, то вау !! у тебя все хорошо. Если нет, не волнуйтесь, мы обсудим то же самое в следующей части статьи.
Операторы Shift:
Как установить k-й бит числа?
Простой подход к этой проблеме - сначала создать маску, в которой установлен k-й бит.
Мы можем добиться этого, сдвинувшись 1 k раз влево или выполнив (1 ‹---------------- k).
Например: мы должны установить 3 бита в 1000001. 1 ‹---------------- 3 даст нам 1000.
Теперь, чтобы установить 3-й бит (или k-й бит), нам нужно только выполнить операцию ИЛИ числа и маски.
Следовательно, 1000001 | 1000 = 1001001 (с установленным 3-м битом)
Код:
N = N | (1<<k)
Как очистить k-й бит?
Если нам дается задача очистить k-й бит числа (или установить для k-го бита значение 0), мы можем создать маску, в которой все единицы, кроме k-го бита, равны 0. Преимущество, которое мы получаем от этой маски, состоит в том, что, если мы выполним ' & 'с маской, мы получим все биты числа, как есть, с дополнительным преимуществом, что наш k-й бит теперь равен 0. Потому что (0 и любое no) всегда равно 0.
Допустим, у нас есть 1001101, и мы хотим очистить его 3-й бит. Итак, 1 ‹---------------- 3 даст нам 1000, но мы хотим что-то вроде 1110111. Что мы можем сделать ??
Попробуем снять отрицание нашей маски. Итак, ~ (маска) = ~ (1000) = ~ (0001000) = 1110111
Теперь мы можем просто выполнить операцию «&» для числа и маски, чтобы очистить 3-й бит.
Вы узнали о побитовых операторах и о том, как получить доступ к определенному биту путем создания масок, и вот вам простая задача в качестве упражнения.
Q Вам дано число n битов. Установите все биты между k и l равными 1. Возьмите k и l у пользователя. (k ‹l‹ = n)
Поиграйте с этими операторами, чтобы лучше понимать побитовые операции.
Пришло время узнать, как можно использовать создание битов для оптимизации кода. Давайте прыгнем на это !!
Практическое побитовое маскирование:
Все мы знаем, что информация хранится в виде битов в памяти компьютера, а это означает, что прямое манипулирование этими битами даст более быстрые результаты, чем выполнение вычислений с обычными данными.
Хорошо, теперь мы увидим, решив некоторые вопросы, как битовая маскировка на самом деле оптимизирует код.
В. Начнем с простого примера замены двух чисел.
Например: a = 4 (100 в двоичном формате), b = 6 (110 в двоичном формате)
Мы хотим, чтобы в качестве ответа были a = 6 и b = 4.
a = a ^ b (a = 4 ^ 6)
b = a ^ b (b = 4 ^ 6 ^ 6) {и ранее мы видели, что xor тех же чисел равно 0, следовательно, b = 4 (поскольку 6 ^ 6 = 0)}
a = a ^ b (a = 4 ^ 6 ^ 4= 6)
Следовательно, a = 6 и b = 4.
Мы успешно справились с поставленной задачей .. Ура !!
Очевидно, это может быть достигнуто с помощью обычного обмена местами, но использование побитовых операторов приведет к более эффективному по времени коду.
Q Учитывая список целых чисел, где все целые числа встречаются четное время, ожидайте, что одно из них встречается нечетное время. Найдите это целое число.
Например: l = {1,2,2,1,1,4,4,4,5,4,5} наши ans. должно быть 1
При простом методе грубой силы нужно подсчитать, сколько раз каждое целое число присутствует в списке, и вывести целое число, соответствующее нечетному счету. В худшем случае это приведет к временной сложности O (n * k), где k - количество различных элементов.
Давайте попробуем использовать битовую маскировку. Что произойдет, если мы возьмем xor всех элементов?
Взятие xor уничтожит все те числа, которые встречаются четное время (напомним, что XOR тех же чисел = 0), и у нас останется только целое число, которое повторяется нечетное время. Интересно !! Не правда ли ??
Я надеюсь, что теперь вы лучше понимаете это !! Давайте теперь обсудим небольшую сложную проблему.
Q Дана строка, выведите все ее перестановки.
Например: данная строка - «abc». Итак, самая первая мысль, которая нас поразит, - это то, как мы можем получить доступ к каждому символу строки. Помните про маску, которую мы узнали ?? Да, вы поняли !! Здесь мы создадим маску для каждого возможного состояния, и после посещения каждого персонажа мы распечатаем наш ответ. Длина маски, очевидно, будет равна длине веревки.
На каждой итерации мы будем проверять, какие именно биты не установлены, а затем пробовать разные перестановки, устанавливая разные биты на каждой итерации. Если конкретный бит уже установлен, нам не нужно ничего делать, но если это не так, мы должны попробовать все возможные комбинации. Различные состояния маски будут определять, какой будет следующая комбинация.
Эта часть станет более понятной, когда мы перейдем к разделу кодирования для этой проблемы.
Вот код того же:
Надеюсь, теперь у вас есть четкое представление о том, как работает битовая маскировка (или, я бы сказал, битовая магия).
Пришло время поработать над некоторыми интересными задачами.
Моя следующая статья о битовой маскировке будет посвящена более сложным проблемам, связанным с битовой маской наряду с динамическим программированием.
А до тех пор счастливого кодирования :)
Ссылки на некоторые интересные проблемы:
· Https://practice.geeksforgeeks.org/problems/subsets-with-xor-value/0
