Calculate the number of times to divide by two

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)

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.

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)

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)

This is not an answer, but I couldn't make it a comment. Consider a recursive function:

int someFunc(int n, int times) {
  if(n == 0) return 0;
  if( n % 2 == 0) return someFunc(n/2, times+1);
  else return n+times;
}

Does it do what you want?

someFunc(1, 0) -> 1
someFunc(2, 0) -> 2
someFunc(3, 0) -> 3
someFunc(5, 0) -> 5
someFunc(10, 0) -> 6
...

First off, your question is not well-posed. This is an example of how a question should not be asked (no offense). I will take that your question is: given a positive integer x, find integers m, n such that x = m*2^n where m is odd, then return y = f(x) = n + g(m). Because you didn't tell how f(x) is computed for odd x, I assume g(.) is given.

If in your problem, n is not large, there is no real benefit using a more sophisticated algorithm than a simple loop (naive algorithm). I will present an algorithm that benefits the case where n is large (say a few hundreds, a few thousands). I don't know Java, so I present the algorithm in a general form (using Python-style syntax).

If you take the binary representation of x (b_{N-1} ... b_1 b_0, b_i = 0 or 1) then your problem reduces to finding the first bit 1 from the right (i.e. the least significant bit 1). Say the position of this bit is k (0<=k<=N-1) then n = k and m = x >> k. I believe the best you can do to find k is to use binary search, which results in a O(log N) algorithm. The algorithm is as follows (<< and >> are the shift operators):

Algorithm: Input: x -> Outputs: (m, n)

if x is odd or x == 0: return (x, 0)  # x is odd when x & 1 == 1 or x % 2 == 1
N = ceil(log(x, 2))  # ceil: smallest integer larger than the argument
n = 0
orig_x = x

while x & 1 == 0:   # if bit 0 is 1 (i.e. x is odd), stop the search
  half = int(N/2)
  lowerhalf = x & ((1 << half) - 1)  # obtain the lower half
  if lowerhalf == 0:   # all zeros
    n += half
    x = x >> half
    N -= half
  else:
    x = lowerhalf
    N = half

return (orig_x >> n, n)

As an example, if N = 1000 (x is 1000-bit integer), this algorithm takes at most 10 iterations (while the naive algorithm takes 1000 iterations in the worst case). However, actual execution time depends on how the bit operations and == operator are implemented for integers of 1000-bit length.

OK first off let's notice that all the inputs are multiples of 5, so we pull out a factor of 5 in the inputs; and we notice that the outputs start at 6, so we pull out a scaling by 6 in the outputs. I'll call this new function g:

g(1)      0
g(2)      1
g(4)      2
g(8)      3
g(16)     4
g(32)     5
g(64)     6

Now this function hopefully is a lot more familiar - g(x) is simple 2 to the power of x. And to do this (in Java) we can just use java.lang.Math.pow(2, x).

All that remains is to get f from g. But this is simply:

• given the input to f
• divide by 5
• use as input to g
• add 6

I'll leave that for you.

Try this:

f(x) = log<sub>2</sub>(x/5) + 6