Приёмы работы с битами

Практические приёмы работы с отдельными битами: проверить, установить, снять, переключить, найти младший бит и сосчитать единицы.

Все операции с одним битом строятся из маски 1 << i — числа, у которого единственный единичный бит на позиции i.

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

Когда число используют как набор флагов или как подмножество (битовая маска), нужно уметь мгновенно манипулировать отдельными битами: «включён ли элемент i в множество», «добавить элемент», «убрать», «сколько элементов в множестве». Эти микрооперации — кирпичики динамики по подмножествам, переборов с отсечениями, компактного хранения состояний. Знать их наизусть так же важно, как таблицу умножения: на олимпиаде нет времени выводить их заново.

Проверка, установка, снятие, переключение бита

Все четыре операции используют маску 1 << i:

x = 0b1010          # биты 1 и 3 установлены (= 10)
i = 2

print((x >> i) & 1)         # проверка бита 2: он 0
print(bin(x | (1 << i)))    # установить бит 2 -> 0b1110
print(bin(x & ~(1 << 1)))   # снять бит 1     -> 0b1000
print(bin(x ^ (1 << 3)))    # переключить бит 3 -> 0b10 (сняли)

Вывод:

0
0b1110
0b1000
0b10

Запомните паттерн: | ставит, & ~ снимает, ^ переключает, >> & 1 проверяет. Маска 1 << i — общий знаменатель. Эти выражения работают и в Python, и в C++ практически без изменений.

Младший установленный бит

Красивый трюк: x & (−x) выделяет самый младший единичный бит числа. Почему? В дополнительном коде −x = ~x + 1: инвертирование с прибавлением единицы оставляет младший единичный бит на месте, а всё ниже превращает в нули, всё выше инвертирует. AND оставляет ровно этот бит. Этот приём — сердце дерева Фенвика (BIT), которое вы встретите в курсе алгоритмов.

def lowest_bit(x):
    return x & (-x)

print(lowest_bit(0b101100))      # 0b100 = 4 (младший единичный бит)
print(bin(lowest_bit(12)))       # 12 = 1100 -> младший бит 0b100
print(lowest_bit(0b1000))        # 8 — само число, если бит один

# снять младший установленный бит: x & (x-1)
print(bin(0b101100 & (0b101100 - 1)))   # убрали младший бит

Вывод:

4
0b100
8
0b101000

Парный трюк x & (x − 1) снимает младший единичный бит. Его повторное применение, пока число не обнулится, — способ перебрать все установленные биты или сосчитать их (алгоритм Кернигана).

Подсчёт установленных битов

Сколько единиц в двоичной записи? В Python проще всего x.bit_count() (или bin(x).count('1')). Но полезно знать алгоритм Брайана Кернигана: повторяем x &= x − 1, пока x не станет нулём, считая итерации — каждая снимает один бит. Он делает ровно столько шагов, сколько единичных бит, а не log x.

def popcount_kernighan(x):
    count = 0
    while x:
        x &= x - 1        # снять младший единичный бит
        count += 1
    return count

print(popcount_kernighan(0b101100))   # 3 единицы
print((0b101100).bit_count())         # встроенный способ
print([n.bit_count() for n in range(8)])  # популяция битов 0..7

Вывод:

3
3
[0, 1, 1, 2, 1, 2, 2, 3]

Разбор задачи: число как множество флагов

Битмаска компактно кодирует подмножество. Пусть есть 5 предметов, и маска x хранит, какие выбраны. Соберём список выбранных индексов, добавим предмет, уберём другой — всё через битовые операции.

items = ["хлеб", "молоко", "яйца", "сыр", "масло"]
mask = 0b01010              # выбраны индексы 1 (молоко) и 3 (сыр)

# какие предметы выбраны?
chosen = [items[i] for i in range(len(items)) if (mask >> i) & 1]
print(chosen)

mask |= (1 << 0)            # добавить хлеб (бит 0)
mask &= ~(1 << 3)           # убрать сыр (бит 3)
chosen = [items[i] for i in range(len(items)) if (mask >> i) & 1]
print(chosen)
print(mask.bit_count(), "предмета в корзине")

Вывод:

['молоко', 'сыр']
['хлеб', 'молоко']
2 предмета в корзине

Маска заменила список булевых флагов одним целым числом: проверка, добавление и удаление — за одну операцию. Так состояние «какие из n предметов выбраны» хранится в одном int, что критично для динамики по подмножествам (следующий урок).

Разбор задачи: степень двойки и округление вверх

Битовые трюки дают мгновенные ответы на вопросы о степенях двойки. Проверка «является ли x степенью двойки» — это x > 0 and (x & (x−1)) == 0: у степени двойки ровно один единичный бит, и снятие младшего бита обнуляет число. А «ближайшая степень двойки не меньше x» нужна для размеров хеш-таблиц, сегментных деревьев, выравнивания. Через длину битов это 1 << (x−1).bit_length().

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

def next_power_of_two(x):
    if x <= 1:
        return 1
    return 1 << (x - 1).bit_length()   # наименьшая степень двойки >= x

print([n for n in range(1, 17) if is_power_of_two(n)])
print(next_power_of_two(5), next_power_of_two(8), next_power_of_two(17))

Вывод:

[1, 2, 4, 8, 16]
8 8 32

Степени двойки до 16 — это 1,2,4,8,16, как и должно быть. Округление вверх: для 5 это 8, для уже точной степени 8 — само 8, для 17 — 32. Хитрость (x−1).bit_length() корректно обрабатывает точные степени (иначе для 8 получили бы 16). Эти однострочники — повседневный инструмент при работе со структурами, требующими размеров-степеней двойки.

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

• Скобки вокруг битовых выражений. Из-за низкого приоритета пишите (x >> i) & 1, а не x >> i & 1 в сложных условиях.
• Снятие бита. x & ~(1 << i); не путайте с x ^ (1 << i) (переключение): второе установит бит, если его не было.
• Младший бит и знак. x & (−x) опирается на дополнительный код; в Python работает корректно для положительных x.
• Индексация бит. Биты нумеруют с нуля справа; не сместите на единицу.

Итог

• Маска 1 << i — основа: проверка (x>>i)&1, установка x|маска, снятие x&~маска, переключение x^маска.
• x & (−x) выделяет младший бит, x & (x−1) его снимает.
• Подсчёт бит: x.bit_count() или алгоритм Кернигана за число единиц.
• Битмаска кодирует подмножество в одном целом — компактно и быстро.