Эта статья посвящена одной из наипопулярнейших задач в области программирования. Сложно представить себе программиста, который хотя бы раз в своей карьере не сталкивался с ней.
Существует целый ряд способов её решения. В этой статье будут рассмотрены два, наиболее грамотные из них.
Данные методы считаются таковыми не только в силу своей вычислительной эффективности, но и прежде всего потому, что имеют объективное математическое обоснование.
1.Использование битовых операций
Если
1 |
n and (n-1) =0 |
Или в варианте C++ и ему подобных языков
1 |
n & (n-1) == 0 |
Данное число n является степенью числа 2 или числом 0. Отдельное внимание заслуживает число 1, которое является числом 2 в степени 0.
Таким образом, чтобы проверка была корректной необходимо исключить числа 0 и 1. Например, так:
1 2 3 4 5 6 7 8 |
var n: Integer; … if (n > 1) then if n and (n - 1) = 0 then WriteLn('Yes') else WriteLn('No'); |
Или в варианте для C++:
1 2 3 4 5 6 7 8 9 10 |
int n ; … if ((n&(n - 1)) == 0) { printf("Yes"); } else { printf("No"); } |
2.Использование логарифмов
Этот способ уже был подробно описан в статье «Является ли число степенью другого числа». В данном способе задача проверки, является ли число степенью двойки, рассматривается как частный случай задачи рассмотренной там.
Для выполнения проверки необходимо вычислить логарифм числа по основанию 2 или частное логарифмов проверяемого числа и числа 2 по общему основанию и проверить является ли результат целым числом.
Если используемый язык программирования или библиотека имеют готовую функцию для вычисления логарифма по основанию 2, решение упрощается до предела.
Вариант для Delphi:
1 2 3 4 5 6 7 |
function IsPower2(n: Штеупук): boolean; begin if (n>1) then result := (Trunc(Log2(n)) = Log2(n)); else result:=false; end; |
Вариант для C++:
1 2 3 4 5 6 7 8 9 10 11 |
bool isPower2(int n) { if (n>1) { return (double)((int)log2(n)) == log2(n); } else { return false } } |
Так же как и в предыдущем способе необходимо исключить числа 1 и 0. Особенно 0, так как иначе программа выдаст ошибку.
Помимо двух вышеприведённых, существуют и другие способы проверить, является ли число степенью числа 2. Но по своей простоте и, главное, эффективности они не могут с ними соперничать. Поэтому их использование нежелательно.
Добавить комментарий