Power of Two
Дано целое число n. Верните true, если n является степенью двойки, то есть n = 2^k для некоторого целого числа k ≥ 0, и false в противном случае. Таким образом, подходят 1, 2, 4 и 8, а 0, 6 и все отрицательные числа — нет.
Функция
- ninteger
- целое число для проверки, которое может быть нулём или отрицательным
- Возвращаетboolean
- истинно, если n равно 2^k для некоторого k ≥ 0, иначе ложно
Ограничения
-231 ≤ n ≤ 231-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.
+17 скрытых тестов при отправке
Дополнительный вопрос
Используя те же битовые трюки, можешь ли ты проверить, является ли n степенью четвёрки, без цикла?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Запишите несколько степеней числа 2 в двоичной системе:
1,10,100,1000. Что есть общего у всех них, чего нет у 6 (110)?Степень двойки имеет ровно один бит 1. Сравните
nсn-1в двоичной системе: вычитание 1 меняет младший бит 1 на 0, а каждый бит 0 ниже него — на 1.Итак,
nявляется степенью двойки тогда и только тогда, когда оно положительно, а побитовое И между ним иn-1даёт 0. Проверяй знак до битов, поскольку 0 и отрицательные числа никогда не являются степенями двойки.
Решение
Степень двойки имеет фиксированную форму в двоичной записи: одна единица, за которой следуют нули, например 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. - Верните результат проверки, равно ли теперь
n1.
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++ и JavaScriptn & n - 1 == 0читается какn & ((n - 1) == 0)и даёт неверный ответ без какой-либо ошибки; Java и C# отклоняют это выражение из-за ошибки типа. Пишите(n & (n - 1)) == 0. - Использование логарифмов. При двойной точности
log(536870912) / log(2)даёт 29.000000000000004 вместо 29, поэтому проверка на целое число считает2^29значением false.
Частые вопросы4
Как проверить, является ли число степенью двойки?
Возвращайте 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-битного целого числа.
Является ли 1 степенью двойки? А 0?
1 — это степень двойки, потому что 2^0 = 1, и в её двоичной записи есть один бит со значением 1. 0 — нет: ни одна целая степень не даёт 0, и в его записи вообще нет битов со значением 1. Отрицательные числа тоже никогда не являются степенями двойки.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def isPowerOfTwo(n):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
n = 16
Ожидается
true