Как проверить, является ли заданное число степенью двойки?
Как проверить, является ли заданное число степенью двойки. Например: 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: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.
Ошибка сервера в приложении ‘/’.
Описание: На сервере возникла ошибка приложения. Текущая пользовательская настройка ошибок для этого приложения не позволяет удаленно просматривать сведения об ошибке данного приложения (из соображений безопасности). Однако, сведения можно просматривать в браузерах, запущенных на локальном сервере.
Сведения: Для разрешения просмотра сведений данного сообщения об ошибке на локальном сервере создайте тег в файле конфигурации «web.config», который находится в корневом каталоге текущего веб-приложения. В теге следует задать атрибут «mode» со значением «Off».
Примечания: Отображаемую в данный момент страницу ошибок можно заменить на пользовательскую страницу ошибок, изменив атрибут «defaultRedirect» тега конфигурации приложения таким образом, чтобы он содержал URL-адрес пользовательской страницы ошибок.
Проверить, является ли натуральное число степенью двойки
Формулировка. Дано натуральное число 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.
Как определить, является ли число степенью двойки на python3?
Проблема в том, что log(16, 2) # = 4.0 по мнению интерпретатора не является целым числом.
Как можно по другому проверить является ли n степенью двойки?
- Вопрос задан более трёх лет назад
- 24647 просмотров
Комментировать
Решения вопроса 2
«I’m here to consult you» © Dogbert
Ох..но, проверять степень двойки с помощью логарифма.
Вот вам идея для решения попроще: n & (n — 1) равно нулю только для нуля и степеней двойки (& — побитовое «и»).
Ответ написан более трёх лет назад
Нравится 2 1 комментарий
boi @xozzslip Автор вопроса
Спасибо большое.
boi @xozzslip Автор вопроса
n = 16 from math import log Logn = log(n, 2) if (Logn == int(Logn)): print "True" else: print "False"Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
Ответы на вопрос 2
Умею рисовать тени
return x && ((x & (x — 1)) == 0); Гугл отключили?
Ответ написан более трёх лет назад
Нравится 1 1 комментарий
object_Object @object_Object
Бляха дошутитесь так и рил отрубят от гуглсервисов
Drugs-driven development
Тебе же в прошлом вопросе разжевали всё, зачем снова плодить глупые вопросы? Но если ты прошлый вопрос спрашивал, чтобы таким образом проверять на степень двойки, то лучше сразу уходи их профессии. Изучи хотя бы основы построения алгоритмов.
Нормальная и быстрая проверка на степень двойки делается через бинарные операции:
def check2rec(num): if num == 1: return True if num & 1: return False return check2rec(num >> 1)Плюс, эту функцию можно ещё пооптимизировать.
Ну и бенчмарки, чтобы доказать ущербность логарифмического метода:
def check2rec(num): if num == 1: return True if num & 1: return False return check2rec(num >> 1) def check2log(num): r = log(num, 2) return int(r) == r numbers = list() print('Generating numbers. ') for _ in range(1000): numbers.append(randint(10000, 1000000)) print('Done!') start = datetime.datetime.now() for _ in range(10000): for n in numbers: check2rec(n) print('Rec: ', datetime.datetime.now() - start) start = datetime.datetime.now() for _ in range(10000): for n in numbers: check2log(n) print('Log: ', datetime.datetime.now() - start)Результаты:
Rec: 0:00:07.408942 Log: 0:00:12.101660Разница почти в 2 раза.
P.S. С такими «знаниями» тебя в более-менее приличное место не возьмут никогда. Изучи сперва программирование (т.е. построение алгоритмов), а не язык. Почитай Вирта, Кормена, или SICP.