Урок: Битовые операции в Python

📚 Теория: Двоичная система и битовые операции

1. Двоичная система счисления

• Каждое число представляется последовательностью битов (0 и 1)
• Пример: 5 в двоичной = 101 (4 + 0 + 1 = 5)
• В Python можно посмотреть двоичное представление:

bin(5)  # '0b101'
format(5, '08b')  # '00000101' (8 бит)

2. Основные битовые операции

2.1. AND (&) - Побитовое И

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

Пример: 5 & 3 = 101 & 011 = 001 = 1

2.2. OR (|) - Побитовое ИЛИ

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

Пример: 5 | 3 = 101 | 011 = 111 = 7

2.3. XOR (^) - Исключающее ИЛИ

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

Пример: 5 ^ 3 = 101 ^ 011 = 110 = 6

2.4. NOT (~) - Побитовое НЕ

Инвертирует все биты (в Python использует дополнительный код)

2.5. Сдвиги (<<, >>)

• x << n: сдвиг влево на n битов (умножение на 2ⁿ)
• x >> n: сдвиг вправо на n битов (целочисленное деление на 2ⁿ)

🔥 Лайфхаки и полезные трюки

1. Проверка чётности

def is_even(n):
    return (n & 1) == 0

# Пример:
is_even(4)  # True (100 & 001 = 000)
is_even(5)  # False (101 & 001 = 001)

2. Проверка степени двойки

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

# Пример:
is_power_of_two(16)  # True
is_power_of_two(15)  # False

3. Умножение/деление на степень двойки

# Умножение на 2^n
def multiply_by_power_of_two(x, n):
    return x << n

# Деление на 2^n (целочисленное)
def divide_by_power_of_two(x, n):
    return x >> n

# Пример:
multiply_by_power_of_two(5, 3)  # 5 * 8 = 40
divide_by_power_of_two(40, 3)   # 40 // 8 = 5

4. Получение младшего установленного бита

def get_lsb(n):
    return n & -n

# Пример:
get_lsb(12)  # 12 = 1100, -12 = 0100 (в доп. коде) → 0100 = 4

5. Установка/сброс бита

# Установить i-й бит (нумерация с 0)
def set_bit(n, i):
    return n | (1 << i)

# Сбросить i-й бит
def clear_bit(n, i):
    return n & ~(1 << i)

# Проверить i-й бит
def check_bit(n, i):
    return (n >> i) & 1

# Пример:
n = 5  # 101
set_bit(n, 1)   # 111 = 7
clear_bit(n, 0) # 100 = 4
check_bit(n, 2) # 1 (бит установлен)

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

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)  # сбрасываем младший установленный бит
        count += 1
    return count

# Встроенная функция:
bin(5).count('1')  # 2

📝 Практические задачи

Задача 1: Одиночное число

Дан массив, где каждое число встречается дважды, кроме одного. Найдите это число.

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# Пример: [4, 1, 2, 1, 2] → 4

Задача 2: Проверка степени двойки

Напишите функцию, проверяющую является ли число степенью двойки.

def is_power_of_two(n):
    # Ваш код здесь
    pass

Задача 3: Инвертирование битов

Инвертируйте все биты в числе (в заданном диапазоне бит).

def invert_bits(n, num_bits=32):
    mask = (1 << num_bits) - 1
    return n ^ mask

# Пример: invert_bits(5, 4) → 1010 = 10

Задача 4: Найти два уникальных числа

Дан массив, где все числа встречаются дважды, кроме двух чисел. Найдите их.

def find_two_unique(nums):
    xor_all = 0
    for num in nums:
        xor_all ^= num
    
    # Находим младший установленный бит
    lsb = xor_all & -xor_all
    
    # Разделяем числа на две группы
    num1, num2 = 0, 0
    for num in nums:
        if num & lsb:
            num1 ^= num
        else:
            num2 ^= num
    
    return num1, num2

Задача 5: Сумма без сложения

Реализуйте сложение двух чисел используя только битовые операции.

def add_without_plus(a, b):
    while b != 0:
        carry = a & b
        a = a ^ b
        b = carry << 1
    return a

💡 Полезные паттерны

1. Создание маски

# Маска из n единиц
mask = (1 << n) - 1

# Маска для битов i..j
mask = ((1 << (j - i + 1)) - 1) << i

2. Извлечение диапазона битов

def extract_bits(n, i, j):
    mask = ((1 << (j - i + 1)) - 1) << i
    return (n & mask) >> i

3. Установка диапазона битов

def set_bits_range(n, i, j, value):
    mask = ((1 << (j - i + 1)) - 1) << i
    # Очищаем диапазон
    n &= ~mask
    # Устанавливаем новые значения
    n |= (value << i) & mask
    return n

🚀 Оптимизации с битовыми операциями

1. Быстрое вычисление 2ⁿ

# Вместо 2**n используйте:
1 << n  # Быстрее и точнее для целых чисел

2. Проверка наличия общего бита

# Проверить, есть ли общие установленные биты
if (a & b) != 0:
    print("Есть общие биты")

3. Быстрое переключение между 0 и 1

toggle = 0
toggle ^= 1  # Стало 1
toggle ^= 1  # Стало 0

📊 Таблица приоритетов операций

1. ~ (побитовое НЕ)
2. <<, >> (сдвиги)
3. & (И)
4. ^ (исключающее ИЛИ)
5. | (ИЛИ)

🔍 Отладка и визуализация

def print_binary(n, bits=8):
    print(f"{n:3} = {format(n & ((1 << bits) - 1), f'0{bits}b')}")

# Пример использования:
print_binary(5)    #   5 = 00000101
print_binary(~5)   #  -6 = 11111010 (в доп. коде)

🎯 Упражнения для закрепления

1. Реализуйте функцию для обмена значений двух переменных без временной переменной
2. Напишите функцию, возвращающую следующую степень двойки для заданного числа
3. Реализуйте проверку, является ли число палиндромом в двоичном представлении
4. Напишите функцию для циклического сдвига битов влево и вправо
5. Реализуйте умножение двух чисел используя только битовые операции

📌 Итог

Битовые операции — мощный инструмент для:

• Оптимизации вычислений
• Экономии памяти (хранение флагов в одном числе)
• Решения алгоритмических задач
• Низкоуровневого программирования

Помните: читаемость кода важнее микрооптимизаций. Используйте битовые операции там, где они действительно нужны и оправданы!