Как проверить, является ли заданное число степенью двойки?
Как проверить, является ли заданное число степенью двойки.
Как можно это осуществить в C#?
Там по ссылке ещё много всяких битовых трюков.
Как это трюк работает? А вот как. Запишем число n в двоичной системе, и рассмотрим самую правую единицу в двоичном представлении числа n . У числа n — 1 будет на месте этой единицы ноль, а справа от него единицы:
а остальные двоичные цифры (обозначенные как x ) не поменяются. Поэтому после операции & получится вот что:
Это число будет равно нулю тогда и только когда, когда все xxxxxx равны нулю. Единственный случай, где наше соображение не проходит — число 0: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.
Как проверить, является ли число степенью 2
сегодня мне нужен простой алгоритм для проверки, является ли число степенью числа 2.
алгоритм должен быть:
- простой
- необходимая для любого ulong значение.
Я придумал такой простой алгоритм:
но потом я подумал, как насчет проверки, если log2 x — Это точно круглое число? Но когда я проверил 2^63+1, Math.Log вернулся ровно 63 из-за округлений. Так я проверил, если 2 к мощность 63 равна исходному числу — и это так, потому что расчет производится в double s и не в точных числах:
вернуть true для данного неправильного значения: 9223372036854775809 .
есть ли лучший алгоритм?
21 ответов:
есть простой трюк для этой проблемы:
обратите внимание, эта функция будет отчет true на 0 , который не является силой 2 . Если вы хотите исключить это, вот как:
объяснение
прежде всего побитовый двоичный оператор & из определения MSDN:
бинарные & операторы предопределены для интегральных типов и bool. Для целочисленные типы, & вычисляет логический побитовый И его операндов. Для операндов bool & вычисляет логическое и его операндов; что результат true если и только если оба ее операнда истинны.
теперь давайте посмотрим, как все это происходит:
функция возвращает логическое значение (true / false) и принимает один входящий параметр типа unsigned long (x, в данном случае). Давайте для простоты предположим, что кто-то передал значение 4 и вызвал функцию типа Итак:
теперь мы заменяем каждое вхождение x на 4:
Ну мы уже знаем, что 4 != 0 evals к истине, до сих пор так хорошо. Но как насчет:
это, конечно, переводится так:
но что же такое 4&3 ?
двоичное представление 4 равно 100, а двоичное представление 3-011 (помните, что & принимает двоичное представление этих чисел). Так что мы есть:
представьте, что эти значения складываются так же, как элементарное сложение. Элемент & оператор говорит, что если оба значения равны 1, то результат 1, иначе 0. Так что 1 & 1 = 1 , 1 & 0 = 0 , 0 & 0 = 0 и 0 & 1 = 0 . Итак, мы делаем математику:
результат просто 0. Итак, мы возвращаемся и смотрим на то, что теперь переводит наше заявление о возврате:
что переводится сейчас к:
мы все это знаем true && true просто true , и это показывает, что для нашего примера 4-это степень 2.
Как определить, является ли число степенью двойки на python3?
Проблема в том, что log(16, 2) # = 4.0 по мнению интерпретатора не является целым числом.
Как можно по другому проверить является ли n степенью двойки?
- Вопрос задан более трёх лет назад
- 22483 просмотра
- Вконтакте
- Вконтакте
- Вконтакте
- Вконтакте
Тебе же в прошлом вопросе разжевали всё, зачем снова плодить глупые вопросы? Но если ты прошлый вопрос спрашивал, чтобы таким образом проверять на степень двойки, то лучше сразу уходи их профессии. Изучи хотя бы основы построения алгоритмов.
Нормальная и быстрая проверка на степень двойки делается через бинарные операции:
Является ли число степенью двойки
Эта статья посвящена одной из наипопулярнейших задач в области программирования. Сложно представить себе программиста, который хотя бы раз в своей карьере не сталкивался с ней.
Существует целый ряд способов её решения. В этой статье будут рассмотрены два, наиболее грамотные из них.
Данные методы считаются таковыми не только в силу своей вычислительной эффективности, но и прежде всего потому, что имеют объективное математическое обоснование.
1.Использование битовых операций
Или в варианте C++ и ему подобных языков
Данное число n является степенью числа 2 или числом 0. Отдельное внимание заслуживает число 1, которое является числом 2 в степени 0.
Таким образом, чтобы проверка была корректной необходимо исключить числа 0 и 1. Например, так:
Или в варианте для C++:
2.Использование логарифмов
Этот способ уже был подробно описан в статье «Является ли число степенью другого числа». В данном способе задача проверки, является ли число степенью двойки, рассматривается как частный случай задачи рассмотренной там.
Для выполнения проверки необходимо вычислить логарифм числа по основанию 2 или частное логарифмов проверяемого числа и числа 2 по общему основанию и проверить является ли результат целым числом.
Если используемый язык программирования или библиотека имеют готовую функцию для вычисления логарифма по основанию 2, решение упрощается до предела.