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

Эта статья посвящена одной из наипопулярнейших задач в области программирования. Сложно представить себе программиста, который хотя бы раз в своей карьере не сталкивался с ней.

Существует целый ряд способов её решения. В этой статье будут рассмотрены два, наиболее грамотные из них.

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

1.Использование битовых операций

Если

Или в варианте C++ и ему подобных языков

Данное число n является степенью числа 2 или числом 0. Отдельное внимание заслуживает число 1, которое является числом 2 в степени 0.

Таким образом, чтобы проверка была корректной необходимо исключить числа 0 и 1. Например, так:

Или в варианте для C++:

2.Использование логарифмов

Этот способ уже был подробно описан в статье «Является ли число степенью другого числа». В данном способе задача проверки, является ли число степенью двойки, рассматривается как частный случай задачи рассмотренной там.

Для выполнения проверки необходимо вычислить логарифм числа по основанию 2 или частное логарифмов проверяемого числа и числа 2 по общему основанию и проверить является ли результат целым числом.

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

Вариант для Delphi:

Вариант для C++:

Так же как и в предыдущем способе необходимо исключить числа 1 и 0. Особенно 0, так как иначе программа выдаст ошибку.

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

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

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