Битовые маски

Пусть единица на \(i\)-том месте в числе будет отвечать не только за наличие в нем слагаемого \(2^i\), но и за наличие в каком-либо подмножестве \(i\)-го элемента из стороннего набора.

mask	0	1	1	0	1	0
data	2	1	3	9	4	6

Последовательность битов, обозначенная в примере за \(mask\) называется битовой маской.

Битовая маска —– определённые данные, которые используются для маскирования —– выбора отдельных битов или полей из нескольких битов из двоичной строки или числа. В нашем случае это можно интерпретировать как из набора элементов \(\{ 2, 1, 3, 9, 4, 6 \}\) выбирается подмножество \(\{ 1, 3, 4 \}\).

Реализация и применение

Представим, что у нас имеется набор из \(n\) (пусть \(n \leq 10\)) элементов и нам зачем-то нужно перебрать все его подмножества. Поэтому битовая маска должна иметь \(n\) битов, значение каждого из которых будет отвечать за наличие соответствующего элемента в подмножестве.

Теперь нам нужно понять, в какой момент перебор элементов нужно закончить. Если рассматривать маску именно как число, то становится понятно, что перебирать значения нужно в пределах полуинтервала \([0, 2^n)\). Число \(0\) отвечает за пустое подмножество и является самым маленьким числом, которое можно получить с использованием n битов. А \(2^n − 1\) — максимальное число, представимое с помощью тех же \(n\) битов, и отвечающее за подмножество, включающее в себя все \(n\) элементов набора.

Соответственно, перебор всех масок размера \(n\) можно удобно осуществлять путем перебора всех чисел от \(0\) до \(2^n-1\) с помощью простого цикла:

for mask in range(1 << n):
    ...

Остался вопрос — как проверять наличие определенного элемента в подмножестве \(mask\)? Для этого опять стоит вспомнить, что битовая маска представляет из себя просто число, а потому с ней допустимы привычные для чисел операции, в том числе и битовые.

Давайте для проверки наличия \(i\)-го элемента в подмножестве создадим новое число, которое будет иметь единичный бит только на \(i\)-ом месте. Обозначим его за \(x\). Саму проверку будем осуществлять с помощью операции \(AND\): если применить ее к числам \(mask\) и \(x\), то мы получим значение большее нуля только при условии, что в \(mask\) на \(i\)-ом месте стоит единичный бит.

Дополним наш код:

for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):
            # что-то делаем с элементом a[i]

Среди преимуществ перебора с использованием битовых масок есть и весьма очевидные — меньшее использование ресурсов компьютера (у итеративного решения стек рекурсивных вызовов пуст), малый объем кода (если понимать идею масок).

Почему важно уметь писать переборные решения

На большинстве проводимых школьных олимпиад каждая задача разбивается на подзадачи для возможности получения частичных баллов. Поэтому, во-первых, в случае отсутствия идеи для решения задачи на полный балл, написать решение получающее частичный будет лучше, чем получить за нее \(0\).

Вторая причина, вероятно, более весомая. Используя переборное решение можно найти ошибку в оптимальном при помощи стресс-теста. Да, его не для любой задачи написать можно легко и быстро, но пренебрегать такой возможностью не стоит.

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

Пример

Дан массив \(a\) из \(n\) целых чисел. Требуется сказать, существует ли подмножество чисел из этого набора, сумма которых равна \(k\).

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = "NO"
for mask in range(1 << n):
    cur_sum = 0
    for i in range(n):
        if mask & (1 << i):
            cur_sum += a[i]
    if cur_sum == k:
        ans = "YES"
        break
print(f"{ans}")

Перебор всех подмасок данной маски

Дана битовая маска \(m\). Требуется эффективно перебрать все её подмаски, т.е. такие маски \(s\), в которых могут быть включены только те биты, которые были включены в маске \(m\).

Сразу рассмотрим реализацию этого алгоритма, основанную на трюках с битовыми операциями:

s = m
while s > 0:
    # можно использовать s
    s = (s - 1) & m

Единственное исключение — подмаска, равная нулю, обработана не будет. Её обработку придётся выносить из цикла.

Разберём, почему приведённый выше код действительно находит все подмаски данной маски, причём без повторений, за \(O\)(их количества), и в порядке убывания.

Пусть у нас есть текущая подмаска \(s\), и мы хотим перейти к следующей подмаске. Отнимем от маски \(s\) единицу, тем самым мы снимем самый правый единичный бит, а все биты правее него поставятся в \(1\). Затем удалим все "лишние" единичные биты, которые не входят в маску \(m\) и потому не могут входить в подмаску. Удаление осуществляется битовой операцией \(\& \ m\). В результате мы "обрежем" маску \(s-1\) до того наибольшего значения, которое она может принять, т.е. до следующей подмаски после \(s\) в порядке убывания.

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

Практические задания

Авторизация