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

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

  • автор:

Ошибка сервера в приложении ‘/’.

Описание: На сервере возникла ошибка приложения. Текущая пользовательская настройка ошибок для этого приложения не позволяет удаленно просматривать сведения об ошибке данного приложения (из соображений безопасности). Однако, сведения можно просматривать в браузерах, запущенных на локальном сервере.

Сведения: Для разрешения просмотра сведений данного сообщения об ошибке на локальном сервере создайте тег в файле конфигурации «web.config», который находится в корневом каталоге текущего веб-приложения. В теге следует задать атрибут «mode» со значением «Off».

Примечания: Отображаемую в данный момент страницу ошибок можно заменить на пользовательскую страницу ошибок, изменив атрибут «defaultRedirect» тега конфигурации приложения таким образом, чтобы он содержал URL-адрес пользовательской страницы ошибок.

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

Напишите функцию JavaScript, чтобы проверить, является ли число степенью двойки.
Примечание:
Последовательность чисел, первое из которых равно 1, а каждое последующее вдвое больше: 1, 2, 4, 8, 16, . можно записать в эквивалентном виде: 2 0 , 2 1 , 2 2 , 2 3 , 2 4 , . Называется она: последовательность степеней двойки.
Никаких отрицательных чисел и дробей.
Данные теста :
document.write(power_of_2 (16));
document.write(power_of_2 (18));
document.write(power_of_2 (256));
Вывод :
true
false
true

Выполнить код » Скрыть результаты

Примечание: Оператор & — возвращает единицу в каждой битовой позиции, для которой соответствующие биты обеих операндов являются единицами.

Kwork.ru - услуги фрилансеров от 500 руб.

Есть другой способ решить эту задачу? Разместите свой код (и комментарии) через Disqus.

Комментарии

пожелания к комментариям…

  • Приветствуются комментарии, соответствующие теме урока: вопросы, ответы, предложения.
  • Одну строчку кода оборачивайте в тег , несколько строчек кода — в теги
    . ваш код.

    .

  • Допускаются ссылки на онлайн-песочницы (codepen, plnkr, JSBin и др.).

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

Формулировка. Дано натуральное число 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.

Код:

  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.

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

Проблема в том, что log(16, 2) # = 4.0 по мнению интерпретатора не является целым числом.

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

  • Вопрос задан более трёх лет назад
  • 24938 просмотров

Комментировать
Решения вопроса 2
"I'm here to consult you" © Dogbert

Ох..но, проверять степень двойки с помощью логарифма.
Вот вам идея для решения попроще: n & (n - 1) равно нулю только для нуля и степеней двойки (& -- побитовое "и").

Ответ написан более трёх лет назад
Нравится 2 1 комментарий

xozzslip

boi @xozzslip Автор вопроса
Спасибо большое.

xozzslip

boi @xozzslip Автор вопроса

n = 16 from math import log Logn = log(n, 2) if (Logn == int(Logn)): print "True" else: print "False"

Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
Ответы на вопрос 2

donkaban

Умею рисовать тени
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.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *