Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае. Операцией возведения в степень пользоваться нельзя!

Чтобы определить, является ли данное натуральное число $N$ точной степенью двойки, можно воспользоваться логическим анализом битовой структуры числа. Число $N$ является точной степенью двойки, если оно может быть представлено в виде $2^k$, где $k$ — неотрицательное целое число. Это возможно тогда и только тогда, когда $N > 0$ и в его двоичном представлении присутствует ровно одна единица.

Простое решение задачи без использования операции возведения в степень:

1. Проверка остатка при делении на 2: Повторно делите число $N$ на 2, проверяя каждый раз, делится ли оно без остатка. Если в итоге вы получите 1 и при этом все промежуточные деления были без остатка, значит, $N$ — точная степень двойки. В противном случае — нет.

2. Использование побитовых операций: Для проверки можно использовать свойство двоичных чисел. Если $N$ — точная степень двойки, то выполняется условие:

   $$N \, \& \, (N - 1) = 0$$

   Здесь «&» — это побитовая операция «И». Это работает потому, что в двоичном представлении точной степени двойки есть только одна единица, а $N-1$ обнуляет эту единицу и выставляет все младшие разряды в 1.

Алгоритм проверки:

1. Если $N \leq 0$, сразу выводим NO, так как степень двойки — это только положительное число.
2. Применяем битовую проверку или последовательное деление.
3. Если $N \, \& \, (N - 1) = 0$, выводим YES, иначе NO.

Пример кода на Python:

python
def is_power_of_two(N):
    if N <= 0:
        return "NO"
    if N & (N - 1) == 0:
        return "YES"
    else:
        return "NO"
# Пример использования:
N = int(input("Введите число: "))
print(is_power_of_two(N))

Объяснение работы:

• Если $N = 8$ (двоично: 1000), тогда $N-1 = 7$ (двоично: 0111). При побитовом «И» получится $1000 \& 0111 = 0000$, что подтверждает, что $N$ — точная степень двойки.
• Если $N = 10$ (двоично: 1010), тогда $N-1 = 9$ (двоично: 1001). При побитовом «И» получится $1010 \& 1001 = 1000$, что не равно 0, значит, $N$ не является степенью двойки.

Этот подход эффективен, так как использует минимальное количество операций.