CODEWITHSUNDEEP
c#timetime-complexity
Muhammad Ali
Muhammad Ali

Reputation: 3536

What is the time complexity of the following Power Of Two code?

I would like to know the time complexity of the following code. If it is not constant time, what is a better solution?

static bool powerOfTwo(double number)
{
    double log = Math.Log(number, 2); 
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

Upvotes: 0

Views: 83

Answers (1)

Probie
Probie

Reputation: 1361

It's constant time, but it's not the fastest constant time solution. If we're happy with incorrect answers on really small doubles (i.e subnormals)

long bits = BitConverter.DoubleToInt64Bits(number);
return (bits & 0xfffffffffffffL == 0L) && number != 0.0;

We simply pull out the mantissa and check that it's zero (well, actually 1, because there's an implicit 1 on all normal doubles). If this is true, the number must be a power of two, or 0. If you want this to work for subnormal numbers it's a bit more work.

Upvotes: 1

Related Questions