Или как заставить биты двигаться и сделать за нас грязную работу.
Когда мы слышим "битовые сдвиги", в голове сразу всплывают ассемблер, страшные бинарные числа и программисты в чёрных худи, шепчущие n << 1 при луне. Но на самом деле, битовые сдвиги — это мощный и удобный инструмент, который часто используется в задачах на собеседованиях, особенно там, где нужна скорость, компактность и чуть-чуть магии.
В этой статье мы:
- разберём операторы << и >>;
- увидим, как работают сдвиги на пальцах;
- порешаем задачи (и для новичков, и для тех, кто любит "хардкор").
🧮 Основы: что такое побитовые сдвиги?
Python (и другие языки) позволяет вам двигать биты числа влево и вправо:
- x << n — сдвиг влево на n бит. Умножает x на 2^n.
- x >> n — сдвиг вправо на n бит. Делит x на 2^n (целочисленно).
Пример 1: Простое умножение и деление
x = 4
print(x << 1) # Сдвигаем влево на 1 (4 * 2 = 8)
print(x >> 1) # Сдвигаем вправо на 1 (4 // 2 = 2)
Комментарии:
- 4 в двоичной — 100
- 4 << 1 → 1000 → это 8
- 4 >> 1 → 10 → это 2
📌 А теперь задачки. От простого к божественному.
✅ Задача 1: Проверить, чётное ли число, без if и %
def is_even(n):
return (n & 1) == 0
Объяснение:
- n & 1 проверяет последний бит числа.
- Если он 1 — число нечётное. Если 0 — чётное.
print(is_even(10)) # True
print(is_even(7)) # False
✅ Задача 2: Умножить на 8 без *
def multiply_by_eight(n):
return n << 3 # 2^3 = 8
Почему это работает:
- Сдвиг влево на 3 позиции = умножение на 2³ = 8
print(multiply_by_eight(5)) # 40
✅ Задача 3: Найти уникальное число в списке, где остальные дублируются
def find_unique(nums):
result = 0
for num in nums:
result ^= num
return result
Что происходит:
- XOR (^) — суперспособность.
- a ^ a = 0, a ^ 0 = a
- Все дубликаты "взаимоуничтожаются", остаётся уникальный элемент.
print(find_unique([2, 3, 2, 4, 4])) # 3
✅ Задача 4: Подсчитать количество установленных битов (единичек)
def count_bits(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
Пояснение:
- n & 1 проверяет, установлен ли младший бит.
- n >>= 1 сдвигает число вправо (убираем младший бит).
- Повторяем, пока не обнулим всё число.
print(count_bits(7)) # 3, потому что 111
print(count_bits(8)) # 1, потому что 1000
✅ Задача 5 (профи): Переставить биты в числе в обратном порядке
def reverse_bits(n, bits=32):
result = 0
for i in range(bits):
result <<= 1
result |= (n >> i) & 1
return result
Что происходит:
- Мы берём каждый бит n, начиная с младшего (справа).
- Кладём его в result слева.
- Получается "перевёрнутая" битовая строка.
print(bin(reverse_bits(0b00000000000000000000000000000101))) # → '0b10100000000000000000000000000000'
🛠 Зачем вообще это всё?
Побитовые сдвиги и операции:
- Ускоряют выполнение (умножения и деления — медленные операции).
- Часто нужны в работе с флагами, битовыми масками, компрессией.
- Важны в задачах по алгоритмам, безопасности, low-level разработке.
😄 Заключение
Побитовые сдвиги — это не страшный динозавр из прошлого, а швейцарский нож для оптимизации и решения изящных задач. Они делают код компактнее, быстрее и иногда просто прикольнее.
💡 Совет: если хочешь стать разработчиком, который не боится ни LeetCode, ни продакшена, — учи и практикуй побитовые штуки. Да, иногда тебе кажется, что ты больше электрик, чем программист, но зато как красиво!
