Как проверить, является ли число степенью 2

Question

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

Алгоритм должен быть:

1. Simple
2. Правильно для любого значения ulong.

Я придумал этот простой алгоритм:

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

Но тогда я подумал, а как насчет проверки, является ли log<sub>2</sub> x точно круглым числом? Но когда я проверил на 2 ^ 63 + 1, Math.Log вернул ровно 63 из-за округления. Поэтому я проверил, равно ли 2 степени 63 исходному числу - и это так, потому что вычисление выполняется в double с, а не в точных числах:

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

Это вернуло true для данного неправильного значения: 9223372036854775809.

Есть ли лучший алгоритм?

Answer 1

Для этой проблемы есть простой трюк:

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

Обратите внимание, эта функция выдаст true для 0, что не является степенью 2. Если вы хотите исключить это, вот как:

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Объяснение

Прежде всего побитовый двоичный оператор & из определения MSDN:

Двоичные & операторы предопределены для целочисленных типов и bool. За целочисленные типы & вычисляют логическое побитовое И своих операндов. Для булевых операндов & вычисляет логическое И своих операндов; тот результат равен true, если и только если оба его операнда имеют значение true.

Теперь давайте посмотрим, как все это закончится:

Функция возвращает логическое значение (true / false) и принимает один входящий параметр типа unsigned long (в данном случае x). Давайте для простоты предположим, что кто-то передал значение 4 и вызвал функцию следующим образом:

bool b = IsPowerOfTwo(4)

Теперь мы заменим каждое вхождение x на 4:

return (4 != 0) && ((4 & (4-1)) == 0);

Ну, мы уже знаем, что 4! = 0 - это правда, пока все хорошо. Но как насчет:

((4 & (4-1)) == 0)

Это, конечно, означает:

((4 & 3) == 0)

Но что именно 4&3?

Двоичное представление 4 равно 100, а двоичное представление 3 - 011 (помните, что & принимает двоичное представление этих чисел). Итак имеем:

100 = 4
011 = 3

Представьте, что эти значения складываются во многом как элементарное сложение. Оператор & говорит, что если оба значения равны 1, то результат равен 1, в противном случае он равен 0. Итак, 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0 и 0 & 1 = 0. Итак, мы делаем математику:

100
011
----
000

Результат просто 0. Итак, мы вернемся и посмотрим, что наш оператор возврата теперь переводит:

return (4 != 0) && ((4 & 3) == 0);

Что теперь означает:

return true && (0 == 0);

return true && true;

Мы все знаем, что true && true - это просто true, и это показывает, что для нашего примера 4 - это степень 2.

Answer 2

Некоторые сайты, которые документируют и объясняют этот и другие хитрые взломы:

• http://graphics.stanford.edu/~seander/bithacks.html
  (http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
• http://bits.stephan -brumme.com /
  (http://bits.stephan -brumme.com / isPowerOfTwo.html )

И их дедушка, Книга Генри Уоррена-младшего "Восхищение Хакера" :

• http://www.hackersdelight.org/

Как показывает страница Шона Андерсона , выражение ((x & (x - 1)) == 0) неверно указывает, что 0 - это степень 2. Он предлагает использовать:

(!(x & (x - 1)) && x)

чтобы исправить эту проблему.

Answer 3

return (i & -i) == i

Answer 4

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

Answer 5

Недавно я написал статью об этом на http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/. В ней описывается подсчет битов, правильное использование логарифмов, классическая проверка "x &&! (X & (x - 1))" и другие.

Answer 6

Вот простое решение C ++ :

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

Answer 7

После публикации вопроса я подумал о следующем решении:

Нам нужно проверить, является ли ровно одна из двоичных цифр единицей. Таким образом, мы просто сдвигаем число на одну цифру за раз и возвращаем true, если оно равно 1. Если в любой точке мы получаем нечетное число ((number & 1) == 1), мы знаем, что результат равен false. Это оказалось (с помощью эталона) немного быстрее, чем оригинальный метод для (больших) истинных значений и намного быстрее для ложных или малых значений.

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

---

Конечно, решение Грега намного лучше.

Answer 8

    bool IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

А вот общий алгоритм определения, является ли число степенью другого числа.

    bool IsPowerOf(int n,int b)
    {
        if (n > 1)
        {
            while (n % b == 0)
            {
                n /= b;
            }
        }
        return n == 1;
    }

Answer 9

Следующее дополнение к принятому ответу может быть полезно для некоторых людей:

Степень двойки, выраженная в двоичном виде, всегда будет выглядеть как 1, за которым следуют n нулей , где n больше или равно 0. Пример:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

и т. Д.

Когда мы вычитаем 1 из таких чисел, они становятся 0, за которыми следуют n единиц , и снова n такое же, как указано выше. Пример:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

и т. Д.

Подходя к сути

Что происходит, когда мы делаем побитовое И из числа x, которое является сила 2, а x - 1?

Один из x выравнивается с нулем x - 1, а все нули x выравниваются с нулями x - 1, в результате чего побитовое И приводит к 0. И именно так у нас вышеупомянутый однострочный ответ является правильным.

---

Дальнейшее добавление к красоте принятого ответа выше -

Итак, в нашем распоряжении есть имущество:

Когда мы вычитаем 1 из любого числа, то в двоичном представлении крайний правый 1 станет 0 и все нули до этого самого правого 1 теперь станет 1

Одним из удивительных применений этого свойства является выяснение - Сколько единиц присутствует в двоичном представлении заданного числа? Короткий и приятный код для этого для заданного целого числа x: :

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

---

Другим аспектом чисел, который может быть доказан из концепции, объясненной выше, является «Может ли каждое положительное число быть представлено как сумма степеней 2?» .

Да, каждое положительное число может быть представлено как сумма степеней 2. Для любого числа возьмите его двоичное представление. Пример: взять номер 501.

The binary of 501 is 111110101

Because  111110101 = 100000000 + 10000000 + 1000000 + 100000 + 1000 + 000 + 100 + 00 + 1
we have  501       = 256       + 128      + 64      + 32     + 16   + 0   + 4   + 0  + 1

Answer 10

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;