Побитовые операторы в Python

# Конвертация в двоичное представление
number = 42
binary_str = bin(number)  # '0b101010'
print(f"Число {number} в двоичной системе: {binary_str}")
 
# Обратное преобразование
decimal = int('101010', 2)  # 42
print(f"Двоичное 101010 в десятичной: {decimal}")
 
# Работа с форматированием для красивого вывода
formatted = f"{number:08b}"  # '00101010' - 8 бит с ведущими нулями
print(f"С ведущими нулями: {formatted}")

# Побитовая инверсия в Python
x = 5  # 0b0101
result = ~x
print(f"~{x} = {result}")  # -6, а не 250 или 1010
 
# Почему так происходит?
# Python использует формулу: ~x = -(x + 1)
# Это поведение дополнительного кода, но без фиксированной разрядности

# Эмуляция беззнакового 8-битного инверта
x = 5
mask = 0xFF  # 8 бит
unsigned_invert = ~x & mask
print(f"Беззнаковый инверт {x}: {unsigned_invert}")  # 250
 
# Для 16-битного числа
mask_16 = 0xFFFF
unsigned_16 = ~x & mask_16  # 65530

a = 100
b = 100
print(a is b)  # True - это один объект в памяти
 
x = 1000
y = 1000
print(x is y)  # False - разные объекты (но может быть True из-за оптимизаций)
 
# Проверка адреса в памяти
print(f"id(a): {id(a)}, id(b): {id(b)}")

import sys
 
small = 2[B]30
large = 2[/B]100
 
# Размер объекта в памяти
print(f"Размер {small}: {sys.getsizeof(small)} байт")
print(f"Размер {large}: {sys.getsizeof(large)} байт")
 
# Python хранит большие числа как массив 30-битных "цифр"
# Система счисления с основанием 2^30
print(f"Количество бит в {large}: {large.bit_length()}")

from math import factorial
 
huge_number = factorial(100)
print(f"100! = {huge_number}")
print(f"Требуется бит: {huge_number.bit_length()}")  # 525 бит
print(f"Размер объекта: {sys.getsizeof(huge_number)} байт")  # ~88 байт
 
# Для сравнения - сколько "цифр" в системе 2^30
digits_count = (huge_number.bit_length() + 29) // 30
print(f"Количество 30-битных цифр: {digits_count}")  # 18 цифр

# Читаем 4 байта из условного потока
bytes_data = b'\xFF\xFF\xFF\xFF'  # Максимальное 32-битное беззнаковое
 
# Неправильный подход - получим знаковое
def parse_wrong(data):
    result = 0
    for byte in data:
        result = (result << 8) | byte
    return result
 
wrong = parse_wrong(bytes_data)
print(f"Неправильно: {wrong}")  # 4294967295 - правильно по величине
 
# Но если старший бит единица, можем получить проблемы
signed_bytes = b'\x80\x00\x00\x00'
print(f"Со старшим битом: {parse_wrong(signed_bytes)}")  # 2147483648
 
# Правильный подход с явным указанием беззнаковости
import struct
 
# Формат '<I' = little-endian unsigned int
correct = struct.unpack('<I', bytes_data)[0]
print(f"Правильно: {correct}")
 
# Альтернатива через int.from_bytes()
also_correct = int.from_bytes(bytes_data, byteorder='little', signed=False)
print(f"Тоже правильно: {also_correct}")

positive = 8  # 0b1000
negative = -8  # внутри как ...11111000 в дополнительном коде
 
# Проверка третьего бита (индекс 3, считая с нуля)
print(f"Бит 3 в {positive}: {(positive >> 3) & 1}")  # 1
print(f"Бит 3 в {negative}: {(negative >> 3) & 1}")  # 1
 
# Но если сдвинуть дальше
print(f"Бит 10 в {positive}: {(positive >> 10) & 1}")  # 0
print(f"Бит 10 в {negative}: {(negative >> 10) & 1}")  # 1 - всё единицы!
 
# Проверка знака числа через старший "виртуальный" бит
def is_negative_bitwise(n):
    # У отрицательных чисел старший бит всегда 1
    # Сдвигаем на заведомо большое число позиций
    return (n >> 1000) & 1 == 1
 
print(f"-42 отрицательное? {is_negative_bitwise(-42)}")  # True
print(f"42 отрицательное? {is_negative_bitwise(42)}")    # False

# Извлечение младшего байта из 32-битного числа
value = 0x12345678
lower_byte = value & 0xFF  # Маска оставляет только 8 младших бит
print(f"Младший байт: 0x{lower_byte:02X}")  # 0x78
 
# Проверка четности через младший бит
number = 42
is_even = (number & 1) == 0  # Если младший бит 0 - число четное
print(f"{number} четное? {is_even}")
 
# Извлечение RGB компонент из цвета
color = 0xFF5733  # Оранжевый в hex
red = (color >> 16) & 0xFF    # Старший байт
green = (color >> 8) & 0xFF   # Средний байт
blue = color & 0xFF            # Младший байт
print(f"RGB: ({red}, {green}, {blue})")  # (255, 87, 51)

# Установка флагов доступа
READ = 0b0001    # 1
WRITE = 0b0010   # 2
EXECUTE = 0b0100 # 4
 
# Комбинируем права на чтение и запись
permissions = READ | WRITE
print(f"Права: {permissions:04b}")  # 0011
 
# Добавление флага к существующим правам
permissions |= EXECUTE  # Эквивалентно permissions = permissions | EXECUTE
print(f"С выполнением: {permissions:04b}")  # 0111
 
# Построение байта из отдельных бит
byte = (1 << 7) | (1 << 5) | (1 << 0)  # Биты 7, 5 и 0 включены
print(f"Собранный байт: 0b{byte:08b}")  # 0b10100001

# Классический XOR-трюк: обмен значений без временной переменной
a, b = 5, 10
print(f"До обмена: a={a}, b={b}")
 
a ^= b  # a = a ^ b
b ^= a  # b = b ^ (a ^ b) = a
a ^= b  # a = (a ^ b) ^ a = b
 
print(f"После обмена: a={a}, b={b}")
 
# Простейшее "шифрование" XOR
message = "HELLO"
key = 0x55  # Ключ шифрования
 
# Шифруем
encrypted = bytes([ord(char) ^ key for char in message])
print(f"Зашифровано: {encrypted.hex()}")
 
# Расшифровываем тем же ключом (свойство XOR!)
decrypted = ''.join([chr(byte ^ key) for byte in encrypted])
print(f"Расшифровано: {decrypted}")
 
# Поиск единственного уникального элемента в массиве дубликатов
# Все числа повторяются дважды, кроме одного
nums = [2, 3, 5, 2, 3, 7, 5]
unique = 0
for num in nums:
    unique ^= num  # Дубликаты взаимоуничтожатся
print(f"Уникальный элемент: {unique}")  # 7

x = 5  # 0b0101
print(f"~{x} = {~x}")  # -6
 
# Почему -6? В дополнительном коде:
# 5 = ...00000101
[H2]~5 = ...11111010 = -6 в дополнительном коде[/H2]
 
# Для получения "нормальной" инверсии нужна маска
mask_8bit = 0xFF
inverted_8 = ~x & mask_8bit
print(f"8-битная инверсия {x}: {inverted_8}")  # 250 (0b11111010)
 
# Проверка: инверсия + исходное = все единицы
print(f"{inverted_8} + {x} = {inverted_8 + x}")  # 255 (0xFF)

# Сброс битов 2 и 3 (считая с нуля)
value = 0b11111111  # Все биты включены
mask = 0b00001100   # Биты, которые хотим сбросить
 
# Инвертируем маску и применяем AND
result = value & ~mask
print(f"Результат: 0b{result:08b}")  # 0b11110011
 
# Альтернативный подход через позицию бита
def clear_bit(number, position):
    """Сбрасывает бит на указанной позиции"""
    return number & ~(1 << position)
 
value = 0xFF
value = clear_bit(value, 3)  # Сбрасываем 3-й бит
value = clear_bit(value, 5)  # И 5-й
print(f"После сброса: 0b{value:08b}")  # 0b11010111

# Левый сдвиг - умножение
x = 5
print(f"{x} << 1 = {x << 1}")  # 10 (5 * 2)
print(f"{x} << 2 = {x << 2}")  # 20 (5 * 4)
print(f"{x} << 3 = {x << 3}")  # 40 (5 * 8)
 
# Правый сдвиг - деление с округлением вниз
y = 20
print(f"{y} >> 1 = {y >> 1}")  # 10 (20 // 2)
print(f"{y} >> 2 = {y >> 2}")  # 5 (20 // 4)
 
# Быстрое возведение двойки в степень
power = 10
result = 1 << power  # 2^10
print(f"2^{power} = {result}")  # 1024
 
# Проверка, является ли число степенью двойки
def is_power_of_two(n):
    """Степень двойки имеет только один включенный бит"""
    return n > 0 and (n & (n - 1)) == 0
 
print(f"16 - степень двойки? {is_power_of_two(16)}")  # True
print(f"15 - степень двойки? {is_power_of_two(15)}")  # False

positive = 8   # 0b1000
negative = -8  # ...11111000 в дополнительном коде
 
print(f"{positive} >> 2 = {positive >> 2}")  # 2
print(f"{negative} >> 2 = {negative >> 2}")  # -2 (не 2!)
 
