(вторая часть: задачки для тех, кто уже не боится «&» и «^»)
✅ Задача 1: Определить чётность без использования %
Условие:
Проверьте, является ли число n чётным, используя только побитовые операции.
Решение:
def is_even(n):
return (n & 1) == 0 # Если последний бит 0 — число чётное
print(is_even(4)) # True
print(is_even(7)) # False
💡 Почему так: последний бит любого числа отвечает за чётность. 0 — чётное, 1 — нечётное.
✅ Задача 2: Обнулить младший установленный бит
Условие:
Дано число n. Обнулите самый младший установленный бит (самую правую 1).
Пример:
n = 10 → 1010 → после операции → 1000 → 8
Решение:
def clear_lowest_bit(n):
return n & (n - 1)
print(clear_lowest_bit(10)) # 8
🧠 Объяснение:
- n - 1 инвертирует все биты от самой младшей 1 вправо.
- & убирает эту младшую 1, оставляя все остальные.
⚙️ Часто встречается как подзадача в оптимизированных циклах.
✅ Задача 3: Проверить, является ли n степенью четырёх (4^k)
Продолжение классики "проверка степени двойки", но теперь усложним!
Условие:
Проверьте, что n = 4^k, где k >= 0.
Решение:
def is_power_of_four(n):
return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0
print(is_power_of_four(16)) # True
print(is_power_of_four(8)) # False
🔍 Как работает:
- (n & (n - 1)) == 0 — проверка степени двойки
- 0xAAAAAAAA — это маска всех чётных битов, начиная с 2-й позиции (101010...)
- Если n & 0xAAAAAAAA == 0, значит единичка на правильной (нечётной) позиции.
📌 Уровень — middle или выше. Хороший способ проверить не просто знание &, но и масок.
✅ Задача 4: Выделить младший установленный бит как отдельное число
Условие:
Выведите число, в котором только один установленный бит — самый младший из n.
Пример:
n = 12 → 1100 → младший установленный бит = 0100 → 4
Решение:
def extract_lowest_bit(n):
return n & -n # Или n & (~n + 1)
print(extract_lowest_bit(12)) # 4
🔍 Объяснение:
- Отрицательное n (дополнение до двух) инвертирует и прибавляет 1.
- n & -n = битовая маска, где остаётся только младший установленный бит.
⚔️ Часто используется в алгоритмах на деревьях Фенвика (Binary Indexed Tree).
✅ Задача 5: Поменять местами чётные и нечётные биты
Условие:
Дано 32-битное целое число. Нужно поменять местами все чётные и нечётные биты.
Пример:
n = 23 = 00010111 → после свопа → 00101011 = 43
Решение:
def swap_even_odd_bits(n):
even = (n & 0xAAAAAAAA) >> 1 # чётные биты направо
odd = (n & 0x55555555) << 1 # нечётные биты налево
return even | odd
print(swap_even_odd_bits(23)) # 43
🔍 Что за маски:
- 0xAAAAAAAA → 1010... (чётные позиции)
- 0x55555555 → 0101... (нечётные позиции)
🤹♂️ Один из классических трюков, проверяющий владение битовой арифметикой и масками.
✅ Задача 6: Проверить, равны ли два числа без ==
Условие:
Нельзя использовать ==, !=, if. Только побитовые и арифметические операции.
Решение:
def is_equal(a, b):
return (a ^ b) == 0 # Если XOR == 0 → числа равны
print(is_equal(5, 5)) # True
print(is_equal(5, 4)) # False
👀 Иногда встречается на собеседованиях как "мозголомка на логику без условий".
✅ Задача 7: Подсчёт битов в n с использованием lookup-таблицы
Ускоренный способ, когда надо обрабатывать миллионы чисел.
Идея:
Предрассчитать количество установленных битов от 0 до 255 и использовать для 32-битных чисел по 8 бит.
# Таблица из 256 значений
lookup = [bin(i).count('1') for i in range(256)]
def fast_count_bits(n):
return (lookup[n & 0xff] +
lookup[(n >> 8) & 0xff] +
lookup[(n >> 16) & 0xff] +
lookup[(n >> 24) & 0xff])
print(fast_count_bits(12345678)) # Вывод количества битов
🚀 Используется в high-performance системах, где while n: n &= n - 1 уже не тянет.
🧠 Заключение
Как видите, побитовые задачи — это не только x ^ x = 0. Это обширное поле для оптимизаций, трюков, масок и творческого мышления. Такие задачи любят на собеседованиях, где ищут не просто «знающих Python», а понимающих на каком железе всё это крутится.
