Степень двойки
Удваиваем степень, пока следующее удвоение ещё допустимо.
Как к ней подойти
Разберитесь, как повторять действие, пока выполняется условие, и вовремя остановить цикл.
Цикл while продолжается, пока условие истинно. Продумайте, какое значение меняется на каждом шаге и почему цикл когда-нибудь завершится. Проверяйте как обычный ввод, так и случай, когда тело цикла выполняется ноль раз.
Инвариант: power — степень двойки с показателем exponent.
Проверьте перед запуском
- При N=1 показатель равен нулю, степень равна единице.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Последовательное удвоение
Инвариант: power — степень двойки с показателем exponent.
n = int(input())
power, exponent = 1, 0
while power * 2 <= n:
power *= 2
exponent += 1
print(exponent, power)
Время: O(log N). Память: O(1) целых чисел.
Другой способ: Длина двоичной записи
Старший единичный бит задаёт нужную степень. Сдвиг не использует операцию возведения в степень.
n = int(input())
k = n.bit_length() - 1
print(k, 1 << k)
Время: O(log N) с учётом создания результата в битовой модели. Память: O(log N) бит.