Сумма без оператора плюс

Решение

Задача требует сложить два числа без использования оператора + или арифметических операторов. Это задача, которая демонстрирует понимание битовых операций и принципов работы с числами на низком уровне.

Решение 1: Битовые операции (XOR + AND)

Основной подход — использовать XOR для суммирования битов и AND с левым сдвигом для переноса.

def add_without_plus_iterative(a: int, b: int) -> int:
    """
    Складывает два числа используя битовые операции.
    
    Args:
        a: Первое число
        b: Второе число
    
    Returns:
        Сумма a и b
    
    Time Complexity: O(log n) где n это максимальное число
    Space Complexity: O(1)
    """
    # Маска для работы с 32-битными числами (для обработки отрицательных)
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    
    while b != 0:
        # XOR дает сумму без переносов
        carry = ((a & b) << 1) & MASK
        a = (a ^ b) & MASK
        b = carry
    
    # Преобразуем обратно если число отрицательное
    if a > MAX_INT:
        return ~(a ^ MASK)
    
    return a

Решение 2: Рекурсивный подход с битовыми операциями

Элегантное рекурсивное решение с использованием того же принципа.

def add_without_plus_recursive(a: int, b: int) -> int:
    """
    Рекурсивное сложение с использованием битовых операций.
    
    Args:
        a: Первое число
        b: Второе число
    
    Returns:
        Сумма a и b
    
    Time Complexity: O(log n)
    Space Complexity: O(log n) из-за стека рекурсии
    """
    # Базовый случай: нет переноса
    if b == 0:
        return a
    
    # Рекурсивный случай
    sum_without_carry = a ^ b  # XOR без переносов
    carry = (a & b) << 1       # AND со сдвигом для переноса
    
    return add_without_plus_recursive(sum_without_carry, carry)

Решение 3: Использование встроенных функций Python

Python может обрабатывать числа любого размера, поэтому нужна адаптация.

def add_without_plus_python(a: int, b: int) -> int:
    """
    Сложение для Python (без ограничения на 32 бита).
    
    Args:
        a: Первое число
        b: Второе число
    
    Returns:
        Сумма a и b
    
    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    # Python поддерживает числа произвольного размера
    # Для работы с отрицательными числами нужна специальная обработка
    
    while b != 0:
        # Получаем сумму без переносов и сам перенос
        carry = (a & b) << 1
        a = a ^ b
        b = carry
    
    return a

Примеры использования

# Положительные числа
print(add_without_plus_iterative(5, 7))       # 12
print(add_without_plus_recursive(5, 7))       # 12
print(add_without_plus_python(5, 7))          # 12

# Большие числа
print(add_without_plus_iterative(100, 200))   # 300

# Одно число равно нулю
print(add_without_plus_iterative(0, 5))       # 5
print(add_without_plus_iterative(10, 0))      # 10

# Одинаковые числа
print(add_without_plus_iterative(5, 5))       # 10

# Отрицательные числа (для полной реализации)
print(add_without_plus_iterative(-5, 10))     # 5

Объяснение битовых операций

Как работает логика:

1. XOR (^): Дает сумму битов БЕЗ переносов

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

2. AND (&): Показывает где возникают переносы

   • 0 & 0 = 0
   • 0 & 1 = 0
   • 1 & 0 = 0
   • 1 & 1 = 1 (ПЕРЕНОС!)

3. Левый сдвиг (<<): Смещает перенос на позицию влево

Пример: 5 + 7 = 12

a = 5 (0101)
b = 7 (0111)

Итерация 1:
sum_without_carry = 0101 ^ 0111 = 0010 (2)
carry = (0101 & 0111) << 1 = 0101 << 1 = 1010 (10)

Итерация 2:
a = 0010 (2)
b = 1010 (10)
sum_without_carry = 0010 ^ 1010 = 1000 (8)
carry = (0010 & 1010) << 1 = 0010 << 1 = 0100 (4)

Итерация 3:
a = 1000 (8)
b = 0100 (4)
sum_without_carry = 1000 ^ 0100 = 1100 (12)
carry = (1000 & 0100) << 1 = 0000 << 1 = 0000 (0)

b == 0, возвращаем a = 12

Решение 4: С использованием eval (не рекомендуется, но возможно)

def add_with_eval(a: int, b: int) -> int:
    """
    Решение с использованием eval — только для демонстрации.
    НЕ РЕКОМЕНДУЕТСЯ для продакшена.
    """
    return eval(f"{a}.__add__({b})")

Сравнение подходов

Граничные случаи

# Нулевые значения
add_without_plus_iterative(0, 0)      # 0
add_without_plus_iterative(0, 5)      # 5

# Одинаковые числа
add_without_plus_iterative(3, 3)      # 6

# Разные знаки
add_without_plus_iterative(10, -5)    # 5
add_without_plus_iterative(-10, 5)    # -5

# Противоположные числа
add_without_plus_iterative(5, -5)     # 0

Для QA автоматизации

Рекомендуется Решение 1 (итеративное):

• Работает с любыми 32-битными числами
• Корректно обрабатывает отрицательные числа
• Понятная логика без рекурсии
• Часто требуется на собеседованиях в крупных компаниях