June 3, 2010

I had a hard time finding where I had written this down, and I will almost certainly need it again.

update: More power-of-two fun at Frank's blog with Fast power-of-two modulo.

To find the nearest power of two (linearly) to a given number:

pow(2, int(log(n, 2) + 0.5))

To find the next highest power of two:

int(pow(2, ceil(log(n, 2))))

That's Python code, but pretty much applies in any language. There are some very fast log2 implementations out there if you need them.

Also, if you only have access to log10 in your programming environment (as I did when I worked that out), you might need this:

log2(n) = log10(n) / log10(2)

This is expressed generally as:

logX(n) = logY(n) / logY(X)

(Those two aren't Python code).