Алгоритмы с использованием битовой арифметики и комбинаторные алгоритмы

Сегодня мы спустимся ещё ниже по лестнице абстракций и вспомним о минимальной единице информации — одном бите.

Из битов складываются привычные нам байты, килобайты, мегабайты и так далее.

Бит и байт

• Бит (bit) — атомарная единица информации. Может принимать значения 0 или 1.
• Байт (byte) — производная величина. В современных архитектурах 1 байт = 8 бит,
• но исторически встречались варианты, где 1 байт равнялся 7 или даже 9 битам.

Важно помнить: бит — это основа, а байт лишь соглашение архитектуры.

Биты в языках программирования

В высокоуровневых языках (Python, C++, Java) минимальной адресуемой единицей памяти является байт, а не бит.

В C++ нет отдельного типа "бит", но есть тип char, который занимает 1 байт.

В Python можно задавать числа в двоичной системе:

number = 0b00001101
print(number)  # 13

Битовые операции работают с двоичным представлением числа.

Вот их базовый набор (C++ и Python используют одинаковые обозначения):

Пример в Python: работа с битами

a = 5      # 0101
b = 3      # 0011

print("a & b =", a & b)   # Побитовое И → 1
print("a | b =", a | b)   # Побитовое ИЛИ → 7
print("a ^ b =", a ^ b)   # XOR → 6
print("~a =", ~a)         # Побитовое НЕ → -6
print("a << 1 =", a << 1) # Сдвиг влево → 10
print("a >> 1 =", a >> 1) # Сдвиг вправо → 2

Где применяются битовые операции?

1. Оптимизация хранения: например, хранение множества булевых значений в одном числе.
2. Маскирование: выделение отдельных битов для проверки/изменения флагов.
3. Быстрые математические операции: умножение и деление на степени двойки (сдвиг).
4. Комбинаторные алгоритмы:

• представление подмножеств в виде битовых масок;
• генерация комбинаций;
• динамическое программирование по подмножествам.

Мини-пример: использование битовой маски для подмножеств

Например, у нас есть множество {A, B, C}.

Все его подмножества можно закодировать битами:

• 000 → пустое множество
• 001 → {C}
• 010 → {B}
• 011 → {B, C}
• 100 → {A}
• 101 → {A, C}
• 110 → {A, B}
• 111 → {A, B, C}

Код на Python:

elements = ["A", "B", "C"]

n = len(elements)
for mask in range(1 << n):  # 2^n возможных подмножеств
    subset = [elements[i] for i in range(n) if mask & (1 << i)]
    print(f"{mask:03b} -> {subset}")

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