Битовые маски, подмножества и XOR-трюки

Битовые маски как подмножества, перебор всех подмножеств и XOR-трюки для красивых задач за линейное время.

Битовая маска — целое число, биты которого кодируют принадлежность элементов к подмножеству; перебор масок от 0 до 2ⁿ−1 — это перебор всех подмножеств.

Зачем это в олимпиадах

Битовые маски — мост между «множествами» и «целыми числами», который превращает экспоненциальный перебор в быстрый цикл по числам. На них держится динамика по подмножествам (задача коммивояжёра за O(2ⁿ·n²), раскраски, паросочетания на малых графах). Отдельно стоят XOR-трюки — изящные решения, где побитовое исключающее ИЛИ даёт ответ за один проход. Этот урок собирает воедино биты из предыдущих уроков и показывает, как они решают настоящие олимпиадные задачи.

Перебор всех подмножеств

Множество из n элементов имеет 2ⁿ подмножеств. Каждое подмножество — это маска от 0 до 2ⁿ−1: бит i установлен ⟺ элемент i входит. Перебрать все подмножества — просто пройти числа в этом диапазоне.

items = ["A", "B", "C"]
n = len(items)

for mask in range(1 << n):            # от 0 до 2^n - 1
    subset = [items[i] for i in range(n) if (mask >> i) & 1]
    print(f"{mask:03b}  {subset}")

Вывод:

000  []
001  ['A']
010  ['B']
011  ['A', 'B']
100  ['C']
101  ['A', 'C']
110  ['B', 'C']
111  ['A', 'B', 'C']

Восемь масок — восемь подмножеств трёхэлементного множества, включая пустое (000) и полное (111). Это основа динамики по подмножествам: состояние ДП индексируется маской «какие элементы уже использованы».

Перебор подмножеств заданной маски

Иногда нужно перебрать не все подмножества, а только подмножества конкретной маски (например, подмножества уже выбранных элементов). Есть классический приём: sub = (sub − 1) & mask, стартуя с sub = mask и заканчивая на нуле. Он перечисляет ровно подмножества mask в убывающем порядке, пропуская лишние числа.

mask = 0b1011        # элементы 0, 1, 3

submasks = []
sub = mask
while True:
    submasks.append(sub)
    if sub == 0:
        break
    sub = (sub - 1) & mask

print([format(s, "04b") for s in submasks])
print("Всего подмножеств:", len(submasks))   # 2^(число бит) = 2^3 = 8

Вывод:

['1011', '1010', '1001', '1000', '0011', '0010', '0001', '0000']
Всего подмножеств: 8

Маска 1011 имеет 3 единичных бита, значит у неё 2³ = 8 подмножеств — все перечислены, и все являются подмасками исходной (нет «лишних» единиц). Суммарная сложность перебора подмножеств всех масок — O(3ⁿ), что часто и нужно в ДП.

XOR-трюк: найти два непарных числа

В прошлом уроке XOR нашёл один непарный элемент. Усложним: все числа встречаются дважды, кроме двух разных. XOR всего массива даст a ⊕ b — XOR двух искомых (пары сократились). Как разделить a и b? У a ⊕ b есть хотя бы один единичный бит — позиция, где a и b различаются. Разобьём все числа на две группы по этому биту: в одной окажется a (и пары), в другой b (и пары). XOR внутри каждой группы выделит a и b по отдельности.

from functools import reduce

def find_two_singles(data):
    xor_all = reduce(lambda x, y: x ^ y, data, 0)   # a ^ b
    diff_bit = xor_all & (-xor_all)                  # бит, где a и b различны
    a = b = 0
    for v in data:
        if v & diff_bit:
            a ^= v          # группа с установленным битом
        else:
            b ^= v          # группа без него
    return sorted((a, b))

data = [4, 1, 2, 1, 3, 2, 4, 6]   # непарные: 3 и 6
print(find_two_singles(data))

Вывод:

[3, 6]

XOR всего массива — 3⊕6 = 5 = 101₂; младший различающий бит — 1. Числа с этим битом (нечётные) дают одну группу, остальные — другую, и в каждой группе все, кроме одного непарного, образуют пары. Алгоритм — один проход, O(1) памяти. Это вершина XOR-трюков: разделить два «выживших» элемента по их различающему биту.

Разбор: динамика по подмножествам (идея)

Покажем мощь масок на подсчёте. Сколько способов разбить n элементов на пары (совершенное паросочетание)? Состояние — маска свободных элементов; берём младший свободный и перебираем, с кем его соединить. Это шаблон ДП по битмаскам.

def count_pairings(n):
    from functools import lru_cache
    full = (1 << n) - 1

    @lru_cache(maxsize=None)
    def dp(mask):
        if mask == full:
            return 1
        # найти первый свободный элемент (младший нулевой бит)
        i = 0
        while (mask >> i) & 1:
            i += 1
        total = 0
        for j in range(i + 1, n):
            if not (mask >> j) & 1:           # j тоже свободен
                total += dp(mask | (1 << i) | (1 << j))
        return total

    return dp(0)

for n in (2, 4, 6):
    print(n, count_pairings(n))   # число совершенных паросочетаний = (n-1)!!

Вывод:

2 1
4 3
6 15

Число разбиений на пары равно двойному факториалу (n−1)!! = 1·3·5·…: для 6 элементов это 1·3·5 = 15. Маска «какие элементы уже спарены» — компактное состояние, а перебор по битам — переходы ДП. Так битовые маски превращают экспоненциальный перебор в управляемую динамику.

Разбор задачи: код Грея

Красивое применение битов — код Грея: упорядочивание всех 2ⁿ масок так, что соседние различаются ровно одним битом. Это нужно для последовательного перебора подмножеств с минимальными изменениями состояния (добавили/убрали один элемент), в задачах о переключателях, в аппаратных кодировщиках. Формула обманчиво проста: gray(i) = i ⊕ (i >> 1).

def gray(i):
    return i ^ (i >> 1)

codes = [gray(i) for i in range(8)]
print([format(c, "03b") for c in codes])

# проверим: соседние коды различаются ровно одним битом
def differ_by_one(a, b):
    return (a ^ b).bit_count() == 1

print(all(differ_by_one(codes[i], codes[i + 1]) for i in range(len(codes) - 1)))

Вывод:

['000', '001', '011', '010', '110', '111', '101', '100']
True

Последовательность кодов Грея 000, 001, 011, 010, 110, … действительно меняет ровно один бит на каждом шаге (проверка вернула True). Преобразование i ⊕ (i >> 1) и обратное к нему — изящный мост между обычной нумерацией и «однобитовым» обходом. Это ещё один пример того, как одна битовая операция кодирует нетривиальную комбинаторную структуру.

Подводные камни

Размер маски. 2ⁿ растёт быстро: при n > 20−25 полный перебор масок уже неподъёмен.
Перебор подмасок. Цикл (sub−1)&mask обязан включать sub = 0 в конце и стартовать с sub = mask — иначе пропустите крайние случаи.
XOR двух одиночек. Если непарных чисел не два, а другое количество, базовый трюк не работает — он рассчитан ровно на два.
Низкий приоритет. Всегда оборачивайте (mask >> i) & 1 в скобки в условиях.

Итог

Маски от 0 до 2ⁿ−1 перечисляют все подмножества — основа ДП по подмножествам.
Подмаски маски перебирают через sub = (sub−1) & mask за O(3ⁿ) суммарно.
XOR-трюк находит два непарных числа: XOR всего + разделение по различающему биту.
Битмаски превращают экспоненциальный перебор в динамику с компактным состоянием.