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

Решение

Подход

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

Примеры в двоичной системе:

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

Оптимальное решение O(1)

func isPowerOfTwo(_ n: Int) -> Bool {
    return n > 0 && (n & (n - 1)) == 0
}

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

Битовое выражение n & (n - 1) удаляет самый правый установленный бит из числа n.

Пример с 16 (binary: 10000):

n     = 16      →  10000 (binary)
n - 1 = 15      →  01111 (binary)
n & (n-1) = 0   →  00000 (binary)

Для степени двойки (один бит установлен):

• n & (n - 1) всегда даёт 0

Для не-степени двойки (несколько битов установлены):

• n & (n - 1) даёт ненулевое значение

Пример с 12 (binary: 1100):

n     = 12      →  1100 (binary)
n - 1 = 11      →  1011 (binary)
n & (n-1) = 8   →  1000 (binary) ≠ 0

Альтернативные решения

1. Через логарифм:

func isPowerOfTwo(_ n: Int) -> Bool {
    guard n > 0 else { return false }
    let log = log2(Double(n))
    return log == floor(log)
}

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

2. Через битовый счёт:

func isPowerOfTwo(_ n: Int) -> Bool {
    guard n > 0 else { return false }
    // Считаем количество установленных битов
    return n.nonzeroBitCount == 1
}

Это читаемо и тоже O(1) на большинстве платформ.

3. Через цикл (O(log n)):

func isPowerOfTwo(_ n: Int) -> Bool {
    guard n > 0 else { return false }
    var num = n
    while num % 2 == 0 {
        num /= 2
    }
    return num == 1
}

Это работает, но медленнее (не O(1)).

Тестирование

// Степени двойки (должны быть true)
print(isPowerOfTwo(1))      // true  (2^0)
print(isPowerOfTwo(2))      // true  (2^1)
print(isPowerOfTwo(4))      // true  (2^2)
print(isPowerOfTwo(8))      // true  (2^3)
print(isPowerOfTwo(16))     // true  (2^4)
print(isPowerOfTwo(256))    // true  (2^8)
print(isPowerOfTwo(1024))   // true  (2^10)

// Не степени двойки (должны быть false)
print(isPowerOfTwo(0))      // false (не положительное)
print(isPowerOfTwo(3))      // false
print(isPowerOfTwo(5))      // false
print(isPowerOfTwo(12))     // false (1100 в двоичной)
print(isPowerOfTwo(15))     // false (1111 в двоичной)
print(isPowerOfTwo(-16))    // false (отрицательное)

// Граничные случаи
print(isPowerOfTwo(Int.max))     // false
print(isPowerOfTwo(Int.min))     // false
print(isPowerOfTwo(1 << 30))     // true (2^30)

Почему работает n & (n - 1) == 0?

Математическое объяснение:

Вычитание 1 из степени двойки в двоичной системе даёт очень специфичный результат:

• Все нули справа от единицы становятся единицами
• Сама единица становится нулём

Пример:

16 (10000) - 1 = 15 (01111)
32 (100000) - 1 = 31 (011111)
64 (1000000) - 1 = 63 (0111111)

После операции AND все биты становятся 0, потому что нет совпадающих единиц.

Для других чисел остаётся хотя бы один общий бит:

12 (1100) - 1 = 11 (1011)
12 & 11 = 1000 (8) ≠ 0

Производительность

// Сравнение скорости
import Foundation

func measureTime(name: String, _ closure: () -> Void) {
    let start = Date()
    closure()
    let elapsed = Date().timeIntervalSince(start)
    print("\(name): \(elapsed) seconds")
}

measureTime(name: "Bitwise") {
    for n in 1...1_000_000_000 {
        _ = n > 0 && (n & (n - 1)) == 0
    }
}

measureTime(name: "nonzeroBitCount") {
    for n in 1...1_000_000_000 {
        _ = n > 0 && n.nonzeroBitCount == 1
    }
}

Практическое применение

Это знание используется в:

• Хэш-таблицах — выделение памяти степенями двойки
• Graphics API — текстуры часто требуют степени двойки
• Битовых операциях — оптимизация по памяти и производительности
• Алгоритмах — поиск, сортировка, битовые маски

Рекомендация для интервью

Используйте первое решение:

func isPowerOfTwo(_ n: Int) -> Bool {
    return n > 0 && (n & (n - 1)) == 0
}

Это:

• Демонстрирует знание побитовых операций
• O(1) по времени и памяти
• Очень кратко и элегантно
• Показывает глубокое понимание двоичной системы

Если интервьюер спросит о альтернативах:

// Более явный вариант
func isPowerOfTwo(_ n: Int) -> Bool {
    guard n > 0 else { return false }
    return n.nonzeroBitCount == 1
}

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

Объяснение на интервью

"Степени двойки в двоичной системе имеют ровно один установленный бит. Когда мы вычитаем 1 из степени двойки, все биты справа от этого единственного бита становятся 1, а сам бит становится 0. Операция AND между исходным числом и результатом вычитания даёт 0, только если исходное число было степенью двойки."