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

Решение: Проверка на степень двойки

Решение 1: Использование битовых операций (Оптимально)

def is_power_of_two_bitwise(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

Как работает:

• n > 0: Число должно быть положительным
• n & (n - 1) == 0: Если n степень 2, то у него в бинарном представлении только один бит = 1
• Вычитание 1 переворачивает все биты после этого единственного бита
• AND этих двух чисел даст 0

Примеры:

• 8 = 1000 (бинарно)
• 7 = 0111 (бинарно)
• 8 & 7 = 0000 = 0 (степень 2!)
• 10 = 1010 (бинарно)
• 9 = 1001 (бинарно)
• 10 & 9 = 1000 ≠ 0 (не степень 2)

Time Complexity: O(1) Space Complexity: O(1)

Решение 2: С использованием логарифма

import math

def is_power_of_two_log(n: int) -> bool:
    if n <= 0:
        return False
    
    log_val = math.log2(n)
    return log_val == int(log_val)

Как работает:

• log2(8) = 3.0 (точное число)
• log2(10) = 3.321... (не целое число)

Минусы:

• Может быть проблема с точностью при больших числах
• Медленнее чем битовые операции

Решение 3: Проверка через деление

def is_power_of_two_division(n: int) -> bool:
    if n <= 0:
        return False
    
    while n % 2 == 0:
        n = n // 2
    
    return n == 1

Как работает:

• Делим число на 2 пока оно четное
• Если получилось 1, то это была степень 2

Примеры:

• 8: 8 -> 4 -> 2 -> 1 (степень 2!)
• 10: 10 -> 5 (не четное, осталось 5 ≠ 1)

Time Complexity: O(log n) Space Complexity: O(1)

Решение 4: Подсчет количества единиц в бинарном представлении

def is_power_of_two_bit_count(n: int) -> bool:
    if n <= 0:
        return False
    
    # Количество единиц в бинарном представлении
    return bin(n).count('1') == 1

Как работает:

• Преобразуем в бинарную строку
• Считаем количество '1'
• У степеней 2 ровно одна единица

Примеры:

• bin(8) = '0b1000' -> 1 единица (степень 2!)
• bin(10) = '0b1010' -> 2 единицы (не степень 2)

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

# Тестовые данные
test_cases = [
    (1, True),      # 2^0
    (2, True),      # 2^1
    (4, True),      # 2^2
    (8, True),      # 2^3
    (16, True),     # 2^4
    (32, True),     # 2^5
    (64, True),     # 2^6
    (128, True),    # 2^7
    (256, True),    # 2^8
    (1024, True),   # 2^10
    (3, False),
    (5, False),
    (10, False),
    (15, False),
    (100, False),
    (0, False),
    (-8, False),
]

# Тестируем все реализации
for n, expected in test_cases:
    assert is_power_of_two_bitwise(n) == expected
    assert is_power_of_two_division(n) == expected
    assert is_power_of_two_bit_count(n) == expected
    if n > 0:
        assert is_power_of_two_log(n) == expected

print("Все тесты пройдены!")

Визуализация биты операции

Число 8:
  8 = 1000 (бинарно)
  7 = 0111 (бинарно)
8 & 7 = 0000 = 0 ✓ (степень 2!)

Число 10:
  10 = 1010 (бинарно)
   9 = 1001 (бинарно)
10 & 9 = 1000 = 8 ≠ 0 (не степень 2)

Число 16:
  16 = 10000 (бинарно)
  15 = 01111 (бинарно)
16 & 15 = 00000 = 0 ✓ (степень 2!)

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

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

# Проверяем граничные случаи
assert is_power_of_two_bitwise(1) == True    # 2^0
assert is_power_of_two_bitwise(0) == False   # 0 не степень 2
assert is_power_of_two_bitwise(-1) == False  # Отрицательные числа
assert is_power_of_two_bitwise(2**31) == True # Большие числа

Почему работает битовое решение

Степень 2 в бинарном представлении - это число с одной единицей и остальными нулями:

• 1 = 0001
• 2 = 0010
• 4 = 0100
• 8 = 1000
• 16 = 10000

Когда вычтем 1 из степени 2, все биты после единственной единицы переворачиваются:

• 1 - 1 = 0 = 0000
• 2 - 1 = 1 = 0001
• 4 - 1 = 3 = 0011
• 8 - 1 = 7 = 0111
• 16 - 1 = 15 = 01111

AND между ними всегда даст 0!

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

Рекомендуется использовать Решение 1 (битовые операции):

• O(1) временная сложность
• O(1) дополнительная память
• Самое быстрое решение
• Часто встречается на собеседованиях
• Демонстрирует понимание битовых операций

Альтернатива: Решение 3 (деление) - более понятное для всех.