3

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

Например:

256 = 2^8

8 = 2^3

Как можно это осуществить в C#?

7
  • 1
    Степень двойки делается простым регистровым сдвигом 2 << 7 == 128 << 1 == 256. Ну а дальше можно например в цикле перебирать остатком по делению. Либо, как уже наверное догадались, посчитать в числе кол-во бит равных 1. 21 фев 2021 в 12:33
  • Ага, либо воспользоваться школьными знаниями о логарифмах: взять логарифм по основанию два.
    – A K
    21 фев 2021 в 12:38
  • 1
    stackoverflow.com/q/600293/5752652
    – A K
    21 фев 2021 в 12:49
  • Для целых, как и в любом С-подобном языке -- if ((x & (x - 1)) == 0) { // это степень двойки }
    – avp
    21 фев 2021 в 13:21
  • 2
    Хороший простой вопрос. Не вижу смысла минусовать или ставить флаг за закрытие ¯_(ヅ)_/¯
    – Kromster
    21 фев 2021 в 13:22

3 ответа 3

5

Ещё один классический способ:

n > 0 && (n & (n - 1)) == 0

Там по ссылке ещё много всяких битовых трюков.


Как это трюк работает? А вот как. Запишем число n в двоичной системе, и рассмотрим самую правую единицу в двоичном представлении числа n. У числа n - 1 будет на месте этой единицы ноль, а справа от него единицы:

n      : xxxxxx1000
1      : 0000000001
n - 1  : xxxxxx0111

а остальные двоичные цифры (обозначенные как x) не поменяются. Поэтому после операции & получится вот что:

n&(n-1): xxxxxx0000

Это число будет равно нулю тогда и только когда, когда все xxxxxx равны нулю. Единственный случай, где наше соображение не проходит — число 0: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.


Интересно, что gcc и clang выдают на этот код и код из ответа @aepot строго одинаковый ассемблерный код: https://godbolt.org/z/xWx1qT

2
  • ну так, оптимизации в плюсах работают, можно еще JIT ассемблер глянуть.
    – aepot
    21 фев 2021 в 13:33
  • 1
    @aepot: вот
    – VladD
    21 фев 2021 в 13:37
3

Есть простой арифметический способ.

private bool IsPowerOfTwo(int number)
{
    for (int x = 1; x <= number; x *= 2)
    {
        if (x == number) return true;
    }
    return false;
}
Console.WriteLine(IsPowerOfTwo(256));

Но все же к вопросам про двойки всегда приходит лучшим ответом (как правило) двоичная арифметика и немного знаний о том, как числа хранятся в памяти в двоичном виде.

private bool IsPowerOfTwo(int number)
{
    return number > 0 && (number & -number) == number;
}
0
var num = 16;

var log = Math.Log2(num);

if (log - Math.Truncate(log) != 0)
    System.Console.WriteLine($"{num} is not a power of 2.");

Но тут кроется куча проблем.

3

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.