Понимание битовой маски для интервью по программированию

Практическое руководство по сложной теме

Вам нужно знать Bit Manipulation и Bitmask для собеседования по программированию?

Эти две темы считаются продвинутыми материалами и «неявно» не требуются для собеседования по кодированию. Тем не менее интервьюер имеет полное право задать вам эти вопросы, если захочет.

Это краткий обзор всех стандартных методов и шаблонов, которые вы должны знать для решения проблем с битовыми масками.

Оглавление

· Основные
∘ Общие операции для битовых манипуляций
∘ Важные операции для битовых масок
· Шаблоны битовых манипуляций
∘ Подсчитайте количество 1 бит в двоичное представление числа
∘ Проверить, является ли положительное число степенью двойки
∘ Эффективно вычислить Pow(x, n), где x › 0 и n › 0
· Шаблон битовой маски
∘ Общий шаблон:
∘ По заданному массиву уникальных элементов найти все возможные подмножества
∘ Посчитать все возможные подмножества размера k, сумма которых к заданной цели
· Вывод

Все коды и уравнения написаны автором.

Базовый

Битовая маска — это идея использования двоичного представления чисел для решения сложных проблем. Это представление уникально для каждого числа.

Пример. Количество битов числа 11 равно "1011", потому что в системе счисления 2:

11 = 8 + 2 + 1 = 1*2³ + 0*2² + 1*2¹ + 1*2⁰= “1011”

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

Общие операции для битовых манипуляций

• Сдвиг влево: чтобы сдвинуть x влево на n пробелов, мы используем x << n. Например, в двоичной форме "1011" << 3 = "1011000" или 11 << 3 = 88.
• Правый Shift: аналогично используем x >> n. Например, "10101" >> 3= "101" (обратите внимание, что единичные биты исчезли).
• Очистить младший установленный бит: x & (x — 1) (например, "10100" -> "10000" )
• И: a & b = 1, если a = 1 И b = 1, иначе 0
• ИЛИ: a | b = 1, если a = 1 ИЛИ b = 1, иначе 0
• XOR: a ^ b = 1, если ровно одно из a или b равно 1, иначе 0
• Для чисел больше 1 мы применяем эти операции итеративно к каждой битовой позиции. Например. "10111" AND "1100" = "00100" = "100"

Важные операции с битовыми масками

• Превратите i^й бит в 1: mask = mask | (1 << i) или mask |= (1 << i)
• Перевернуть i^й бит: mask = mask ^ (1 << i) или mask ^= (1 << i)

Большую часть времени вы будете манипулировать числом под названием mask. Эта маска будет использоваться для отслеживания «используемых» или «неиспользуемых» элементов в списке.

Пример. Учитывая набор из 3 элементов A = {1,2,3}, как мы можем эффективно представить все подмножества этого набора?

Ответ:Используйте числа от 0 до 7 и соответствующие им битовые маски, где каждая 1-битная позиция сигнализирует выбранному элементу:

0 = "000" = {} = the empty set
1 = "001" = {1}
2 = "010" = {2}
3 = "011" = {1, 2}
4 = "100" = {3}
5 = "101" = {1, 3}
6 = "110" = {2, 3}
7 = "111" = {1, 2, 3}

В общем случае, имея набор из n элементов, мы всегда можем представить все подмножества этого набора с помощью чисел от 0 до 2^n — 1.

И это основная идея битовой маски. Мы будем манипулировать mask, представляющим текущее подмножество данного списка.

Шаблоны битовых манипуляций

Подсчитайте количество 1 бит в двоичном представлении числа

Мы можем продолжать сдвигать число вправо, пока оно не станет равным нулю. На каждом шаге мы проверяем, равен ли 0^й бит единице, и добавляем его к общему счету:

Мы можем дополнительно оптимизировать это решение: вместо того, чтобы каждый раз сдвигать на 1 бит, мы можем удалить самый младший установленный бит и сдвинуть соответственно:

Проверить, является ли положительное число степенью двойки

Если n является степенью двойки, то для некоторого положительного целого числа k

