• 0
Votes
name
name Punditsdkoslkdosdkoskdo

How to check if a number is a power of 2

Today I needed a simple algorithm for checking if a number is a power of 2.

The algorithm needs to be:

  1. Simple
  2. Correct for any ulong value.

I came up with this simple algorithm:

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;
}

But then I thought, how about checking if log2 x is an exactly round number? But when I checked for 2^63+1, Math.Log returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in doubles and not in exact numbers:

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

This returned true for the given wrong value: 9223372036854775809.

Is there a better algorithm?