How to check if a number is a power of 2
- by configurator
Today I needed a simple algorithm for checking if a number is a power of 2.
The algorithm needs to be:
Simple
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 log2x 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.
Does anyone have any suggestion for a better algorithm?
