Что такое bitmask и операции с битами?

Bitmask — представление множества через биты integer: каждый бит — наличие/отсутствие элемента.

mask | (1 << i)    # set бит i (добавить элемент)
mask & ~(1 << i)   # clear бит i (убрать)
mask ^ (1 << i)    # toggle бит i
(mask >> i) & 1    # check бит i
a | b              # union
a & b              # intersection
(a & b) == a       # a — subset of b

# Итерация всех subsets множества mask
sub = mask
while True:
    process(sub)
    if sub == 0:
        break
    sub = (sub - 1) & mask

Bit tricks: x & (x-1) обнуляет младший бит (Brian Kernighan для popcount), x & -x — младший set бит. Применения: Subsets (78, iterate masks 0..2ⁿ-1), Travelling Salesman Held-Karp (DP[mask][v]), status flags. Для n ≤ 64 — long long, для больших — bitset (C++) / Python int (arbitrary precision).