Сигнал задачи
Когда применять
Нужно работать с флагами, XOR или малым множеством.
Что держать в голове
- Уметь безопасно строить и применять битовые маски.
- Уметь объяснять инвариант подсчёта установленных битов.
Сложность
- Операция над машинным словом считается O(1); перебор всех масок n элементов требует O(2ⁿ), а просмотр битов каждой маски — O(n · 2ⁿ).
Границы и ошибки
- Сдвиг, знаковость и ширина типа зависят от языка; перед 1 << k проверяйте допустимый диапазон k и нужный тип.