Power of Two

Q: Как проверить, является ли число степенью двойки?

Возвращайте true, когда n > 0 и n & (n-1) равно 0. У степени двойки ровно один бит 1, и при вычитании 1 он сбрасывается, а устанавливаются только биты ниже него, поэтому результат операции AND равен 0. Без побитовых операций делите n пополам, пока оно чётное, и проверьте, что в итоге получили 1.

Q: Какова временная сложность алгоритма проверки степени двойки?

Проверка n & (n-1) выполняется за время O(1) и требует O(1) памяти: одно сравнение, одно вычитание и одна операция AND. Цикл с делением пополам выполняется за время O(log n) и занимает не более 31 шага для 32-битного целого числа.

ЛегкоБитовые операции

+10

Дано целое число n. Верните true, если n является степенью двойки, то есть n = 2^k для некоторого целого числа k ≥ 0, и false в противном случае. Таким образом, подходят 1, 2, 4 и 8, а 0, 6 и все отрицательные числа — нет.

Функция

isPowerOfTwo(n: integer) → boolean

ninteger: целое число для проверки, которое может быть нулём или отрицательным
Возвращаетboolean: истинно, если n равно 2^k для некоторого k ≥ 0, иначе ложно

Ограничения

-2³¹ ≤ n ≤ 2³¹-1

Примеры

Ввод: n = 16
Вывод: true
Пояснение: 16 = 2 × 2 × 2 × 2 = 2^4. В двоичной системе это 10000 — один бит со значением 1.

Ввод: n = 24
Вывод: false
Пояснение: 24 = 8 × 3. При делении пополам получаем 12, 6, а затем 3 — это нечётное число, но не 1. В двоичной системе 24 — это 11000, два бита 1.

Ввод: n = 1
Вывод: true
Пояснение: 1 = 2^0, значит, это степень двойки. В двоичной записи 1 ровно один бит равен 1.

Дополнительный вопрос

Используя те же битовые трюки, можешь ли ты проверить, является ли n степенью четвёрки, без цикла?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Степень двойки имеет фиксированную форму в двоичной записи: одна единица, за которой следуют нули, например 10000 для 16. Подтвердить это можно, деля n пополам, пока оно не станет нечётным; на это потребуется до 31 шага. Или можно проверить это за один шаг с помощью n & (n-1): эта операция сбрасывает младший установленный бит и оставляет 0, только если этот бит был единственным. В обеих версиях сначала проверяется знак, потому что с нулём и отрицательными числами очевидный код не работает.

Делите на 2, пока число чётное

Идея

Если n = 2^k, его можно ровно k раз разделить на 2 и получить 1, причём каждое промежуточное значение будет чётным. Если у n есть нечётный множитель больше 1, деление пополам остановится на нечётном числе, которое не равно 1. Для 16: 16, 8, 4, 2, 1, поэтому ответ — true. Для 24: 24, 12, 6, 3, а 3 — нечётное число, не равное 1, поэтому ответ — false.

Возвращайте false для n ≤ 0 до цикла. Степень двойки не может быть нулевой или отрицательной, а цикл никогда не завершится на 0, потому что 0 — чётное число, и половина от 0 по-прежнему равна 0.

На каждом шаге n делится пополам, поэтому для 32-битного входного значения требуется не более 31 шага: время O(log n) и память O(1).

Алгоритм

Если n ≤ 0, верните false.
Пока n чётное, разделите его на 2.
Верните результат проверки, равно ли теперь n 1.

def isPowerOfTwo(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Сбросьте младший установленный бит с помощью n & (n-1)

Идея

Запишите степень двойки в двоичном виде — это будет единица, за которой следуют нули: 16 — это 10000. При вычитании 1 эта единица превращается в 0, а каждый ноль справа от неё — в 1: 15 — это 01111. В этих двух числах нет общих битов, равных 1, поэтому 16 & 15 равно 0.

У любого другого положительного числа есть как минимум два бита, равных 1. При вычитании 1 меняется только младший бит, равный 1, и нули справа от него, поэтому каждый старший бит, равный 1, присутствует в обоих числах, и результат операции AND не равен 0. Для 24, то есть 11000, получаем 23 = 10111, а 24 & 23 равно 10000, то есть 16.

Сначала проверьте n > 0. 0 & -1 равно 0, а в 32-битной арифметике -2^31 — это единственный бит, равный 1, за которым следуют 31 ноль, поэтому одна лишь операция AND сочла бы оба числа степенями двойки. Вся проверка состоит из одного сравнения, одного вычитания и одной операции AND: время и память — O(1). В Lua 5.1 нет оператора AND, поэтому код на Lua выполняет операцию AND побитно, максимум за 31 шаг для 32-битного n; сама проверка остаётся такой же.

Алгоритм

Если n ≤ 0, верните false.
Вычислите n & (n-1) — это n с очищенным младшим битом 1.
Верните, равно ли полученное значение 0.

def isPowerOfTwo(n):
    # One set bit: n - 1 flips it and every bit below, so the AND is 0.
    return n > 0 and n & (n - 1) == 0

Ловушки и крайние случаи

Проверка бита занимает одну строку, и большинство ошибок связано со входными данными, для которых она не предназначена.

Пропуск проверки знака. 0 & (0-1) равно 0, поэтому 0 проходит проверку AND. С 32-битными целыми числами -2^31 тоже проходит проверку, потому что его двоичная форма содержит единственный бит 1. В обоих случаях результатом должно быть false.
Запуск цикла деления пополам для 0. Ноль — чётное число, а деление его пополам снова даёт 0, поэтому цикл никогда не заканчивается.
Пропуск скобок. == имеет более высокий приоритет, чем &, поэтому в C, C++ и JavaScript n & n - 1 == 0 читается как n & ((n - 1) == 0) и даёт неверный ответ без какой-либо ошибки; Java и C# отклоняют это выражение из-за ошибки типа. Пишите (n & (n - 1)) == 0.
Использование логарифмов. При двойной точности log(536870912) / log(2) даёт 29.000000000000004 вместо 29, поэтому проверка на целое число считает 2^29 значением false.

Частые вопросы3

Как проверить, является ли число степенью двойки?

Возвращайте true, когда n > 0 и n & (n-1) равно 0. У степени двойки ровно один бит 1, и при вычитании 1 он сбрасывается, а устанавливаются только биты ниже него, поэтому результат операции AND равен 0. Без побитовых операций делите n пополам, пока оно чётное, и проверьте, что в итоге получили 1.

Почему n & (n-1) сбрасывает младший установленный бит?

При вычитании 1 происходит заимствование у младшего бита, равного 1: этот бит становится 0, а все нули справа от него становятся единицами, тогда как старшие биты остаются неизменными. Побитовое И с исходным числом оставляет только биты, установленные в обоих числах, то есть именно старшие биты. У степени двойки старших битов нет, поэтому результат равен 0.

Какова временная сложность алгоритма проверки степени двойки?

Проверка n & (n-1) выполняется за время O(1) и требует O(1) памяти: одно сравнение, одно вычитание и одна операция AND. Цикл с делением пополам выполняется за время O(log n) и занимает не более 31 шага для 32-битного целого числа.

def isPowerOfTwo(n):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

n = 16

Ожидаемый вывод

true