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

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

Формулировка. Дано натуральное число n. Проверить, представляет ли оно собой натуральную степень числа 2.

Решение. Проще говоря, нам нужно ответить на вопрос: можно ли возвести число 2 в какую-либо натуральную степень (или в нулевую степень, так как 2 0 = 1), чтобы получилось число n?

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

n and (n – 1) = 0

Обозначим его как (1).

Дело в том, что натуральная степень числа 2 с показателем p в двоичном виде всегда представляется как единица с pнулями справа. Это происходит потому, что двоичная запись этого числа в десятичном виде представляется как 1 * 2 p + 0 * 2 p–1 + … + 0 * 2 1 + 0 * 2 0 , где все пропущенные слагаемые имеют коэффициент 0, и из этой записи легко восстановить двоичное представление: 10…00, здесь нулей всего p. Поэтому если мы отнимем от любой степени двойки 1, то получим число 1…11, где всего p единиц (точнее говоря, это будет число 01…11). В итоге, если мы применим к этим двум числа побитовую конъюнкцию, то всегда будем получать результирующее число, равное 0.

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

Пример: выполним поразрядную конъюнкцию двоичных чисел 011001₂ и 101011₂ (при этом выпишем их так, чтобы соответствующие двоичные разряды стояли друг под другом):

Первый операнд: 011001₂

Второй операнд: 101011₂

Биты, конъюнкция которых даст 0, выделены красным цветом, а те, конъюнкция которых даст 1 – синим.

Так как 1-й разряд слева у первого числа равен 0, а у второго – 1, то в соответствующий первый разряд результата идет бит 0. 2-е разряды, соответственно, равны 1 и 0, и в результат снова идет бит 0. 3-и разряды у обоих чисел равны 1 (выделены синим цветом), поэтому в 3-й разряд результата идет 1 и так далее.

Кстати, наша формула (1) пропускает число 0 в качестве степени двойки. Так как компиляторы языка Pascal(гарантированно называются Borland Delphi 7 и PascalABC) реализуют числовые типы данных в виде кольцевых отрезков (то есть, например, в типе byte после числа 255 следует число 0, а перед числом 0 – число 255), то в любом таком типе выражение (0 – 1) имеет некоторое ненулевое битовое представление (так как нулевое битовое представление имеет лишь число 0), а побитовая конъюнкция числа 0 и любого другого числа дает в результате число 0.

Вообще, так как нам данное нам n является натуральным числом, число 0 вводиться не будет. Однако покажем, как отсечь 0 при проверке числа по формуле (1): можно осуществить проверку введенного числа на равенство нулю, и в случае равенства заменить его на какое-либо другое число, заведомо не являющееся степенью двойки, чтобы условие формулы (1) отработало правильно:

if n = 0 then n := 3;

Вообще, формула (1) требует доказательства в обе стороны: мы лишь доказали, что если n является степенью двойки, то есть n = 2 p (где p – любое натуральное число или 0), то выражение n and (n – 1) гарантированно дает результат 0. Покажем это схематически еще раз:

Первый операнд: 100…00

Второй операнд: 011…11

Однако мы также должны доказать, что никакое другое число n, кроме как степень двойки, не может дать 0 в результате выполнения операции n and (n – 1). Однако мы примем это утверждение без доказательства. В итоге тело программки может выглядеть так (для натурального n, которое также может быть нулем):

if n = 0 then n := 3;

writeln(n and (n – 1) = 0);

Однако мы в качестве основного решения возьмем более простую идею: пусть данное число n является степенью двойки. Следовательно, его можно представить так: 2 p = 1 * 2 * 2 * … * 2 (здесь ровно p двоек). Разделив это выражение на 2 определенное количество раз, в результате мы получим число 1.

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

1) Вводим n;

2) В цикле с предусловием n > 1 работаем с n:

3) Выводим на экран значение выражения n = 1 (если цикл завершился, то это условие истинно и n – степень двойки, а если нет – то на каком-то шаге мы получили остаток при делении на 2 и вышли через break);

Даже если ввести n, равное 0, то программа выдаст правильный ответ, так как не будет осуществлен вход в цикл (2) и на шаге (3) будет выведено значение выражения 0 = 1, равное false.

Код:

1. program PowerOfTwo;
2. var
3. n: integer;
4. begin
5. readln(n);
6. while n > 1 do begin
7. if n mod 2 = 1 then break;
8. n := n div 2
9. end;
10. writeln(n = 1)
11. end.