# При сдвиге вправо знак сохраняется
# Это эквивалентно floor(x / 2^n) для любого знака
print(f"-7 >> 1 = {-7 >> 1}")  # -4 (не -3!)
print(f"-7 // 2 = {-7 // 2}")  # -4 - то же самое

# Маска из N младших бит
def create_mask(num_bits):
    return (1 << num_bits) - 1
 
print(f"4-битная маска: 0b{create_mask(4):04b}")  # 0b1111
print(f"8-битная маска: 0x{create_mask(8):02X}")  # 0xFF
 
# Извлечение диапазона бит
def extract_bits(value, start, count):
    """Извлекает count бит, начиная с позиции start"""
    mask = create_mask(count)
    return (value >> start) & mask
 
data = 0b11010110
bits = extract_bits(data, 2, 3)  # Биты 2-4
print(f"Биты 2-4 из {data:08b}: 0b{bits:03b}")  # 0b101

def parse_vlq(bytes_data):
    """Распаковка переменной длины из MIDI"""
    value = 0
    for byte in bytes_data:
        # Берём 7 младших бит и добавляем к результату
        value = (value << 7) | (byte & 0x7F)
        # Если старший бит 0 - это последний байт
        if (byte & 0x80) == 0:
            break
    return value
 
# Пример: число 16384 в VLQ записано как 0x81 0x80 0x00
midi_bytes = [0x81, 0x80, 0x00]
number = parse_vlq(midi_bytes)
print(f"VLQ {[hex(b) for b in midi_bytes]} = {number}")  # 16384

# Ошибка новичка: проверка флага
READ_FLAG = 0b0001
permissions = 0b0101
 
# Так НЕ работает!
if permissions & READ_FLAG == 1:  # Сравнение выполнится раньше!
    print("Есть права на чтение")  # Не выполнится
 
# Что происходит на самом деле:
[H2]permissions & (READ_FLAG == 1) -> permissions & True -> некорректный результат[/H2]
 
# Правильный вариант с явными скобками
if (permissions & READ_FLAG) == 1:
    print("Правильная проверка")
 
# Или еще проще - проверка на ненулевое значение
if permissions & READ_FLAG:
    print("Тоже работает")

# Коварный пример
value = 0xFF00
result1 = value >> 8 + 4  # value >> 12
result2 = (value >> 8) + 4  # (value >> 8) + 4
 
print(f"Без скобок: {result1}")  # 15
print(f"Со скобками: {result2}")  # 259 - совсем другое!
 
# Еще один подвох с масками
data = 0b11010110
# Хотим проверить, установлены ли биты 2 И 3 одновременно
mask = 0b00001100
 
# Неправильно
if data & mask == mask:  # Сравнение раньше!
    print("Не сработает как ожидалось")
 
# Правильно
if (data & mask) == mask:
    print("Оба бита установлены")

# Упаковка RGB в 24-битное значение
def pack_rgb(r, g, b):
    """Упаковывает три байта цвета в одно число"""
    return (r << 16) | (g << 8) | b
 
# Распаковка обратно
def unpack_rgb(color):
    """Извлекает компоненты RGB"""
    r = (color >> 16) & 0xFF
    g = (color >> 8) & 0xFF
    b = color & 0xFF
    return r, g, b
 
orange = pack_rgb(255, 165, 0)
print(f"Упакованный цвет: 0x{orange:06X}")
r, g, b = unpack_rgb(orange)
print(f"Распакованный: RGB({r}, {g}, {b})")
 
# Установка и сброс нескольких битов одновременно
def modify_bits(value, set_mask, clear_mask):
    """Устанавливает биты из set_mask и сбрасывает из clear_mask"""
    value |= set_mask      # Включаем нужные биты
    value &= ~clear_mask   # Выключаем ненужные
    return value
 
flags = 0b00000000
flags = modify_bits(flags, 0b00001010, 0b00000100)  # Включить 1 и 3, выключить 2
print(f"Флаги: 0b{flags:08b}")  # 0b00001010
 
# Циклический сдвиг влево (rotate left)
def rotl(value, shift, bits=8):
    """Циклический сдвиг влево для N-битного числа"""
    shift %= bits  # Нормализуем сдвиг
    mask = (1 << bits) - 1
    return ((value << shift) | (value >> (bits - shift))) & mask
 
byte = 0b10110010
rotated = rotl(byte, 3)
print(f"Исходный: 0b{byte:08b}")
print(f"После rotl(3): 0b{rotated:08b}")  # 0b10010101

def crc32_simple(data, poly=0xEDB88320):
    """Упрощенная реализация CRC-32"""
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^= byte  # XOR с текущим байтом
        
        for _ in range(8):  # Обрабатываем каждый бит
            # Если младший бит 1 - применяем полином
            if crc & 1:
                crc = (crc >> 1) ^ poly
            else:
                crc >>= 1
    
    return crc ^ 0xFFFFFFFF  # Финальная инверсия
 
test_data = b"Hello, World!"
checksum = crc32_simple(test_data)
print(f"CRC-32: 0x{checksum:08X}")

# Наглядная демонстрация
positive = 5   # ...00000101
negative = -5  # ...11111011 (в дополнительном коде)
 
# Правый сдвиг заполняет единицами
print(f"{negative} >> 1 = {negative >> 1}")  # -3 (не 2147483645!)
print(f"{negative} >> 2 = {negative >> 2}")  # -2
 
# Побитовое И с отрицательным числом
result = 0xFF & negative
print(f"0xFF & {negative} = {result}")  # 251 (0xFB)
 
# XOR с отрицательным
print(f"5 ^ -5 = {5 ^ -5}")  # -2
[H2]Почему? 00000101 ^ 11111011 = 11111110 = -2[/H2]
 
# Проверка на нечетность работает и с отрицательными
def is_odd(n):
    return bool(n & 1)
 
print(f"-7 нечетное? {is_odd(-7)}")   # True
print(f"-8 нечетное? {is_odd(-8)}")   # False

# Сравнение операций
numbers = [7, -7, 8, -8]
 
for n in numbers:
    shifted = n >> 1
    divided = n // 2
    print(f"{n:3d}: сдвиг={shifted:3d}, деление={divided:3d}, равны? {shifted == divided}")
 
# Вывод покажет, что результаты идентичны
# Это гарантирует корректную работу алгоритмов

def unsigned_rshift(n, shift, bits=32):
    """Эмуляция беззнакового правого сдвига"""
    # Преобразуем в беззнаковое представление
    mask = (1 << bits) - 1
    n &= mask  # Обрезаем до нужной разрядности
    return n >> shift
 
# Пример: -1 в 32-битном беззнаковом = 0xFFFFFFFF
print(f"Знаковый: {-1 >> 8}")  # -1
print(f"Беззнаковый: {unsigned_rshift(-1, 8)}")  # 16777215 (0x00FFFFFF)

# Определяем флаги как степени двойки
NOTIFY_EMAIL = 1 << 0    # 0b00000001 = 1
NOTIFY_SMS = 1 << 1      # 0b00000010 = 2
NOTIFY_PUSH = 1 << 2     # 0b00000100 = 4
NOTIFY_SOUND = 1 << 3    # 0b00001000 = 8
NOTIFY_VIBRATE = 1 << 4  # 0b00010000 = 16
 
# Пользователь выбрал email и push
user_prefs = NOTIFY_EMAIL | NOTIFY_PUSH
print(f"Настройки: 0b{user_prefs:08b}")  # 0b00000101
 
# Проверка конкретного флага
has_email = bool(user_prefs & NOTIFY_EMAIL)
has_sms = bool(user_prefs & NOTIFY_SMS)
print(f"Email включен: {has_email}")  # True
print(f"SMS включен: {has_sms}")      # False
 
# Добавление флага
user_prefs |= NOTIFY_SOUND  # Включаем звук
print(f"После добавления: 0b{user_prefs:08b}")  # 0b00001101
 
# Удаление флага
user_prefs &= ~NOTIFY_EMAIL  # Выключаем email
print(f"После удаления: 0b{user_prefs:08b}")  # 0b00001100
 
# Переключение (toggle)
user_prefs ^= NOTIFY_VIBRATE  # Инвертируем вибрацию
print(f"После toggle: 0b{user_prefs:08b}")

# Маска для извлечения младших 4 бит (нибла)
LOW_NIBBLE_MASK = 0x0F  # 0b00001111
 
# Маска для старших 4 бит
HIGH_NIBBLE_MASK = 0xF0  # 0b11110000
 
byte_val = 0xA7  # 0b10100111
 
low_nibble = byte_val & LOW_NIBBLE_MASK
high_nibble = (byte_val & HIGH_NIBBLE_MASK) >> 4
 
print(f"Младший нибл: 0x{low_nibble:X}")  # 0x7
print(f"Старший нибл: 0x{high_nibble:X}")  # 0xA
 
# Генерация маски для N последовательных бит
def bit_mask(start, length):
    """Создает маску для length бит, начиная с позиции start"""
    mask = ((1 << length) - 1) << start
    return mask
 
# Маска для бит 2-5 (4 бита, начиная с позиции 2)
mask = bit_mask(2, 4)
print(f"Маска бит 2-5: 0b{mask:08b}")  # 0b00111100
 
# Применение маски для извлечения
data = 0b11010110
extracted = (data & mask) >> 2
print(f"Извлеченные биты: 0b{extracted:04b}")  # 0b0101
 
