Степень двойки

[fortpost]

Как определить, является ли целое положительное число n целой степенью двойки, не используя циклы?

[moonlight]

Код:

        bool Pow2(int n)
        {
            return (n == 1 ? true : ((n & 1) == 1 ? false : Pow2(n >> 1)));
        }

[iPhonograph]

посмотреть на логарифм

[Вилли ☂]

в двоичном коде выглядетъ как 1000...000

[fortpost]

Код:

        bool Pow2(int n)
        {
            return (n == 1 ? true : ((n & 1) == 1 ? false : Pow2(n >> 1)));
        }

А тута рекурсия - это тот же цикл, только ишшо хуже.

[fortpost]

посмотреть на логарифм

Та нема ж двоичных логарифмов в ЯПах, тока натуральные, а тогда погрешность может вылезть.

[fortpost]

в двоичном коде выглядетъ как 1000...000

Да, а дальше что с этим делать?

[Ivan A. Kosarev]

Степень двойки в двоичном представлении -- это единственный взведенный разряд в какой-либо позиции. Если в двоичном представлении степени двойки единственный взведенный разряд имеет позицию b, тогда у числа на единицу меньшего этой степени двойки все разряды младше b будут взведены, а все остальные, включая разряд в позиции b, сброшены. Значит, степень двойки -- это число, которое не равно нулю и не имеет общих взведенных разрядов с числом, на единицу меньшим этой степени двойки.

Код:

int is_power_of_two(unsigned n)
{
    return (n != 0 && (n & (n - 1)) == 0);
}

[Вилли ☂]

* меняем первую единичку на нолик (или отбрасываем его) и число сравниваем с 0

* узнаём кол-во бит числа и сравниваем с соответствующей степенью двойки

* вычитаем единичку -> кол-во бит числа уменьшилось на один   (1000 -> 0111)

* побитовый сдвиг влево/вправо и сравнение с исходным числом

[Вилли ☂]

-

[kinder]

ну вы даёте
return !(n&1);

[Ivan A. Kosarev]

ну вы даёте
return !(n&1);

Это проверка на четность.

[fortpost]

А можно так. Если 2ⁿ делится на n, то n является степенью двойки, если не делится, то не является.