Take the 2-minute tour ×

Consider the equation below:

2 ** n = A

Let us assume A=64.

What is the easiest way to find the value of n?

I am currently using following two approaches

A= 64; n = 1; n+=1 while (A >> n) > 0; n-1

A= 64; n = 0; n+=1 until (A == ( 2 ** n));n

Is there a better approach?

Other way of stating the same problem:

2 = nth root A If I know the value of A, how do I determine the value of n?

share|improve this question
I did a simple benchmark on three approaches. As expected logarithmic approach is the fastest. user system total real bit-wise right shift 0.235000 0.000000 0.235000 ( 0.235000) sequential compare 1.484000 0.000000 1.484000 ( 1.500000) logarithmic 0.141000 0.000000 0.141000 ( 0.140000) –  Harish Shetty Oct 14 '09 at 1:34
I changed the logic of bit shift shift method ( i.e my first approach) and got the best performance compared to other three methods. A= 64; n = 0; n+=1 until ((A >>= 1) == 0); n; So I am going with the bit shift approach. –  Harish Shetty Oct 14 '09 at 2:01

5 Answers 5

up vote 4 down vote accepted

Neither of the above answers is better than your first approach:


Evaluating Math.log(x) takes a lot longer than doing a dozen bit-shifts, and will also give you an answer like 5.99999999999980235 to make sense of.

See this SO question for some better ideas.

share|improve this answer

The proposed answer is good, but you have to count up to your logarithm and there is a slightly more efficient way, if you know that the logarithm has an upper bound, i.e. if you know that you never deal with numbers larger than 1 << bound.

def faster_log2(n)
  l = 0; bound = 64
  while bound > 0
    if 1 << bound > n
      n >>= bound; l += bound
    bound >>= 1

If you don't have an upper bound, but you still want to use this algorithm, you can also calculate a bound before executing the algorithm, but if performance is not an issue, then I would stick with the shorter solution.

def bound(n)
  bound = 1;
  bound >>= 1 while 1 << bound < n
share|improve this answer

If you care about the problems mentioned by mobrule. How about this? It is the same as your own method but use built-in function to communicate the idea explictly.

    def exp_value a 
       (1..a).to_a.detect {|n| 2**n >=a}

    exp_value 64
    => 6
share|improve this answer
(1..a).to_a creates an Array of size a. So your algorithm has an O(n) complexity for something that could be achieved much more efficiently... –  Lykos Sep 10 '12 at 19:17
It took several seconds on my computer for numbers like 10 million, which are reasonably small to appear in real world applications. –  Lykos Sep 10 '12 at 19:40

Try this:

def exp_value(n)
  Math.log(n) / Math.log(2)
share|improve this answer
Stuff like this makes me wish that I comprehended logarithms well, know of any good/simple online references? –  Robert K Oct 14 '09 at 0:45
This is not complex mathematics - they teach this in high school: en.wikipedia.org/wiki/Logarithm –  duffymo Oct 14 '09 at 0:59
@Duffymo: fair enough but (1) complex (or not) is a relative term here and (2) not all of us paid attention during high school math classes. There's no sense in telling someone, "this is trivial," if he or she asks for references to more information. –  Telemachus Oct 14 '09 at 1:08

log2n = ln n / ln 2


log_2_64 = Math.log(64) / Math.log(2)
share|improve this answer

Your Answer