# Проверка множественных флагов одновременно
READ_WRITE = NOTIFY_EMAIL | NOTIFY_SMS
has_both = (user_prefs & READ_WRITE) == READ_WRITE
has_any = (user_prefs & READ_WRITE) != 0
 
print(f"Есть оба флага: {has_both}")
print(f"Есть хотя бы один: {has_any}")

# Базовые права (младшие 9 бит)
S_IRUSR = 1 << 8  # 0400 - чтение для владельца
S_IWUSR = 1 << 7  # 0200 - запись для владельца
S_IXUSR = 1 << 6  # 0100 - выполнение для владельца
 
S_IRGRP = 1 << 5  # 0040 - чтение для группы
S_IWGRP = 1 << 4  # 0020 - запись для группы
S_IXGRP = 1 << 3  # 0010 - выполнение для группы
 
S_IROTH = 1 << 2  # 0004 - чтение для остальных
S_IWOTH = 1 << 1  # 0002 - запись для остальных
S_IXOTH = 1 << 0  # 0001 - выполнение для остальных
 
# Специальные биты
S_ISUID = 1 << 11  # 04000 - setuid
S_ISGID = 1 << 10  # 02000 - setgid
S_ISVTX = 1 << 9   # 01000 - sticky bit
 
class FilePermissions:
    """Управление Unix-правами через битовые операции"""
    
    def __init__(self, mode=0):
        self.mode = mode
    
    @classmethod
    def from_string(cls, perm_str):
        """Создает из строки типа 'rwxr-xr--'"""
        mode = 0
        perms = [
            (S_IRUSR, S_IWUSR, S_IXUSR),
            (S_IRGRP, S_IWGRP, S_IXGRP),
            (S_IROTH, S_IWOTH, S_IXOTH)
        ]
        
        for i, (r, w, x) in enumerate(perms):
            offset = i * 3
            if perm_str[offset] == 'r':
                mode |= r
            if perm_str[offset + 1] == 'w':
                mode |= w
            if perm_str[offset + 2] == 'x':
                mode |= x
        
        return cls(mode)
    
    def can_read(self, user_type='owner'):
        """Проверяет право на чтение"""
        masks = {
            'owner': S_IRUSR,
            'group': S_IRGRP,
            'others': S_IROTH
        }
        return bool(self.mode & masks[user_type])
    
    def grant(self, permission):
        """Выдает право"""
        self.mode |= permission
    
    def revoke(self, permission):
        """Отзывает право"""
        self.mode &= ~permission
    
    def to_octal(self):
        """Возвращает восьмеричное представление"""
        return f"{self.mode:04o}"
    
    def __str__(self):
        """Человекочитаемый формат"""
        chars = []
        for flag in [S_IRUSR, S_IWUSR, S_IXUSR,
                     S_IRGRP, S_IWGRP, S_IXGRP,
                     S_IROTH, S_IWOTH, S_IXOTH]:
            chars.append('rwx'[len(chars) % 3] if self.mode & flag else '-')
        return ''.join(chars)
 
# Использование
perms = FilePermissions.from_string('rwxr-xr--')
print(f"Права: {perms}")  # rwxr-xr--
print(f"Восьмеричный: {perms.to_octal()}")  # 0754
 
# Проверки
print(f"Владелец может читать: {perms.can_read('owner')}")    # True
print(f"Остальные могут писать: {perms.can_read('others')}")  # False
 
# Модификация
perms.grant(S_IWOTH)  # Даём право записи всем
print(f"После изменения: {perms}")  # rwxr-xrw-
 
# Сброс всех прав записи
write_mask = S_IWUSR | S_IWGRP | S_IWOTH
perms.revoke(write_mask)
print(f"Без записи: {perms}")  # r-xr-xr--

def get_bit(value, position):
    """Возвращает значение бита на позиции (0 или 1)"""
    return (value >> position) & 1
 
def set_bit(value, position):
    """Устанавливает бит в 1"""
    return value | (1 << position)
 
def clear_bit(value, position):
    """Сбрасывает бит в 0"""
    return value & ~(1 << position)
 
def toggle_bit(value, position):
    """Инвертирует бит"""
    return value ^ (1 << position)
 
def update_bit(value, position, bit_value):
    """Устанавливает бит в заданное значение (0 или 1)"""
    mask = 1 << position
    return (value & ~mask) | ((bit_value << position) & mask)
 
# Тестируем
flags = 0b00000000
 
flags = set_bit(flags, 3)
print(f"После set(3): 0b{flags:08b}")  # 0b00001000
 
flags = set_bit(flags, 7)
print(f"После set(7): 0b{flags:08b}")  # 0b10001000
 
bit_val = get_bit(flags, 7)
print(f"Бит 7: {bit_val}")  # 1
 
flags = toggle_bit(flags, 3)
print(f"После toggle(3): 0b{flags:08b}")  # 0b10000000
 
flags = update_bit(flags, 4, 1)
print(f"После update(4, 1): 0b{flags:08b}")  # 0b10010000

# Проверка знака без сравнения
def sign_no_branch(n):
    """Возвращает -1 для отрицательных, 1 для положительных, 0 для нуля"""
    return (n > 0) - (n < 0)  # Это всё равно с ветвлением
 
# Версия через биты (работает для знаковых чисел)
def sign_bitwise(n):
    return -((n >> 63) & 1) | (n != 0)
 
# Минимум и максимум без if
def min_bitwise(a, b):
    """Выбирает меньшее из двух чисел"""
    return b ^ ((a ^ b) & -(a < b))
 
def max_bitwise(a, b):
    """Выбирает большее из двух чисел"""
    return a ^ ((a ^ b) & -(a < b))
 
# Абсолютное значение без условия
def abs_bitwise(n):
    """Модуль числа через битовые операции"""
    mask = n >> 31  # Все биты = знак (для 32-бит)
    return (n + mask) ^ mask
 
# Среднее без переполнения
def average_safe(a, b):
    """Среднее арифметическое без риска переполнения"""
    return (a & b) + ((a ^ b) >> 1)
 
print(f"min(15, 23): {min_bitwise(15, 23)}")  # 15
print(f"max(15, 23): {max_bitwise(15, 23)}")  # 23
print(f"abs(-42): {abs_bitwise(-42)}")  # 42
print(f"avg(100, 200): {average_safe(100, 200)}")  # 150

import threading
 
class ThreadSafeFlags:
    """Потокобезопасные флаги через блокировки"""
    
    def __init__(self):
        self._flags = 0
        self._lock = threading.Lock()
    
    def set_flag(self, flag):
        with self._lock:
            self._flags |= flag
    
    def clear_flag(self, flag):
        with self._lock:
            self._flags &= ~flag
    
    def has_flag(self, flag):
        # Чтение одного int атомарно в CPython
        return bool(self._flags & flag)
 
# Использование в многопоточной среде
THREAD_STARTED = 1 << 0
THREAD_WORKING = 1 << 1
THREAD_DONE = 1 << 2
 
state = ThreadSafeFlags()
 
def worker():
    state.set_flag(THREAD_STARTED)
    # ... работа ...
    state.set_flag(THREAD_WORKING)
    # ... ещё работа ...
    state.clear_flag(THREAD_WORKING)
    state.set_flag(THREAD_DONE)
 
# GIL в CPython гарантирует атомарность простых операций,
# но для переносимости лучше использовать явные блокировки

# Компактное хранение состояний множества объектов
class BitmapStateTracker:
    """Отслеживание состояний через битовую карту"""
    
    def __init__(self, max_items=1024):
        # Сколько 64-битных чисел нужно для max_items бит
        self.num_words = (max_items + 63) // 64
        self.states = [0] * self.num_words
    
    def set_active(self, item_id):
        """Помечает элемент как активный"""
        word_idx = item_id // 64
        bit_pos = item_id % 64
        self.states[word_idx] |= (1 << bit_pos)
    
    def set_inactive(self, item_id):
        """Помечает элемент как неактивный"""
        word_idx = item_id // 64
        bit_pos = item_id % 64
        self.states[word_idx] &= ~(1 << bit_pos)
    
    def is_active(self, item_id):
        """Проверяет активность элемента"""
        word_idx = item_id // 64
        bit_pos = item_id % 64
        return bool(self.states[word_idx] & (1 << bit_pos))
    
    def count_active(self):
        """Подсчитывает количество активных элементов"""
        return sum(bin(word).count('1') for word in self.states)
    
    def get_active_ids(self):
        """Возвращает список ID активных элементов"""
        active = []
        for word_idx, word in enumerate(self.states):
            if word == 0:
                continue
            # Проверяем каждый бит в слове
            for bit_pos in range(64):
                if word & (1 << bit_pos):
                    active.append(word_idx * 64 + bit_pos)
        return active
 
# Применение
tracker = BitmapStateTracker(max_items=200)
 
# Активируем некоторые элементы
for item_id in [5, 17, 42, 99, 150]:
    tracker.set_active(item_id)
 
print(f"Активных элементов: {tracker.count_active()}")  # 5
print(f"ID активных: {tracker.get_active_ids()}")  # [5, 17, 42, 99, 150]
 
# Проверка конкретного
print(f"Элемент 42 активен? {tracker.is_active(42)}")  # True
print(f"Элемент 43 активен? {tracker.is_active(43)}")  # False
 
