Rounding value to nearest power of two

Question

I am looking for the fastest way in C# to round a value to the nearest power of two. I've discovered that the fastest way to round a value to the next power of two if to use bitwise operators like this.

int ToNextNearest(int x)
{
    if (x < 0) { return 0; }
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

But this gives the next nearest and not the nearest and I would like to only have the nearest power of two. Here is a simple way to do that.

int ToNearest(int x)
{
    Math.Pow(2, Math.Round(Math.Log(x) / Math.Log(2)));
}

But is there a better optimized version of finding the nearest power of two value ?

Thanks a lot.

Answer 1

Surely the best way is to use your bitwise routine to find the next power of two, then divide that result by two. This gives you the previous power of two. Then a simple comparison will tell you which of the two is closer.

int ToNearest(int x)
{
  int next = ToNextNearest(x);
  int prev = next >> 1;
  return next - x < x - prev ? next : prev;
}

Untested code but you get the idea.