Является ли заданное число степенью числа 2?

В этом уроке мы попытаемся проверить, является ли заданное число степенью двойки. Мы решим это, написав эффективный алгоритм, который занимает оптимальное количество времени.

Введение

Давайте зададим еще один сложный вопрос, чтобы проверить ваше понимание побитовых операторов.

Пример 01:

Вывод: True (поскольку 4 равно 2 ^ 2)

Пример 02:

Постановка задачи

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

Давайте рассмотрим число и найдем, как это делает оператор И.

Объяснение

Мы решаем эту проблему, используя оператор & в компьютерах. Есть много способов решить эту проблему, два из которых являются простыми, а один — более сложным, но лучшим решением.

Предположим, что n неотрицательно. Для этого мы используем оператор & .

Решение: метод грубой силы/наивный подход

Подсказка. Самое интересное в вычислении степени двойки состоит в том, что у них количество установленных битов равно единице.

Алгоритм

1. Прочитайте введенное значение.

1. Несколько раз разделите ввод с помощью «2».

• если n не равно 1 и если оно нечетно , мы вернем false .

• иначе истина .

Вот как будет выглядеть наш алгоритм:

Код

экспортировать const IsEven = (n: число): логическое значение =>

вспомогательная функция (значение: число): логическое

если (значение === 0)

в то время как (значение! == 1)

если (значение % 2 !== 0)

Анализ сложности

Временная сложность: O(logn)

Это требует сложности log(n) . Мы можем работать лучше за постоянное время, используя алгоритм Брайана Кернигана.

Пространственная сложность: O(1)

Пространственная сложность O(1) . Он не выделял дополнительного места.

Упражнение по кодированию

Сначала просмотрите приведенные выше фрагменты кода и придумайте решение. Эта задача предназначена для вашей практики, поэтому попробуйте сначала решить ее самостоятельно. Если вы застряли, вы всегда можете обратиться к решению, представленному в разделе решений. Удачи!

экспорт const isPow2 = (n: число): логическое значение =>

// Пишите — Ваш — Код- Здесь

вернуть ложь; // изменить это, вернуть true/false на основе входных данных

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

Я объясню решение ниже.

Давайте посмотрим, как мы используем алгоритм Брайана Кернигана для достижения этой цели.

Обзор решения: алгоритм Брайана Кернигана

Это считается быстрее, чем предыдущий наивный подход.

В этом подходе мы подсчитываем установленные биты. Если число является степенью двойки, мы знаем, что в его двоичном представлении присутствует только один установленный бит.

В двоичном коде мы идем справа налево со степенью двойки.

Алгоритм

Прежде чем говорить об алгоритмических шагах, просмотрите табличную форму шагов, изображающих алгоритм.

1. Если (n & (n — 1) == 0) , вернуть True .

1. иначе Ложь .

Давайте визуализируем значения в таблице ниже:

Давайте посмотрим на пару примеров:

n = 4 => 00000000 00000000 00000000 00000100

п — 1 = 3 => 00000000 00000000 00000000 00000011

(n & (n — 1)) = 0 => 00000000 00000000 00000000 00000000

(n&(n — 1)) , здесь это становится 0 , что является истиной . Следовательно, число «4» является степенью числа 2.

n = 6 => 00000000 00000000 00000000 00000110

п — 1 = 5 => 00000000 00000000 00000000 00000101

(n & (n — 1)) = 4 => 00000000 00000000 00000000 00000100

(n&(n — 1)) равно 4 , что не равно 0 . Следовательно, число «6» не является степенью числа 2.

Рассмотрим оптимизированный подход.

Код

Вот причина этого решения.

экспортировать const IsEven = (n: число): логическое значение =>

вспомогательная функция (значение: число): логическое

если (значение === 0)

Мы можем еще больше упростить этот код до одной строки, показанной ниже.

const IsEven = (n: число): логическое значение =>

Анализ сложности

Временная сложность: O(1)

Время выполнения зависит от количества «1-битов» в «n». В худшем случае все биты в n являются 1-битами . С 32-битным целым числом время выполнения составляет O(1) .

Пространственная сложность: O(1)

Пространственная сложность O(1) . Он не выделял дополнительного места.

Дополнительно

Если вы заинтересованы в освоении битовых трюков, у меня есть курс, который понравился более чем 100 тысячам программистов.