Другими словами, двоичное представление n имеет вид "100...0" . Затем мы можем легко проверить это, удалив младший битовый набор n:

Эффективно вычислить Pow(x, n), где x > 0 и n > 0

Рассмотрим двоичное представление n на примере 11:

Обратите внимание, что каждая позиция в двоичном представлении числа 11 соответствует показателю степени x, x², x⁴, …

Таким образом, вместо того, чтобы зацикливаться и умножать n раз для вычисления ответа, мы можем оптимизировать вычисления, сохраняя только степени двойки: x, x², x⁴, x⁸,… и перемножая соответствующие значения, чтобы получить наш окончательный ответ:

Шаблон битовой маски

Напомним, что маска представляет собой подмножество.

Например, у меня есть маска с надписью "00110011".

Что это за число в десятичной форме?

Я не знаю, и мне все равно.

Все, что нам нужно знать, это то, что эта маска представляет собой состояние множества. Эта конкретная маска означает, что мы обрабатываем подмножество элементов с индексами 0, 1, 4 и 5 (идем справа налево).

Общий шаблон:

Что делает этот кусок кода?

Мы перебираем все индексы в наборе. Если мы встретим «неиспользуемый» элемент по индексу i, то соответствующий элемент маски будет "0". Таким образом, not mask по индексу i равно "1", поэтому not mask & (1 << i) вернет True. Затем мы можем добавить этот элемент в наше подмножество и обработать его дальше.

Учитывая массив уникальных элементов, найдите все возможные подмножества

Напомним из предыдущего раздела: при наличии множества размером n мы можем использовать числа от 0 до 2^n-1 для представления всех подмножеств.

Для каждого числа мы создаем соответствующее подмножество, просматривая его двоичное представление и находя положение всех "1". Затем мы можем добавить подмножество к нашему окончательному результату.

Пример вывода:

>>> A = [1,3,5,7]
>>> subset(A)
[[], [1], [3], [1, 3], [5], [1, 5], [3, 5], [1, 3, 5], [7], [1, 7], [3, 7], [1, 3, 7], [5, 7], [1, 5, 7], [3, 5, 7], [1, 3, 5, 7]]

Подсчитайте все возможные подмножества размера k, сумма которых соответствует заданной цели.

Эта задача называется Combination Sum III на Leetcode. Мы хотим найти все подмножества размера k, которые в сумме дают n, такие что:

• Используются только номера с 1 по 9.
• Каждое число используется не более одного раза.

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

Наша начальная маска равна 0, что представляет собой пустой набор (это будет иметь место в 99% случаев). На каждом шаге мы выбираем включение любого бита в позициях от 1 до 9 (справа налево, с начальной позицией, проиндексированной 0).

Например, "1010101010" имеет "1" на позициях 1, 3, 5, 7 и 9. Эта маска представляет набор {1,3,5,7,9} с суммой, равной 25.

Мы можем решить проблему, используя Bitmask и DP. Когда у нас есть набор всех допустимых масок, мы можем декодировать каждую маску и получить окончательный набор чисел.

Вот решение, в котором используются три различных метода манипулирования битами, обсуждаемые в этом посте:

Заключение

Bitmask не должен пугать.

Когда я начал готовиться к собеседованию по программированию, я обнаружил, что битовая маска — самая сложная тема. Сначала я бы вообще пропустил эти вопросы. Однако по мере того, как я решаю все больше и больше проблем, я в конце концов понял, что все не так страшно, как я себе представлял.

Некоторым из моих друзей действительно задавали вопросы о битовой маске во время их интервью (в какой-то Большой Технологии). Уровень сложности аналогичен двум задачам, представленным в разделе «Шаблон битовой маски». Вопросы предполагалось решать с помощью обратного отслеживания. Но решение с помощью битовой маски — отличный способ произвести впечатление на интервьюеров!

(Скорее всего, им это тоже не очень удобно.)

Если вы хотите поддержать четверг, вы можете зарегистрироваться, чтобы стать участником Medium. За 5 долларов в месяц вы получите неограниченный доступ к историям на Medium. Чт также получит небольшую комиссию, если воспользуетесь его реферальной ссылкой.