# Деактивация
tracker.set_inactive(17)
print(f"После деактивации 17: {tracker.get_active_ids()}")  # [5, 42, 99, 150]

class BitSet:
    """Множество целых чисел через битовую карту"""
    
    def __init__(self, max_value=1000):
        self.max_value = max_value
        # Используем bytearray для изменяемости
        num_bytes = (max_value + 7) // 8
        self.bits = bytearray(num_bytes)
    
    def add(self, value):
        """Добавляет значение в множество"""
        if value >= self.max_value:
            raise ValueError(f"Значение {value} превышает максимум {self.max_value}")
        byte_idx = value // 8
        bit_pos = value % 8
        self.bits[byte_idx] |= (1 << bit_pos)
    
    def remove(self, value):
        """Удаляет значение из множества"""
        byte_idx = value // 8
        bit_pos = value % 8
        self.bits[byte_idx] &= ~(1 << bit_pos)
    
    def contains(self, value):
        """Проверяет наличие значения"""
        byte_idx = value // 8
        bit_pos = value % 8
        return bool(self.bits[byte_idx] & (1 << bit_pos))
    
    def __contains__(self, value):
        return self.contains(value)
    
    def union(self, other):
        """Объединение двух множеств"""
        result = BitSet(self.max_value)
        for i in range(len(self.bits)):
            result.bits[i] = self.bits[i] | other.bits[i]
        return result
    
    def intersection(self, other):
        """Пересечение множеств"""
        result = BitSet(self.max_value)
        for i in range(len(self.bits)):
            result.bits[i] = self.bits[i] & other.bits[i]
        return result
    
    def __len__(self):
        """Количество элементов в множестве"""
        return sum(bin(byte).count('1') for byte in self.bits)
 
# Использование
primes = BitSet(100)
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
    primes.add(p)
 
evens = BitSet(100)
for e in range(0, 100, 2):
    evens.add(e)
 
print(f"7 простое? {7 in primes}")  # True
print(f"8 простое? {8 in primes}")  # False
print(f"Всего простых: {len(primes)}")  # 11
 
# Пересечение - четные простые числа
even_primes = primes.intersection(evens)
print(f"Четных простых: {len(even_primes)}")  # 1 (только 2)

import time
 
# Сравнение производительности
def benchmark_sets():
    # Стандартное множество
    std_set = set(range(0, 100000, 2))  # Четные числа
    
    # Битовое множество
    bit_set = BitSet(100000)
    for i in range(0, 100000, 2):
        bit_set.add(i)
    
    # Проверка наличия
    start = time.perf_counter()
    results = [i in std_set for i in range(0, 10000, 3)]
    std_time = time.perf_counter() - start
    
    start = time.perf_counter()
    results = [i in bit_set for i in range(0, 10000, 3)]
    bit_time = time.perf_counter() - start
    
    print(f"Стандартное set: {std_time*1000:.3f} мс")
    print(f"Битовое set: {bit_time*1000:.3f} мс")
    print(f"Разница: {std_time/bit_time:.2f}x")
 
benchmark_sets()

# Сохранение и восстановление битового множества
def serialize_bitset(bitset):
    """Упаковка в hex-строку"""
    return bitset.bits.hex()
 
def deserialize_bitset(hex_str, max_value):
    """Распаковка из hex-строки"""
    bitset = BitSet(max_value)
    bitset.bits = bytearray.fromhex(hex_str)
    return bitset
 
# Пример
original = BitSet(64)
for val in [1, 5, 13, 21, 34, 55]:
    original.add(val)
 
# Сериализуем
serialized = serialize_bitset(original)
print(f"Упакованно в: {serialized}")  # Короткая hex-строка
 
# Восстанавливаем
restored = deserialize_bitset(serialized, 64)
print(f"21 присутствует? {21 in restored}")  # True
print(f"22 присутствует? {22 in restored}")  # False

# Наивное масштабирование с потерей точности
def scale_naive(coord, factor):
    return int(coord * factor)
 
# Через сдвиги - без промежуточных дробей
def scale_shift(coord, power):
    """factor = 2^power"""
    return coord << power
 
# Деление с округлением вниз
def scale_down_shift(coord, power):
    return coord >> power
 
# Тестируем
original = 100
scaled_up = scale_shift(original, 3)  # *8
scaled_down = scale_down_shift(scaled_up, 3)  # /8
 
print(f"{original} -> {scaled_up} -> {scaled_down}")  # 100 -> 800 -> 100
# Идеальная обратимость без дробей

def is_power_of_two(n):
    """У степени двойки ровно один бит установлен"""
    return n > 0 and (n & (n - 1)) == 0
 
# Как это работает:
# 8 = 0b1000, 8-1 = 0b0111
[H2]0b1000 & 0b0111 = 0b0000 = 0 ✓[/H2]
 
# 6 = 0b0110, 6-1 = 0b0101  
[H2]0b0110 & 0b0101 = 0b0100 ≠ 0 ✗[/H2]
 
for num in [1, 2, 3, 4, 5, 8, 15, 16, 32, 33]:
    print(f"{num}: {is_power_of_two(num)}")

