Разбор задачи «Лампы на башне»

Идея задачи

Дано целое число n. Нужно определить, является ли оно степенью двойки.

Напомним, что степени двойки — это числа:

• 1
• 2
• 4
• 8
• 16
• 32
• ...

То есть числа вида 2^k, где k ≥ 0.

Например:

• 1 — да
• 8 — да
• 10 — нет
• 0 — нет
• отрицательные числа — нет

Как можно было бы думать сначала

Самая простая идея — много раз делить число на 2, пока это возможно.

Например, для числа 8:

• 8 → 4 → 2 → 1

Всё делилось на 2 без остатка, значит это степень двойки.

А для 10:

• 10 → 5

Дальше уже на 2 без остатка не делится, значит это не степень двойки.

Такой способ работает, но в этой задаче есть более красивое и очень известное битовое решение.

Главное наблюдение

Посмотрим на степени двойки в двоичной записи:

• 1 = 1
• 2 = 10
• 4 = 100
• 8 = 1000
• 16 = 10000

У любой степени двойки в двоичной записи ровно одна единица.

Теперь посмотрим, что будет, если вычесть 1.

Пример: n = 8

8  = 1000
7  = 0111

Если сделать побитовое AND:

1000
0111
----
0000

Получается 0.

Пример: n = 16

16 = 10000
15 = 01111

Снова:

10000
01111
-----
00000

Опять 0.

Почему это работает

Если число является степенью двойки, то его двоичная запись выглядит так:

1000...000

То есть одна единица и дальше только нули.

Тогда число на 1 меньше выглядит так:

0111...111

Единица исчезает, а все биты справа становятся единицами.

Поэтому у чисел n и n - 1 не будет общих единичных битов, и значит:

n & (n - 1) = 0

Почему нужна проверка n > 0

Важно не забыть, что условие

n & (n - 1) == 0

само по себе недостаточно.

Например:

Пример: n = 0

0 & (0 - 1) = 0

Но число 0 не является степенью двойки.

Поэтому правильная проверка такая:

• число должно быть положительным;
• число должно удовлетворять условию (n & (n - 1)) == 0.

Итоговая формула:

n > 0 && (n & (n - 1)) == 0

Алгоритм

1. Считать число n.
2. Если n <= 0, вывести NO.
3. Иначе проверить выражение (n & (n - 1)) == 0.
4. Если оно истинно, вывести YES, иначе вывести NO.

Почему алгоритм корректен

Докажем корректность.

Случай 1. Число n — степень двойки

Тогда в двоичной записи у него ровно одна единица. После вычитания 1 эта единица исчезает, а все биты справа становятся единицами. Значит, в числе n и в числе n - 1 нет общих единичных битов. Следовательно,

n & (n - 1) = 0

Так как n > 0, программа выведет YES.

Случай 2. Число n не является степенью двойки

Тогда возможны два варианта.

• Либо n <= 0. Тогда программа сразу выводит NO, что верно.
• Либо n > 0, но в двоичной записи у числа больше одной единицы. Тогда после вычисления n & (n - 1) хотя бы одна единица останется, и результат не будет равен нулю. Значит программа выведет NO, что тоже верно.

Следовательно, алгоритм правильно определяет, является ли число степенью двойки.

Оценка сложности

Все действия выполняются за постоянное время:

• время: O(1)
• память: O(1)

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;

    if (n > 0 && (n & (n - 1)) == 0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

Реализация на Python

n = int(input())

if n > 0 and (n & (n - 1)) == 0:
    print("YES")
else:
    print("NO")

Разбор примеров

Пример 1

n = 8

Двоичная запись:

8 = 1000
7 = 0111

Тогда:

8 & 7 = 0

Ответ:

YES

Пример 2

n = 10

Двоичная запись:

10 = 1010
9  = 1001

Тогда:

10 & 9 = 1000 ≠ 0

Ответ:

NO

Пример 3

n = 1

Число 1 — это 2^0, значит это степень двойки.

Ответ:

YES

Частые ошибки

Ошибка 1. Забыть проверить, что число положительное

Нельзя писать только так:

if ((n & (n - 1)) == 0)

Потому что для n = 0 это даст неверный результат.

Ошибка 2. Считать, что 0 — степень двойки

0 не представляется в виде 2^k, где k ≥ 0.

Ошибка 3. Путать обычное логическое and и побитовое &

В этой задаче нужен именно побитовый оператор.

• в C++ это &
• в Python это тоже &

Альтернативное решение

Можно решать и так: пока число делится на 2, делить его на 2. Если в конце получим 1, значит это степень двойки.

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;

    if (n <= 0) {
        cout << "NO\n";
        return 0;
    }

    while (n % 2 == 0) {
        n /= 2;
    }

    if (n == 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

Python

n = int(input())

if n <= 0:
    print("NO")
else:
    while n % 2 == 0:
        n //= 2

    if n == 1:
        print("YES")
    else:
        print("NO")

Это решение тоже правильное, но битовый способ обычно считается более красивым и коротким.

Вывод

В этой задаче важно заметить ключевое свойство степени двойки:

• в двоичной записи у неё ровно одна единица.

Из этого сразу получается удобная проверка:

n > 0 and (n & (n - 1)) == 0

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