В этом курсе вы узнаете, как решать проблемы, используя манипуляции с битами, мощную технику, которая может оптимизировать ваши алгоритмические навыки и навыки решения проблем. В курсе есть простое объяснение со схемами, подробными пошаговыми рисунками и различными способами решения с помощью побитовых операторов.

Эти битовые трюки могут помочь в соревновательном программировании и собеседованиях по кодированию при запуске алгоритмов, в основном за время O (1) .

Это одна из самых важных/критических тем, когда кто-то готовится к собеседованию по программированию для компаний FAANG (Facebook, Amazon, Apple, Netflix и Google).

Для начала вы начнете с изучения системы счисления и того, как она представлена. Затем вы перейдете к изучению шести различных побитовых операторов: AND, OR, NOT, XOR и битового сдвига. На протяжении всего курса вы получите массу практического опыта, работая над практическими задачами, чтобы улучшить свое понимание.

К тому времени, когда вы закончите этот курс, вы будете решать проблемы быстрее и эффективнее!! ��

Тест «Степени двойки» по информатике для ЕГЭ

Пройдя тестирование за класс вы получите ПОЛНУЮ КАРТИНУ ЗНАНИЙ ПО ВСЕМ ТЕМАМ.
Такой подход позволит глубинно проанализировать знания, вывести успеваемость и понимание предмета на качественно новый уровень.

Пройдя тестирование по одной теме вы получите РЕЗУЛЬТАТ ЗНАНИЙ ТОЛЬКО ЭТОЙ ТЕМЫ, которая, возможно, плохо изучена. Такой метод не является комплексным и дает лишь точечное понимание знаний по предмету.

Данный тест поможет сформировать устойчивый учебный навык, который поможет не только определить, является ли число степенью двойки, но и безошибочно ее указать. Этот навык пригодится при изучении языков программирования, поможет с легкостью решать задачи на ЕГЭ.

Тест состоит примерно из 30 заданий, в каждом из которых нужно будет разложить число на степени двойки или указать результат, полученный при возведении в степень. Писать ничего не потребуется, только указать верный ответ из четырех вариантов, предложенных на экране. Поначалу это может показаться трудным, но после нескольких тренировок вы сможете с легкостью выполнить эту задачу.

Есть и обратное задание. На экране указывается число, являющееся степенью двойки, а вы должны определить, какая это степень, и выбрать правильный ответ. Задания чередуются в произвольном порядке, иногда повторяются. В общей сложности на прохождение теста тратится не более 10 минут.

Для достижения цели – выработки устойчивого учебного навыка вычисления степени без ошибок – требуется несколько повторных тестирований. В первый раз вы можете пройти проверку бесплатно, но затем нужно зарегистрироваться и оплатить доступ к образовательной платформе, чтобы иметь возможность заниматься в удобное время. Алгоритм интеллектуального тренажера выстроен таким образом, что уже после 4-5 дней ежедневных тренировок вырабатывается стойкое умение определять, какая степень двойки скрывается за указанными числами.

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

Как проверить, является ли заданное число степенью двойки. Например: 256 = 2^8 8 = 2^3 Как можно это осуществить в C#?

Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 21 фев 2021 в 12:19
37 1 1 золотой знак 2 2 серебряных знака 5 5 бронзовых знаков

Степень двойки делается простым регистровым сдвигом 2
21 фев 2021 в 12:33
Ага, либо воспользоваться школьными знаниями о логарифмах: взять логарифм по основанию два.
21 фев 2021 в 12:38
21 фев 2021 в 12:49
Для целых, как и в любом С-подобном языке — if ((x & (x — 1)) == 0) < // это степень двойки >
21 фев 2021 в 13:21
Хороший простой вопрос. Не вижу смысла минусовать или ставить флаг за закрытие ¯_(ヅ)_/¯
21 фев 2021 в 13:22

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

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

Там по ссылке ещё много всяких битовых трюков.

Как это трюк работает? А вот как. Запишем число n в двоичной системе, и рассмотрим самую правую единицу в двоичном представлении числа n . У числа n — 1 будет на месте этой единицы ноль, а справа от него единицы:

n : xxxxxx1000 1 : 0000000001 n - 1 : xxxxxx0111 

а остальные двоичные цифры (обозначенные как x ) не поменяются. Поэтому после операции & получится вот что:

n&(n-1): xxxxxx0000 

Это число будет равно нулю тогда и только когда, когда все xxxxxx равны нулю. Единственный случай, где наше соображение не проходит — число 0: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.