(rss)
June 3, 2010
Nearest power of two

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).

2 years, 11 months ago - Mon 07 Apr 2014
Maria

Hi I type your expression for next highest power of two and i get an answer: In [9]: n=1000

In [10]: int(pow(2, ceil(log(n, 2))))

TypeError Traceback (most recent call last) in () ----> 1 int(pow(2, ceil(log(n, 2))))

TypeError: return arrays must be of ArrayType

Any hint? thanks in advance, Maria

2 years, 11 months ago - Thu 17 Apr 2014

I'm sorry Maria, I tried it on various versions of Python and it always works for me. I am not sure why you would be getting that error.

2 years, 1 month ago - Fri 06 Feb 2015
Kwame

Maria, I have had the same problem. You need to import the math module,

e.g.

import math as mh

and then use 'mh.log' rather than just 'log'

Leave a comment

(use markdown syntax if you like)