def count_bits_naive(n):
    """Наивный подход - O(количество бит)"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count
 
def count_bits_kernighan(n):
    """Алгоритм Кернигана - O(количество единиц)"""
    count = 0
    while n:
        n &= n - 1  # Сбрасывает младший единичный бит
        count += 1
    return count
 
# Почему быстрее? 
# n & (n-1) обнуляет самый правый бит со значением 1
# Например: 0b1010 & 0b1001 = 0b1000
[H2]За одну итерацию убираем один бит, а не проверяем все[/H2]
 
# Тест производительности
import time
 
large_number = 0xFFFFFFFFFFFF  # 48 бит установлено
 
start = time.perf_counter()
for _ in range(10000):
    count_bits_naive(large_number)
naive_time = time.perf_counter() - start
 
start = time.perf_counter()
for _ in range(10000):
    count_bits_kernighan(large_number)
kernighan_time = time.perf_counter() - start
 
print(f"Наивный: {naive_time*1000:.2f} мс")
print(f"Кернигана: {kernighan_time*1000:.2f} мс")
print(f"Ускорение: {naive_time
 
/kernighan_time:.2f}x")
 
# В Python 3.10+ есть встроенный метод
print(f"Встроенный метод: {large_number.bit_count()}")

def simple_hash(data, size=32):
    """Примитивная хеш-функция через XOR"""
    if isinstance(data, str):
        data = data.encode()
    
    hash_value = 0
    for i in range(0, len(data), size // 8):
        chunk = int.from_bytes(data[i:i + size // 8], 'little')
        hash_value ^= chunk
    
    return hash_value
 
# Тест
text1 = "Hello, World!"
text2 = "Hello, World?"
print(f"Хеш 1: {simple_hash(text1):08X}")
print(f"Хеш 2: {simple_hash(text2):08X}")
 
# Контрольная сумма Флетчера - более надежная
def fletcher16(data):
    """16-битная контрольная сумма"""
    if isinstance(data, str):
        data = data.encode()
    
    sum1 = sum2 = 0
    for byte in data:
        sum1 = (sum1 + byte) % 255
        sum2 = (sum2 + sum1) % 255
    
    return (sum2 << 8) | sum1
 
checksum = fletcher16("The quick brown fox")
print(f"Fletcher-16: {checksum:04X}")

# Классический способ
def is_even_mod(n):
    return n % 2 == 0
 
# Через биты
def is_even_bit(n):
    return (n & 1) == 0
 
# Чётность всего числа (количество единичных бит)
def parity(n):
    """Возвращает 0 для четного числа единиц, 1 для нечетного"""
    count = 0
    while n:
        count ^= 1
        n &= n - 1  # Убираем младший бит
    return count
 
# Быстрая версия через XOR
def parity_fast(n):
    """Параллельное вычисление четности"""
    n ^= n >> 16
    n ^= n >> 8
    n ^= n >> 4
    n ^= n >> 2
    n ^= n >> 1
    return n & 1
 
print(f"Четность 0b1011 (3 единицы): {parity_fast(0b1011)}")  # 1
print(f"Четность 0b1111 (4 единицы): {parity_fast(0b1111)}")  # 0

def reverse_bits_naive(n, bits=8):
    """Наивный реверс через строку"""
    binary = f"{n:0{bits}b}"
    reversed_binary = binary[::-1]
    return int(reversed_binary, 2)
 
def reverse_bits_fast(n, bits=8):
    """Быстрый реверс через битовые операции"""
    result = 0
    for _ in range(bits):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result
 
# Оптимизированный через lookup-таблицу для байтов
REVERSE_BYTE = [int(f'{i:08b}'[::-1], 2) for i in range(256)]
 
def reverse_bits_lookup(n, bits=32):
    """Реверс через предвычисленную таблицу"""
    result = 0
    for _ in range(bits // 8):
        result = (result << 8) | REVERSE_BYTE[n & 0xFF]
        n >>= 8
    return result
 
# Тест
original = 0b11010110
reversed_8 = reverse_bits_fast(original, 8)
print(f"{original:08b} -> {reversed_8:08b}")  # 11010110 -> 01101011

class XorShift32:
    """Простой ГПСЧ на основе XOR-сдвигов"""
    
    def __init__(self, seed=123456789):
        self.state = seed
    
    def next(self):
        """Генерирует следующее 32-битное число"""
        x = self.state
        x ^= (x << 13) & 0xFFFFFFFF
        x ^= (x >> 17) & 0xFFFFFFFF
        x ^= (x << 5) & 0xFFFFFFFF
        self.state = x
        return x
    
    def random_float(self):
        """Возвращает число в диапазоне [0, 1)"""
        return self.next() / 0x100000000
    
    def random_range(self, min_val, max_val):
        """Число в заданном диапазоне"""
        return min_val + int(self.random_float() * (max_val - min_val))
 
# Использование
rng = XorShift32(seed=42)
numbers = [rng.random_range(1, 100) for _ in range(10)]
print(f"Случайные числа: {numbers}")
 
# Проверка распределения
samples = [rng.random_range(0, 10) for _ in range(10000)]
distribution = [samples.count(i) for i in range(10)]
print(f"Распределение: {distribution}")

def rgb_to_int(r, g, b):
    """RGB -> 24-битное число"""
    return (r << 16) | (g << 8) | b
 
def int_to_rgb(color):
    """24-битное число -> RGB"""
    return (color >> 16) & 0xFF, (color >> 8) & 0xFF, color & 0xFF
 
def rgba_to_int(r, g, b, a=255):
    """RGBA -> 32-битное число"""
    return (a << 24) | (r << 16) | (g << 8) | b
 
def blend_colors(color1, color2, alpha):
    """Смешивает два цвета с коэффициентом alpha [0.0-1.0]"""
    r1, g1, b1 = int_to_rgb(color1)
    r2, g2, b2 = int_to_rgb(color2)
    
    r = int(r1 * (1 - alpha) + r2 * alpha)
    g = int(g1 * (1 - alpha) + g2 * alpha)
    b = int(b1 * (1 - alpha) + b2 * alpha)
    
    return rgb_to_int(r, g, b)
 
# Осветление/затемнение через битовые сдвиги
def lighten(color, amount=1):
    """Осветляет цвет через сдвиг вправо"""
    r, g, b = int_to_rgb(color)
    r = min(255, r + (r >> amount))
    g = min(255, g + (g >> amount))
    b = min(255, b + (b >> amount))
    return rgb_to_int(r, g, b)
 
# Извлечение канала альфа
def get_alpha(rgba):
    return (rgba >> 24) & 0xFF
 
# Установка альфа-канала
def set_alpha(rgb, alpha):
    return (rgb & 0xFFFFFF) | (alpha << 24)
 
# Применение
red = rgb_to_int(255, 0, 0)
blue = rgb_to_int(0, 0, 255)
purple = blend_colors(red, blue, 0.5)
 
r, g, b = int_to_rgb(purple)
print(f"Фиолетовый: RGB({r}, {g}, {b})")  # RGB(127, 0, 127)
 
# Работа с прозрачностью
semi_transparent = set_alpha(purple, 128)
print(f"С альфой: {semi_transparent:08X}")
print(f"Альфа канал: {get_alpha(semi_transparent)}")
 
# Инверсия цвета
def invert_color(color):
    r, g, b = int_to_rgb(color)
    return rgb_to_int(255 - r, 255 - g, 255 - b)
 
inverted = invert_color(purple)
r, g, b = int_to_rgb(inverted)
print(f"Инвертированный: RGB({r}, {g}, {b})")

def brightness_fast(color):
    """Приблизительная яркость через сдвиги"""
    r, g, b = int_to_rgb(color)
    # Формула: 0.299*R + 0.587*G + 0.114*B
    # Приближаем: (R + 2*G + B) / 4
    return (r + (g << 1) + b) >> 2
 
def grayscale(color):
    """Преобразование в оттенки серого"""
    brightness = brightness_fast(color)
    return rgb_to_int(brightness, brightness, brightness)
 
# Применение
colored = rgb_to_int(255, 100, 50)
gray = grayscale(colored)
print(f"Цветной: {colored:06X}, Серый: {gray:06X}")

class GameEntityState:
"""Состояние игрового объекта через битовые поля"""
 
def __init__(self):
    # Всё состояние в одном 32-битном числе
    self._state = 0
 
# Определяем поля через позицию и ширину
ALIVE = (0, 1)          # 1 бит с позиции 0
HEALTH = (1, 7)         # 7 бит с позиции 1 (0-127)
DIRECTION = (8, 3)      # 3 бита (8 направлений)
TEAM = (11, 2)          # 2 бита (4 команды)
WEAPON = (13, 4)        # 4 бита (16 типов оружия)
STATUS = (17, 3)        # 3 бита (8 статусов)
[H2]Итого используем 20 бит из 32[/H2]
 
def _get_field(self, position, width):
    """Извлекает значение поля"""
    mask = (1 << width) - 1
    return (self._state >> position) & mask
 
def _set_field(self, position, width, value):
    """Устанавливает значение поля"""
    mask = (1 << width) - 1
    # Проверяем переполнение
    if value > mask:
        raise ValueError(f"Значение {value} не помещается в {width} бит")
    # Очищаем старое значение и устанавливаем новое
    clear_mask = ~(mask << position)
    self._state = (self._state & clear_mask) | (value << position)
 
@property
def alive(self):
    return bool(self._get_field(*self.ALIVE))
 
@alive.setter
def alive(self, value):
    self._set_field(*self.ALIVE, int(value))
 
@property
def health(self):
    return self._get_field(*self.HEALTH)
 
@health.setter  
def health(self, value):
    self._set_field(*self.HEALTH, min(127, max(0, value)))
 
@property
def direction(self):
    return self._get_field(*self.DIRECTION)
 
@direction.setter
def direction(self, value):
    self._set_field(*self.DIRECTION, value & 0x7)
 
# Использование
entity = GameEntityState()
entity.alive = True
entity.health = 75
entity.direction = 3  # Юго-восток
 
print(f"Состояние: 0x{entity._state:08X}")  # Всё в одном числе
print(f"Здоровье: {entity.health}")
print(f"Направление: {entity.direction}")

def pack_datetime(year, month, day, hour, minute, second):
"""Упаковка даты в 32 бита: год(12), месяц(4), день(5), час(5), минута(6)"""
# Год с 2000: 12 бит (0-4095) -> до 6095 года
# Месяц: 4 бита (1-12)
# День: 5 бит (1-31)
# Час: 5 бит (0-23)
# Минута: 6 бит (0-59)
# Всего: 32 бита
year_offset = year - 2000
if not (0 <= year_offset < 4096):
    raise ValueError("Год должен быть в диапазоне 2000-6095")
 
packed = (year_offset << 20) | (month << 16) | (day << 11) | \
         (hour << 6) | minute
return packed
 
def unpack_datetime(packed):
"""Распаковка даты из 32 бит"""
year = ((packed >> 20) & 0xFFF) + 2000
month = (packed >> 16) & 0xF
day = (packed >> 11) & 0x1F
hour = (packed >> 6) & 0x1F
minute = packed & 0x3F
return year, month, day, hour, minute
 
# Тестируем
dt_packed = pack_datetime(2024, 12, 31, 23, 59)
print(f"Упакованная дата: 0x{dt_packed:08X}")
 
year, month, day, hour, minute = unpack_datetime(dt_packed)
print(f"Дата: {year:04d}-{month:02d}-{day:02d} {hour:02d}:{minute:02d}")

class CompactSubscriptions:
"""Управление подписками через битовые множества"""
 
def __init__(self, num_categories=128):
    self.num_categories = num_categories
    self.users = {}  # user_id -> битовая маска подписок
 
def subscribe(self, user_id, category_id):
    """Добавляет подписку"""
    if user_id not in self.users:
        self.users[user_id] = 0
    self.users[user_id] |= (1 << category_id)
 
def unsubscribe(self, user_id, category_id):
    """Убирает подписку"""
    if user_id in self.users:
        self.users[user_id] &= ~(1 << category_id)
 
def is_subscribed(self, user_id, category_id):
    """Проверяет подписку"""
    return bool(self.users.get(user_id, 0) & (1 << category_id))
 
def get_subscriptions(self, user_id):
    """Список всех подписок пользователя"""
    mask = self.users.get(user_id, 0)
    return [i for i in range(self.num_categories) if mask & (1 << i)]
 
def find_users_by_categories(self, category_ids):
    """Находит всех пользователей, подписанных на ВСЕ указанные категории"""
    # Создаём маску требуемых категорий
    required_mask = 0
    for cat_id in category_ids:
        required_mask |= (1 << cat_id)
    
    # Ищем пользователей, у которых есть все биты
    matching_users = []
    for user_id, user_mask in self.users.items():
        if (user_mask & required_mask) == required_mask:
            matching_users.append(user_id)
    
    return matching_users
 
def find_users_by_any_category(self, category_ids):
    """Находит пользователей, подписанных на ЛЮБУЮ из категорий"""
    required_mask = 0
    for cat_id in category_ids:
        required_mask |= (1 << cat_id)
    
    return [uid for uid, mask in self.users.items() if mask & required_mask]
 
# Применение
subs = CompactSubscriptions()
 
# Пользователи подписываются
subs.subscribe(1, 5)   # Пользователь 1 -> категория 5
subs.subscribe(1, 10)  # Пользователь 1 -> категория 10
subs.subscribe(2, 5)   # Пользователь 2 -> категория 5
subs.subscribe(3, 10)  # Пользователь 3 -> категория 10
 
# Поиск по категориям
users_5_and_10 = subs.find_users_by_categories([5, 10])
print(f"Подписаны на 5 И 10: {users_5_and_10}")  # [1]
 
users_5_or_10 = subs.find_users_by_any_category([5, 10])
print(f"Подписаны на 5 ИЛИ 10: {users_5_or_10}")  # [1, 2, 3]

import hashlib
 
class BloomFilter:
"""Фильтр Блума на битовом массиве"""
 
def __init__(self, size=1000, num_hashes=3):
    self.size = size
    self.num_hashes = num_hashes
    # Битовый массив
    self.bits = bytearray((size + 7) // 8)
 
def _hash(self, item, seed):
    """Хеш-функция с заданным сидом"""
    h = hashlib.md5(f"{item}{seed}".encode())
    return int.from_bytes(h.digest()[:4], 'little') % self.size
 
def add(self, item):
    """Добавляет элемент в фильтр"""
    for i in range(self.num_hashes):
        pos = self._hash(item, i)
        byte_idx = pos // 8
        bit_idx = pos % 8
        self.bits[byte_idx] |= (1 << bit_idx)
 
def contains(self, item):
    """Проверяет возможное наличие элемента"""
    for i in range(self.num_hashes):
        pos = self._hash(item, i)
        byte_idx = pos // 8
        bit_idx = pos % 8
        if not (self.bits[byte_idx] & (1 << bit_idx)):
            return False  # Точно нет
    return True  # Возможно есть
 
def __contains__(self, item):
    return self.contains(item)
 
# Использование
bloom = BloomFilter(size=10000, num_hashes=5)
 
# Добавляем элементы
existing_users = ['alice', 'bob', 'charlie', 'david']
for user in existing_users:
bloom.add(user)
 
# Проверки
print(f"alice в фильтре: {'alice' in bloom}")  # True (точно)
print(f"eve в фильтре: {'eve' in bloom}")      # False (точно нет)
 
# Может быть ложноположительный
# Если вернёт True для 'eve', нужна дополнительная проверка

def compress_rle(data):
"""RLE-сжатие битовой последовательности"""
if not data:
    return []
 
result = []
current_bit = data[0]
count = 1
 
for bit in data[1:]:
    if bit == current_bit:
        count += 1
    else:
        result.append((current_bit, count))
        current_bit = bit
        count = 1
 
result.append((current_bit, count))
return result
 
def decompress_rle(compressed):
"""Восстановление из RLE"""
result = []
for bit, count in compressed:
    result.extend([bit] * count)
return result
 
# Тестируем
bitmap = [0,0,0,0,1,1,1,0,0,1,1,1,1,1,0]
compressed = compress_rle(bitmap)
print(f"Оригинал: {len(bitmap)} бит")
print(f"Сжато: {compressed}")
print(f"Декомпрессия: {decompress_rle(compressed) == bitmap}")

class SerializableBitField:
"""Битовое поле с сериализацией"""
 
def __init__(self, value=0):
    self.value = value
 
def to_bytes(self, length=4, byteorder='little'):
    """Сериализация в байты"""
    return self.value.to_bytes(length, byteorder, signed=False)
 
@classmethod
def from_bytes(cls, data, byteorder='little'):
    """Десериализация из байтов"""
    value = int.from_bytes(data, byteorder, signed=False)
    return cls(value)
 
def to_hex(self):
    """В hex-строку для передачи"""
    return f"{self.value:08X}"
 
@classmethod
def from_hex(cls, hex_str):
    """Из hex-строки"""
    return cls(int(hex_str, 16))
 
# Сериализация массива битовых полей
def serialize_array(fields):
"""Упаковывает массив полей в компактный формат"""
# Формат: [количество][поле1][поле2]...
result = len(fields).to_bytes(4, 'little')
for field in fields:
    result += field.to_bytes(4, 'little')
return result
 
def deserialize_array(data):
"""Распаковывает массив полей"""
count = int.from_bytes(data[:4], 'little')
fields = []
offset = 4
for _ in range(count):
    value = int.from_bytes(data[offset:offset+4], 'little')
    fields.append(SerializableBitField(value))
    offset += 4
return fields
 
# Применение
field1 = SerializableBitField(0xDEADBEEF)
field2 = SerializableBitField(0xCAFEBABE)
 
# Сохраняем
data = serialize_array([field1, field2])
print(f"Сериализовано в {len(data)} байт")
 
# Восстанавливаем
restored = deserialize_array(data)
print(f"Восстановлено: {[f.to_hex() for f in restored]}")

class BitmapIndex:
    """Битовый индекс для быстрых выборок"""
    
    def __init__(self, num_records):
        self.num_records = num_records
        # Словарь: имя поля -> битовая карта
        self.indexes = {}
    
    def create_index(self, field_name):
        """Создаёт индекс для поля"""
        num_bytes = (self.num_records + 7) // 8
        self.indexes[field_name] = bytearray(num_bytes)
    
    def set_value(self, record_id, field_name, value):
        """Устанавливает значение флага для записи"""
        if field_name not in self.indexes:
            self.create_index(field_name)
        
        byte_idx = record_id // 8
        bit_idx = record_id % 8
        
        if value:
            self.indexes[field_name][byte_idx] |= (1 << bit_idx)
        else:
            self.indexes[field_name][byte_idx] &= ~(1 << bit_idx)
    
    def query_and(self, *field_names):
        """Находит записи, где ВСЕ поля истинны"""
        if not field_names:
            return []
        
        # Начинаем с первого индекса
        result = bytearray(self.indexes[field_names[0]])
        
        # Применяем AND с остальными
        for field in field_names[1:]:
            for i in range(len(result)):
                result[i] &= self.indexes[field][i]
        
        # Извлекаем ID записей
        return self._extract_set_bits(result)
    
    def query_or(self, *field_names):
        """Находит записи, где ХОТЯ БЫ ОДНО поле истинно"""
        result = bytearray(len(self.indexes[field_names[0]]))
        
        for field in field_names:
            for i in range(len(result)):
                result[i] |= self.indexes[field][i]
        
        return self._extract_set_bits(result)
    
    def _extract_set_bits(self, bitmap):
        """Извлекает позиции установленных бит"""
        record_ids = []
        for byte_idx, byte_val in enumerate(bitmap):
            if byte_val == 0:
                continue
            for bit_idx in range(8):
                if byte_val & (1 << bit_idx):
                    record_id = byte_idx * 8 + bit_idx
                    if record_id < self.num_records:
                        record_ids.append(record_id)
        return record_ids
 
# Создаём индекс для миллиона записей
index = BitmapIndex(1_000_000)
index.create_index('active')
index.create_index('premium')
index.create_index('verified')
 
# Заполняем данными (симулируем)
import random
random.seed(42)
for i in range(1000):  # Упрощённо - только первую тысячу
    index.set_value(i, 'active', random.random() > 0.3)
    index.set_value(i, 'premium', random.random() > 0.8)
    index.set_value(i, 'verified', random.random() > 0.5)
 
# Запросы выполняются мгновенно
active_premium = index.query_and('active', 'premium')
print(f"Активных премиум пользователей: {len(active_premium)}")
 
any_flag = index.query_or('active', 'premium', 'verified')
print(f"С любым флагом: {len(any_flag)}")

def encode_deltas(numbers):
    """Кодирует последовательность как база + дельты"""
    if not numbers:
        return []
    
    base = numbers[0]
    deltas = [numbers[i] - numbers[i-1] for i in range(1, len(numbers))]
    return base, deltas
 
def pack_small_ints(numbers, bits_per_number=8):
    """Упаковывает небольшие числа в битовый поток"""
    result = []
    current_byte = 0
    bit_position = 0
    
    for num in numbers:
        # Упаковываем число побитово
        for bit_idx in range(bits_per_number):
            bit = (num >> bit_idx) & 1
            current_byte |= (bit << bit_position)
            bit_position += 1
            
            if bit_position == 8:
                result.append(current_byte)
                current_byte = 0
                bit_position = 0
    
    # Добавляем остаток
    if bit_position > 0:
        result.append(current_byte)
    
    return bytes(result)
 
def unpack_small_ints(data, count, bits_per_number=8):
    """Распаковывает числа из битового потока"""
    numbers = []
    bit_position = 0
    byte_idx = 0
    
    for _ in range(count):
        num = 0
        for bit_idx in range(bits_per_number):
            if bit_position == 8:
                byte_idx += 1
                bit_position = 0
            
            bit = (data[byte_idx] >> bit_position) & 1
            num |= (bit << bit_idx)
            bit_position += 1
        
        numbers.append(num)
    
    return numbers
 
# Применение
ids = [1000, 1003, 1005, 1012, 1015, 1020]
base, deltas = encode_deltas(ids)
print(f"База: {base}, дельты: {deltas}")  # База: 1000, дельты: [3, 2, 7, 3, 5]
 
# Дельты малы, упаковываем в 4 бита вместо 32
packed = pack_small_ints(deltas, bits_per_number=4)
print(f"Оригинал: {len(deltas) * 4} байт, упаковано: {len(packed)} байт")
 
# Распаковка
unpacked = unpack_small_ints(packed, len(deltas), bits_per_number=4)
restored = [base] + [base + sum(unpacked[:i+1]) for i in range(len(unpacked))]
print(f"Восстановлено: {restored}")

def bits_needed(n):
    """Минимальное количество бит для числа"""
    if n == 0:
        return 1
    return n.bit_length()
 
def optimal_pack(numbers):
    """Упаковка с автоматическим определением разрядности"""
    if not numbers:
        return bytes()
    
    max_val = max(numbers)
    bits_per_num = bits_needed(max_val)
    
    # Записываем метаданные: количество чисел и бит на число
    header = bytes([len(numbers) & 0xFF, bits_per_num])
    data = pack_small_ints(numbers, bits_per_num)
    
    return header + data
 
# Автоматическая упаковка
small_numbers = [1, 5, 3, 7, 2, 6]
packed = optimal_pack(small_numbers)
print(f"Упаковано {len(small_numbers)} чисел в {len(packed)} байт")
print(f"Без упаковки: {len(small_numbers) * 4} байт")
print(f"Степень сжатия: {(len(small_numbers) * 4) / len(packed):.1f}x")

from enum import IntFlag, auto
from typing import Dict, List, Optional, Set
from datetime import datetime
import json
 
 
class Permission(IntFlag):
    """Предопределённые права доступа через IntFlag"""
    NONE = 0
    READ = auto()          # 1
    WRITE = auto()         # 2
    DELETE = auto()        # 4
    EXECUTE = auto()       # 8
    SHARE = auto()         # 16
    ADMIN = auto()         # 32
    
    # Комбинированные права
    READ_WRITE = READ | WRITE
    FULL_ACCESS = READ | WRITE | DELETE | EXECUTE | SHARE | ADMIN
 
 
class FlagMetadata:
    """Метаданные флага"""
    
    def __init__(self, name: str, bit_position: int, description: str = ""):
        self.name = name
        self.bit_position = bit_position
        self.description = description
        self.mask = 1 << bit_position
    
    def __repr__(self):
        return f"Flag({self.name}, bit={self.bit_position})"
 
 
class BitFlagManager:
    """Универсальный менеджер битовых флагов"""
    
    def __init__(self, max_flags: int = 64):
        self.max_flags = max_flags
        self._registry: Dict[str, FlagMetadata] = {}
        self._flags: int = 0
        self._history: List[tuple] = []  # История изменений
    
    def register_flag(self, name: str, description: str = "") -> FlagMetadata:
        """Регистрирует новый флаг"""
        if name in self._registry:
            raise ValueError(f"Флаг '{name}' уже зарегистрирован")
        
        # Находим свободную позицию
        used_positions = {meta.bit_position for meta in self._registry.values()}
        for pos in range(self.max_flags):
            if pos not in used_positions:
                meta = FlagMetadata(name, pos, description)
                self._registry[name] = meta
                return meta
        
        raise RuntimeError("Нет свободных позиций для флагов")
    
    def set_flag(self, name: str, log: bool = True) -> None:
        """Устанавливает флаг в активное состояние"""
        meta = self._get_meta(name)
        old_state = self._flags
        self._flags |= meta.mask
        
        if log and old_state != self._flags:
            self._log_change('set', name, old_state, self._flags)
    
    def clear_flag(self, name: str, log: bool = True) -> None:
        """Сбрасывает флаг"""
        meta = self._get_meta(name)
        old_state = self._flags
        self._flags &= ~meta.mask
        
        if log and old_state != self._flags:
            self._log_change('clear', name, old_state, self._flags)
    
    def toggle_flag(self, name: str) -> bool:
        """Переключает флаг, возвращает новое состояние"""
        meta = self._get_meta(name)
        old_state = self._flags
        self._flags ^= meta.mask
        new_state = bool(self._flags & meta.mask)
        
        self._log_change('toggle', name, old_state, self._flags)
        return new_state
    
    def has_flag(self, name: str) -> bool:
        """Проверяет наличие флага"""
        meta = self._get_meta(name)
        return bool(self._flags & meta.mask)
    
    def has_all(self, *names: str) -> bool:
        """Проверяет наличие всех указанных флагов"""
        mask = self._build_mask(names)
        return (self._flags & mask) == mask
    
    def has_any(self, *names: str) -> bool:
        """Проверяет наличие хотя бы одного флага"""
        mask = self._build_mask(names)
        return bool(self._flags & mask)
    
    def get_active_flags(self) -> List[str]:
        """Возвращает список активных флагов"""
        return [name for name, meta in self._registry.items() 
                if self._flags & meta.mask]
    
    def set_flags_from_mask(self, mask: int) -> None:
        """Устанавливает флаги из битовой маски"""
        old_state = self._flags
        self._flags = mask & ((1 << self.max_flags) - 1)
        self._log_change('set_mask', f"0x{mask:X}", old_state, self._flags)
    
    def get_mask(self) -> int:
        """Возвращает текущую битовую маску"""
        return self._flags
    
    def export_state(self) -> Dict:
        """Экспортирует состояние в словарь"""
        return {
            'mask': f"0x{self._flags:X}",
            'binary': f"0b{self._flags:0{self.max_flags}b}",
            'active_flags': self.get_active_flags(),
            'history_size': len(self._history)
        }
    
    def get_history(self, limit: int = 10) -> List[Dict]:
        """Возвращает историю изменений"""
        return [
            {
                'timestamp': ts.isoformat(),
                'action': action,
                'flag': flag,
                'old_mask': f"0x{old:X}",
                'new_mask': f"0x{new:X}"
            }
            for ts, action, flag, old, new in self._history[-limit:]
        ]
    
    def _get_meta(self, name: str) -> FlagMetadata:
        """Получает метаданные флага"""
        if name not in self._registry:
            raise KeyError(f"Флаг '{name}' не зарегистрирован")
        return self._registry[name]
    
    def _build_mask(self, names: tuple) -> int:
        """Строит маску из имён флагов"""
        mask = 0
        for name in names:
            meta = self._get_meta(name)
            mask |= meta.mask
        return mask
    
    def _log_change(self, action: str, flag: str, old: int, new: int) -> None:
        """Логирует изменение"""
        self._history.append((datetime.now(), action, flag, old, new))
    
    def __repr__(self):
        active = self.get_active_flags()
        return f"BitFlagManager({len(active)} active: {active})"
 
 
class ResourcePermissionManager:
    """Менеджер прав доступа к ресурсам"""
    
    def __init__(self):
        self._resources: Dict[str, BitFlagManager] = {}
        self._setup_standard_permissions()
    
    def _setup_standard_permissions(self):
        """Инициализирует стандартный набор прав"""
        self.permission_names = [
            ('read', 'Чтение данных'),
            ('write', 'Изменение данных'),
            ('delete', 'Удаление'),
            ('execute', 'Выполнение'),
            ('share', 'Совместный доступ'),
            ('admin', 'Администрирование')
        ]
    
    def create_resource(self, resource_id: str) -> BitFlagManager:
        """Создаёт новый ресурс с правами"""
        if resource_id in self._resources:
            raise ValueError(f"Ресурс '{resource_id}' уже существует")
        
        manager = BitFlagManager(max_flags=32)
        
        # Регистрируем стандартные права
        for name, desc in self.permission_names:
            manager.register_flag(name, desc)
        
        self._resources[resource_id] = manager
        return manager
    
    def grant_permission(self, resource_id: str, permission: str) -> None:
        """Выдаёт право на ресурс"""
        manager = self._get_manager(resource_id)
        manager.set_flag(permission)
    
    def revoke_permission(self, resource_id: str, permission: str) -> None:
        """Отзывает право"""
        manager = self._get_manager(resource_id)
        manager.clear_flag(permission)
    
    def check_permission(self, resource_id: str, permission: str) -> bool:
        """Проверяет наличие права"""
        manager = self._get_manager(resource_id)
        return manager.has_flag(permission)
    
    def grant_preset(self, resource_id: str, preset: str) -> None:
        """Выдаёт предустановленный набор прав"""
        presets = {
            'viewer': ['read'],
            'editor': ['read', 'write'],
            'moderator': ['read', 'write', 'delete'],
            'owner': ['read', 'write', 'delete', 'execute', 'share', 'admin']
        }
        
        if preset not in presets:
            raise ValueError(f"Неизвестный пресет: {preset}")
        
        manager = self._get_manager(resource_id)
        for perm in presets[preset]:
            manager.set_flag(perm, log=False)
        
        # Одна запись в истории для всего пресета
        manager._log_change('grant_preset', preset, 0, manager.get_mask())
    
    def get_resource_summary(self, resource_id: str) -> Dict:
        """Получает сводку по ресурсу"""
        manager = self._get_manager(resource_id)
        return {
            'resource_id': resource_id,
            'permissions': manager.get_active_flags(),
            'state': manager.export_state(),
            'recent_changes': manager.get_history(5)
        }
    
    def _get_manager(self, resource_id: str) -> BitFlagManager:
        """Получает менеджер ресурса"""
        if resource_id not in self._resources:
            raise KeyError(f"Ресурс '{resource_id}' не найден")
        return self._resources[resource_id]
    
    def list_resources(self) -> List[str]:
        """Список всех ресурсов"""
        return list(self._resources.keys())
 
 
# Комплексные тесты
def test_basic_operations():
    """Тестирование базовых операций"""
    print("=== Тест базовых операций ===")
    
    manager = BitFlagManager(max_flags=16)
    
    # Регистрация флагов
    manager.register_flag('active', 'Активность объекта')
    manager.register_flag('verified', 'Проверен')
    manager.register_flag('premium', 'Премиум статус')
    
    # Установка флагов
    manager.set_flag('active')
    manager.set_flag('verified')
    
    print(f"Состояние: {manager}")
    print(f"Экспорт: {json.dumps(manager.export_state(), indent=2)}")
    
    # Проверки
    assert manager.has_flag('active'), "Флаг active должен быть установлен"
    assert manager.has_all('active', 'verified'), "Оба флага должны быть установлены"
    assert not manager.has_flag('premium'), "Флаг premium не должен быть установлен"
    
    # Переключение
    manager.toggle_flag('premium')
    assert manager.has_flag('premium'), "После toggle premium должен быть установлен"
    
    print("✓ Базовые операции работают корректно\n")
 
 
def test_permission_system():
    """Тестирование системы прав"""
    print("=== Тест системы прав ===")
    
    pm = ResourcePermissionManager()
    
    # Создание ресурсов
    pm.create_resource('document_1')
    pm.create_resource('document_2')
    
    # Выдача прав через пресеты
    pm.grant_preset('document_1', 'editor')
    pm.grant_preset('document_2', 'viewer')
    
    # Проверка прав
    assert pm.check_permission('document_1', 'read'), "Editor должен читать"
    assert pm.check_permission('document_1', 'write'), "Editor должен писать"
    assert not pm.check_permission('document_1', 'admin'), "Editor не админ"
    
    assert pm.check_permission('document_2', 'read'), "Viewer должен читать"
    assert not pm.check_permission('document_2', 'write'), "Viewer не должен писать"
    
    # Изменение прав
    pm.grant_permission('document_2', 'write')
    assert pm.check_permission('document_2', 'write'), "После grant должно быть право"
    
    # Сводка
    summary = pm.get_resource_summary('document_1')
    print(f"Сводка по document_1:")
    print(json.dumps(summary, indent=2, ensure_ascii=False))
    
    print("✓ Система прав работает корректно\n")
 
 
def test_performance():
    """Тест производительности"""
    import time
    
    print("=== Тест производительности ===")
    
    manager = BitFlagManager(max_flags=64)
    
    # Регистрируем много флагов
    for i in range(50):
        manager.register_flag(f'flag_{i}', f'Флаг номер {i}')
    
    # Массовые операции
    start = time.perf_counter()
    for i in range(10000):
        manager.set_flag(f'flag_{i % 50}', log=False)
        manager.has_flag(f'flag_{(i + 1) % 50}')
    elapsed = time.perf_counter() - start
    
    print(f"10000 операций выполнено за {elapsed*1000:.2f} мс")
    print(f"Скорость: {10000/elapsed:.0f} операций/сек")
    print("✓ Производительность приемлема\n")
 
 
if __name__ == '__main__':
    test_basic_operations()
    test_permission_system()
    test_performance()
    
    print("=== Все тесты пройдены успешно ===")

class AdvancedBitFlagManager(BitFlagManager):
    """Расширенная версия с дополнительными возможностями"""
    
    def bulk_operation(self, operations: List[tuple]) -> None:
        """Выполняет пакет операций с одной записью в истории"""
        old_state = self._flags
        
        for op_type, flag_name in operations:
            if op_type == 'set':
                meta = self._get_meta(flag_name)
                self._flags |= meta.mask
            elif op_type == 'clear':
                meta = self._get_meta(flag_name)
                self._flags &= ~meta.mask
        
        if old_state != self._flags:
            self._log_change('bulk', f"{len(operations)} ops", old_state, self._flags)
    
    def snapshot(self) -> int:
        """Создаёт снимок текущего состояния"""
        return self._flags
    
    def restore(self, snapshot: int) -> None:
        """Восстанавливает состояние из снимка"""
        old_state = self._flags
        self._flags = snapshot
        self._log_change('restore', 'from_snapshot', old_state, self._flags)
    
    def diff(self, other_mask: int) -> tuple:
        """Находит отличия между масками"""
        added = other_mask & ~self._flags
        removed = self._flags & ~other_mask
        
        added_flags = [name for name, meta in self._registry.items() 
                      if added & meta.mask]
        removed_flags = [name for name, meta in self._registry.items() 
                        if removed & meta.mask]
        
        return added_flags, removed_flags
 
 
# Интеграция с базой данных (концептуально)
class DatabaseBackedPermissions:
    """Пример интеграции с БД"""
    
    def __init__(self, db_connection):
        self.db = db_connection
        self.cache = {}
    
    def get_permissions(self, user_id: int, resource_id: str) -> BitFlagManager:
        """Получает права из БД с кешированием"""
        cache_key = (user_id, resource_id)
        
        if cache_key not in self.cache:
            # Концептуальный запрос: SELECT permission_mask FROM ...
            mask = self._fetch_from_db(user_id, resource_id)
            
            manager = BitFlagManager()
            # Регистрация стандартных флагов
            self._register_standard_flags(manager)
            manager.set_flags_from_mask(mask)
            
            self.cache[cache_key] = manager
        
        return self.cache[cache_key]
    
    def save_permissions(self, user_id: int, resource_id: str, 
                        manager: BitFlagManager) -> None:
        """Сохраняет права в БД"""
        mask = manager.get_mask()
        # Концептуальный запрос: UPDATE ... SET permission_mask = ?
        self._save_to_db(user_id, resource_id, mask)
        
        # Инвалидация кеша
        cache_key = (user_id, resource_id)
        if cache_key in self.cache:
            del self.cache[cache_key]

from functools import wraps
from typing import Callable
 
class PermissionDecorator:
    """Декоратор для проверки прав доступа"""
    
    def __init__(self, permission_manager: ResourcePermissionManager):
        self.pm = permission_manager
    
    def require_permission(self, resource_id: str, *required_perms: str):
        """Требует наличия указанных прав"""
        def decorator(func: Callable) -> Callable:
            @wraps(func)
            def wrapper(*args, **kwargs):
                # Проверяем все требуемые права
                manager = self.pm._get_manager(resource_id)
                
                if not manager.has_all(*required_perms):
                    missing = [p for p in required_perms 
                             if not manager.has_flag(p)]
                    raise PermissionError(
                        f"Недостаточно прав. Требуются: {missing}"
                    )
                
                return func(*args, **kwargs)
            return wrapper
        return decorator
 
# Применение в API
pm = ResourcePermissionManager()
pm.create_resource('document_123')
pm.grant_preset('document_123', 'editor')
 
decorator = PermissionDecorator(pm)
 
@decorator.require_permission('document_123', 'write')
def update_document(content: str):
    """Обновление документа"""
    return f"Документ обновлён: {content[:50]}..."
 
@decorator.require_permission('document_123', 'delete', 'admin')
def delete_document():
    """Удаление требует двух прав одновременно"""
    return "Документ удалён"
 
# Тест декоратора
try:
    result = update_document("Новое содержимое")
    print(f"✓ {result}")
except PermissionError as e:
    print(f"✗ Ошибка: {e}")
 
try:
    delete_document()  # Должно упасть - нет прав admin
except PermissionError as e:
    print(f"✓ Корректная блокировка: {e}")

class RoleHierarchy:
    """Иерархическая система ролей"""
    
    def __init__(self, manager: BitFlagManager):
        self.manager = manager
        self.roles = {}
    
    def define_role(self, role_name: str, flags: List[str]):
        """Определяет роль как набор флагов"""
        mask = 0
        for flag in flags:
            meta = self.manager._get_meta(flag)
            mask |= meta.mask
        self.roles[role_name] = mask
    
    def inherit_role(self, child_role: str, parent_role: str, 
                     additional_flags: List[str] = None):
        """Создаёт дочернюю роль с наследованием прав"""
        parent_mask = self.roles[parent_role]
        child_mask = parent_mask
        
        if additional_flags:
            for flag in additional_flags:
                meta = self.manager._get_meta(flag)
                child_mask |= meta.mask
        
        self.roles[child_role] = child_mask
    
    def assign_role(self, role_name: str):
        """Назначает роль (устанавливает её права)"""
        if role_name not in self.roles:
            raise ValueError(f"Роль '{role_name}' не определена")
        self.manager.set_flags_from_mask(self.roles[role_name])
    
    def get_role_permissions(self, role_name: str) -> List[str]:
        """Список прав роли"""
        mask = self.roles[role_name]
        return [name for name, meta in self.manager._registry.items()
                if mask & meta.mask]
 
# Настройка иерархии
manager = BitFlagManager()
for name, desc in [('read', 'Чтение'), ('write', 'Запись'), 
                   ('delete', 'Удаление'), ('admin', 'Админ')]:
    manager.register_flag(name, desc)
 
hierarchy = RoleHierarchy(manager)
 
# Определяем базовую роль
hierarchy.define_role('viewer', ['read'])
# Расширяем для редактора
hierarchy.inherit_role('editor', 'viewer', ['write'])
# Модератор получает все права редактора плюс удаление
hierarchy.inherit_role('moderator', 'editor', ['delete'])
# Админ - всё
hierarchy.inherit_role('admin', 'moderator', ['admin'])
 
# Назначение роли
hierarchy.assign_role('moderator')
print(f"Права модератора: {manager.get_active_flags()}")  # ['read', 'write', 'delete']