Как проверить является ли число степенью двойки за O(1)?

Отличный, классический вопрос на знание битовых операций и оптимизацию. Проверка за O(1), то есть за константное время, выполняется с использованием битовых свойств чисел, являющихся степенями двойки.

Математическое и битовое представление

Число, являющееся степенью двойки, в двоичной системе счисления имеет совершенно уникальный вид: оно состоит из одной единицы и нулей в остальных разрядах.

Примеры:

2^0 = 1    -> 00000001
2^1 = 2    -> 00000010
2^2 = 4    -> 00000100
2^3 = 8    -> 00001000
2^4 = 16   -> 00010000
2^5 = 32   -> 00100000

Ключевое наблюдение: для такого числа n (где n > 0) число n - 1 будет иметь строго противоположный битовый вид: все нули после единицы становятся единицами, а сама единица становится нулём.

Пример для n = 8 (2^3):

n     = 8 -> 00001000
n - 1 = 7 -> 00000111

Основной алгоритм O(1)

Если мы выполним побитовое И (&) между числом n и числом n-1, то в результате всегда получим 0, но только при двух условиях:

1. n > 0 (так как ноль не является степенью двойки).
2. n — степень двойки.

n & (n - 1) == 0

Проверим на примерах:

• Для n = 8: 00001000 & 00000111 = 00000000 -> true.
• Для n = 7: 00000111 & 00000110 = 00000110 -> false (не ноль).
• Для n = 0: 00000000 & 11111111 = 00000000 -> true, но это ложное срабатывание! Поэтому ноль нужно обработать отдельно.

Корректная реализация на C#

Вот простая, полностью корректная функция, которая работает за константное время O(1), так как состоит из элементарных операций:

bool IsPowerOfTwo(int n)
{
    // Проверяем, что число положительное И результат побитового И равен нулю.
    return n > 0 && (n & (n - 1)) == 0;
}

Почему это работает за O(1)?

• Вычислительная сложность операции определяется не значением числа, а количеством элементарных шагов.
• Операции >, -, &, == являются базовыми инструкциями процессора и выполняются за один такт, независимо от размера int (в пределах машинного слова, обычно 32 или 64 бита).
• Количество этих операций фиксировано и не зависит от входного значения n. Поэтому алгоритм и работает за константное время O(1).

Дополнительные методы и нюансы

Иногда на собеседовании спрашивают альтернативные способы или просят объяснить детали:

1. Метод с подсчётом единичных битов (популяционный счет):

    Можно проверить, что в двоичном представлении числа ровно одна единица. Это также O(1), но менее эффективно.

```csharp
bool IsPowerOfTwoPopCount(int n)
{
    return n > 0 && System.Numerics.BitOperations.PopCount((uint)n) == 1;
    // PopCount подсчитывает количество установленных битов (единиц).
}
```

2. Проверка через логарифм:

    Этот метод математически красив, но на практике **не является O(1)** для целых чисел из-за погрешностей чисел с плавающей точкой и дороговизны операции `Math.Log`. Его лучше не использовать для точной проверки.

```csharp
// НЕ РЕКОМЕНДУЕТСЯ для точной проверки!
bool IsPowerOfTwoLog(int n)
{
    if (n <= 0) return false;
    double log = Math.Log(n, 2);
    return Math.Abs(log - Math.Round(log)) < 1e-10; // Сравнение с допуском
}
```

3. Важный нюанс: Для числа n = int.MinValue (-2147483648, что в битовом представлении равно 1000...0000) формула n & (n - 1) даст неверный результат, так как n-1 вызовет переполнение. Однако наша функция IsPowerOfTwo вернёт false на первом же условии n > 0, что является корректным поведением, так как степень двойки — положительное число.

Итог: Оптимальным, самым быстрым и каноническим решением для проверки на степень двойки в целых числах является использование выражения n > 0 && (n & (n - 1)) == 0. Оно основано на фундаментальном свойстве двоичного представления таких чисел и выполняется за истинное константное время.