Как заменить "тяжёлую артиллерию" арифметики на лёгкую кавалерию битов
Алгоритм работает, но работает медленно?
В коде много *, /, % и прочих "тяжёлых" операций?
Добро пожаловать в мир побитовой оптимизации — старой доброй школы, где даже деление на 2 считается излишеством.
Здесь мы превращаем обычные операции в быстрые, битовые. Плюс — минимум магии, максимум пользы, даже в Python. Да-да, даже в высокоуровневом языке биты — это сила.
🧠 Зачем вообще использовать побитовые операции?
- 🔥 Быстрее: x << 1 почти всегда быстрее, чем x * 2
- 🧵 Легче на CPU: побитовые операции просты для железа
- 🧠 Лучше понимаешь, что под капотом
- ⚙ Используется в системах реального времени, играх, криптографии и компиляторах
🚀 10 реальных задач: от простых до боевых
✅ Задача 1: Умножение на 2, 4, 8
x = 7
print(x * 8) # 56
print(x << 3) # 56 тоже!
- x << n = x * 2ⁿ — обычный сдвиг влево
- << 3 = умножение на 8
💡 Так можно ускорить циклы, если множители — степени двойки.
✅ Задача 2: Деление на 2, 4, 8
x = 36
print(x // 4) # 9
print(x >> 2) # 9
- x >> n = x // 2ⁿ
⚠️ Только для положительных чисел! Отрицательные — отдельная история, Python сохраняет знак.
✅ Задача 3: Проверка чётности
n = 17
if n & 1 == 0:
print("Чётное")
else:
print("Нечётное")
- Последний бит 0 — значит число чётное.
💡 Это работает даже в условиях, где n % 2 дорог.
✅ Задача 4: Умножение на 10 — по-умному
x = 7
res = (x << 3) + (x << 1) # 8x + 2x = 10x
print(res) # 70
- Быстрее, чем x * 10, особенно на слабом железе
🧙 Так компиляторы иногда оптимизируют внутри.
✅ Задача 5: Обнулить младший бит
x = 77 # 0b1001101
res = x & ~1
print(res) # 76 (0b1001100)
- ~1 = 0b...11111110
- & ~1 = делает последний бит 0 (полезно для выравнивания)
✅ Задача 6: Проверка степени двойки
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
Почему работает?
- Степень двойки в двоичном виде — только одна единица
- n - 1 "обнуляет" её и все младшие биты
🧪 Пример:
print(is_power_of_two(8)) # True
print(is_power_of_two(10)) # False
✅ Задача 7: Быстрый min(a, b) и max(a, b) без if
Только для целых чисел — и немного чёрной магии:
def fast_min(a, b):
return b ^ ((a ^ b) & -(a < b))
def fast_max(a, b):
return a ^ ((a ^ b) & -(a < b))
💥 Используется в DSP и embedded, где if медленно (ветвление = зло)
✅ Задача 8: Сравнение с нулём
n = -5
print((n >> 31) & 1) # 1, если n < 0; 0, если n ≥ 0 (на 32 битах)
В Python >> 31 для 32-битного представления — не совсем то же самое, но в C/C++ работает так. В Python можно эмулировать:
sign = int(n < 0)
✅ Задача 9: Быстрое округление вниз до ближайшей степени двойки
def round_down_pow2(n):
p = 1
while p << 1 <= n:
p <<= 1
return p
⏱️ Эффективнее при больших n, чем логарифм или math.pow
✅ Задача 10: Обмен значений без временной переменной
a, b = 5, 9
a = a ^ b
b = a ^ b
a = a ^ b
print(a, b) # 9, 5
💡 Работает через свойство XOR: a ⊕ b ⊕ b = a
🛠 Побитовая таблица "быстрых замен"
⚙️ А стоит ли вообще это использовать в Python?
✔ Если пишете библиотеки, которые требуют скорости
✔ Если работаете с бинарными протоколами
✔ Если хотите тренировать «мышцы алгоритмиста»
✔ Если оптимизируете критические участки кода (напр. в NumPy, Cython, Numba)
❌ Но не стоит злоупотреблять, если понятность важнее микросекунд
📌 Заключение
Побитовые операции — не только для олимпиадников и системщиков. Это:
- 📈 Инструмент для оптимизации
- 🧠 Способ тренировать мозг
- 🧰 Реальный способ улучшить работу алгоритма
Биты — это просто. Главное — начать сдвигаться в нужную сторону. 😉