Проверить, является ли натуральное число степенью двойки
Формулировка. Дано натуральное число 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, иначе.
Пример: выполним поразрядную конъюнкцию двоичных чисел 0110012 и 1010112 (при этом выпишем их так, чтобы соответствующие двоичные разряды стояли друг под другом):
Первый операнд: 0110012
Второй операнд: 1010112
Биты, конъюнкция которых даст 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.
Код:
- program PowerOfTwo;
- var
- n: integer;
- begin
- readln(n);
- while n > 1 do begin
- if n mod 2 = 1 then break;
- n := n div 2
- end;
- writeln(n = 1)
- end.
Как проверить, является ли заданное число степенью двойки?
Как проверить, является ли заданное число степенью двойки. Например: 256 = 2^8 8 = 2^3 Как можно это осуществить в C#?
Отслеживать
13.8k 12 12 золотых знаков 44 44 серебряных знака 77 77 бронзовых знаков
задан 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: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.
Найти степень двойки
Почему только перебором. Можно через логарифм. Возможно есть другие способы. Смотря какие ограничения задачи (если они есть).
18 окт 2019 в 17:10
print(math.log2(8))
18 окт 2019 в 17:17
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Вот целых два способа:
n = int(input()) m = 1 i = 0 while m n: print("No") j = 0 while n != 1: if n % 2 == 0: n = n/2 j = j + 1 else: break if n == 1: print(j) else: print("No") Отслеживать
ответ дан 19 окт 2019 в 4:37
12.6k 2 2 золотых знака 19 19 серебряных знаков 46 46 бронзовых знаков
Решить задачу можно либо перебором, либо через логарифм(вот пример кода перебора):
n = int(input()) c = 0 for i in range(0, 1000): if 2 ** i == n: c += 1 print(i) if c == 0: print("НЕТ") Отслеживать
ответ дан 18 окт 2019 в 17:08
Просто Кодер Просто Кодер
301 4 4 серебряных знака 15 15 бронзовых знаков
Есть проблема, не сработает с числом 21430172143725346418968500981200036211228096234110672148875007767407021022498722449863967576313917162551893458351062936503742905713846280871969155149397149607869135549648461970842149210124742283755908364306092949967163882534797535118331087892154125829142392955373084335320859663305248773674411336138752
18 окт 2019 в 17:30
Для этого, можно поменять значение в for до предельного, просто у меня предел был 1000, поэтому я не заморачивался)
Как проверить, является ли число степенью 2 в Python? ����
Для проверки, является ли число степенью двойки в Python, мы можем использовать побитовую операцию «И» между числом и его предыдущим числом в последовательности степеней двойки.
num = 12 is_power_of_two = (num & (num - 1)) == 0 print(is_power_of_two)
В данном примере мы проверяем, является ли число 12 степенью двойки. Результат будет False, так как 12 не является степенью двойки. Если результат равен True, то число является степенью двойки. Данная проверка основана на том, что числа, являющиеся степенями двойки, в двоичном представлении имеют только одну единицу, а предыдущее число в последовательности степеней двойки имеет все биты до этой единицы равные единице.
Детальный ответ
Как проверить, является ли число степенью двойки в Python
В программировании часто возникает необходимость проверить, является ли заданное число степенью двойки. Например, это может быть полезно при работе с битовыми операциями, масками и условиями, зависящими от нечетности числа. Существуют несколько способов проверки, и мы рассмотрим два наиболее популярных подхода.
1. С помощью битовой маски
Один из простых способов проверки, является ли число степенью двойки, состоит в использовании битовой маски. В Python для этого можно воспользоваться операцией побитового «И» между числом и его предшествующим числом в последовательности степеней двойки.
def is_power_of_two(num): return num & (num - 1) == 0 # Пример использования функции number = 16 if is_power_of_two(number): print(f" является степенью двойки") else: print(f" не является степенью двойки")
В данном примере функция is_power_of_two() принимает число num и проверяет, равно ли побитовое «И» числа num и числа num — 1 нулю. Если равно, то число num является степенью двойки.
2. С использованием битового сдвига
Еще один способ проверки заключается в использовании битового сдвига. Если число num является степенью двойки, то при выполнении битового сдвига вправо на 1 позицию, получим число, кратное 2. Таким образом, можно проверить, что результат битового сдвига на 1 вправо и само число делятся на 2 без остатка.
def is_power_of_two(num): return num != 0 and (num & (num - 1)) == 0 # Пример использования функции number = 8 if is_power_of_two(number): print(f" является степенью двойки") else: print(f" не является степенью двойки")
В данном примере функция is_power_of_two() также принимает число num и проверяет, что оно не равно нулю и результат побитового «И» чисел num и num — 1 равен нулю. Если это условие выполняется, то число num является степенью двойки.
Заключение
В данной статье мы рассмотрели два простых способа проверки, является ли число степенью двойки в Python. Оба подхода основаны на работе с битовыми операциями и предоставляют надежные результаты. Важно помнить, что проверка на степень двойки имеет много применений в программировании и может быть полезна при решении различных задач.