Перевод в двоичную систему

Перевод в двоичную систему

Задача: Преобразовать десятичное число в двоичное представление без встроенной функции bin().

Решение 1: Итеративный подход (классический)

Это наиболее прямолинейный способ — последовательно делим число на 2 и собираем остатки в обратном порядке:

def to_binary(n):
    """
    Преобразует десятичное число в двоичное представление.
    
    Алгоритм:
    1. Пока число > 0:
       - Берём остаток от деления на 2 (0 или 1)
       - Добавляем его в начало строки результата
       - Делим число на 2 (целочисленно)
    2. Возвращаем результат
    """
    if n == 0:
        return "0"
    
    binary = ""
    while n > 0:
        binary = str(n % 2) + binary  # Остаток от деления на 2
        n = n // 2                     # Целочисленное деление на 2
    
    return binary

# Примеры
print(to_binary(10))    # "1010"
print(to_binary(255))   # "11111111"
print(to_binary(1))     # "1"
print(to_binary(0))     # "0"
print(to_binary(127))   # "1111111"

Как это работает на примере to_binary(10):

n = 10

Итерация 1: 10 % 2 = 0, 10 // 2 = 5, binary = "0"
Итерация 2: 5 % 2 = 1,  5 // 2 = 2, binary = "10"
Итерация 3: 2 % 2 = 0,  2 // 2 = 1, binary = "010"
Итерация 4: 1 % 2 = 1,  1 // 2 = 0, binary = "1010"

Результат: "1010"

Решение 2: С использованием списка (более эффективно)

Замена строк на список быстрее, так как строки неизменяемы в Python:

def to_binary_optimized(n):
    """
    Оптимизированная версия с использованием списка.
    Быстрее, так как не создаёт новые строки при каждой итерации.
    """
    if n == 0:
        return "0"
    
    binary_list = []
    while n > 0:
        binary_list.append(str(n % 2))
        n = n // 2
    
    return "".join(reversed(binary_list))

print(to_binary_optimized(10))    # "1010"
print(to_binary_optimized(255))   # "11111111"

Решение 3: Рекурсивный подход

def to_binary_recursive(n):
    """
    Рекурсивное решение.
    
    Базовый случай: n == 0 → возвращаем пустую строку
    Рекурсивный случай: остаток(n, 2) + to_binary(n // 2)
    """
    if n == 0:
        return ""
    else:
        return to_binary_recursive(n // 2) + str(n % 2)

print(to_binary_recursive(10))    # "1010"
print(to_binary_recursive(255))   # "11111111"

# Обработка крайнего случая
def to_binary_recursive_safe(n):
    """Версия, которая корректно обрабатывает 0."""
    if n == 0:
        return "0"
    
    def helper(n):
        if n == 0:
            return ""
        return helper(n // 2) + str(n % 2)
    
    return helper(n)

print(to_binary_recursive_safe(0))  # "0"
print(to_binary_recursive_safe(10)) # "1010"

Решение 4: Используя побитовые операции

def to_binary_bitwise(n):
    """
    Альтернативный подход с побитовыми операциями.
    Проверяем каждый бит числа с помощью побитового И (&).
    """
    if n == 0:
        return "0"
    
    binary = ""
    # Находим количество битов
    bit_length = n.bit_length()  # Встроенный метод
    
    # Проходим по всем битам справа налево
    for i in range(bit_length - 1, -1, -1):
        # Проверяем бит на позиции i
        if n & (1 << i):
            binary += "1"
        else:
            binary += "0"
    
    return binary

print(to_binary_bitwise(10))    # "1010"
print(to_binary_bitwise(255))   # "11111111"

Решение 5: Используя divmod() для изящности

def to_binary_divmod(n):
    """
    Использует divmod() для одновременного получения
    частного и остатка.
    """
    if n == 0:
        return "0"
    
    binary = ""
    while n > 0:
        n, remainder = divmod(n, 2)  # (quotient, remainder)
        binary = str(remainder) + binary
    
    return binary

print(to_binary_divmod(10))    # "1010"
print(to_binary_divmod(255))   # "11111111"

Сравнение решений

import time

def benchmark(func, n, iterations=100000):
    start = time.time()
    for _ in range(iterations):
        func(n)
    end = time.time()
    return end - start

n = 1000

print(f"Итеративный (строка):    {benchmark(to_binary, n):.4f}s")
print(f"Оптимизированный (список): {benchmark(to_binary_optimized, n):.4f}s")
print(f"Рекурсивный:             {benchmark(to_binary_recursive_safe, n):.4f}s")
print(f"divmod:                  {benchmark(to_binary_divmod, n):.4f}s")

# Результат: версия со списком обычно быстрее строковой версии

Полное решение с тестами

def to_binary(n):
    """Преобразует десятичное число в двоичную строку."""
    if n == 0:
        return "0"
    if n < 0:
        # Для отрицательных чисел можно добавить знак
        return "-" + to_binary(-n)
    
    binary = ""
    while n > 0:
        binary = str(n % 2) + binary
        n = n // 2
    return binary

# Тесты
test_cases = [
    (0, "0"),
    (1, "1"),
    (2, "10"),
    (10, "1010"),
    (255, "11111111"),
    (256, "100000000"),
    (1024, "10000000000"),
    (-10, "-1010"),
]

for num, expected in test_cases:
    result = to_binary(num)
    status = "✓" if result == expected else "✗"
    print(f"{status} to_binary({num:4}) = {result:12} (ожидается {expected})")

Анализ сложности

Временная сложность:

• O(log n) — количество операций равно количеству битов в числе
• Для числа n нужно ~log₂(n) операций деления

Пространственная сложность:

• O(log n) — длина результирующей строки (~log₂(n) символов)

Рекомендация

Для практического использования выбираю Решение 2 (со списком), так как оно:

• Читаемо и понятно
• Эффективнее строковой версии (O(log n) вместо O((log n)²) из-за конкатенации строк)
• Не требует рекурсии (нет риска StackOverflow)
• Проще для отладки