Как проверить, является ли число степенью 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

return i> 0 && (i ^ -i) == (-i << 1); </strong>

Не нашел такого ответа. Пусть это будет мое

Answer 2

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}