Calculate the number of times to divide by two

Question

Greetings.

I have a java method that I consider expensive, and I'm trying to replace some calls to it with a mathematical expression. Problem is, I suck at math. I mean really suck.

The following should explain the pattern that I'm trying to exploit.

f(x)   -> y
f(x*2) -> f(x)+1

That is, whenever I double the value for x, the value for y will be 1 greater than for x/2. Here are some example output:

f(5)   -> 6
f(10)  -> 7
f(20)  -> 8
f(40)  -> 9
f(80)  -> 10
f(160) -> 11
f(320) -> 12

My current approach is brute force. I'm looping over the X and test how many times I can halve it before I reach 5, and finally I add 6. This works and is faster than the call to the original method. But I was looking for a more "elegant" or potentially cheaper solution.

Accepted answer goes to the one who manages to help me without pointing out how stupid I am :)

(the title probably sucks, because I don't know what I'm looking for)

Answer 1

Have you considered that what you are looking at is essentially to divide by five, find what power of two you have, and add 6 to that power?

The general approach to "given Y find out what power of X it is" is to use logarithms. With a calculator try dividing the log of 64 with the log of 2 and see that you get 6.

So - divide by five, take the log, divide by the log of two, and add six.

Answer 2

You are looking for a logarithm (base 2)

if the base x is 5, and the base y is 6, then log2(320 / 5) + 6 = 12

In Java, (Math.log(320 / x) / Math.log(2)) + y

Where x and y are the original values (in this example, f(5) = 6)

Answer 3

what you're looking for is the number of digits in the binary representation, which (for a base 10 number and base 10 logarithms) is given by log(x)/log(2)