====== Fast log2 of an unsigned int ======
//Proposed by Bouyack on 04/25/2008//

This one is deceptively simple sounding. Write an function that finds the floor of log<sub>2</sub> for a 32-bit unsigned integer. Make it as fast as possible. One thing: there is a solution to this problem that uses 4 Gb of RAM and may be the fastest in certain situations. That solution is retarded and doesn't count. Don't use more than a reasonable amount of memory, say, 10 Mb (though even that seems excessive for just finding log2(x)). Also, don't use assembly. Yes it will make your program run faster but then I would have to rewrite mine in assembly and I really don't want to bother with that. Anyways, it's the algorithm that's important. Good luck!

====== Discussion ======

==== Cheating ====

Here's an implementation that cheats. It's very fast and always correct... as long as you start with log(1) then log(2), log(3), all the way up to log(0xFFFFFFFF). No cheating!

<code c>
unsigned int fake_log2(unsigned int x)
{
    static unsigned int upper = 1;
    static unsigned int current = 1;
    static unsigned int next_ret = 0;
    unsigned int ret;
	
    ret = next_ret;
    current--;
    if(current == 0)
    {
        upper = upper << 1;
        current = upper;
        next_ret++;
    }
    return ret;
}
</code>

==== Benchmark code ====
This code is listed on the Wikipedia page for the [[wp>Binary_logarithm|binary logarithm]] to solve this very problem.  It generates an answer in O(1) time.  Is there an algorithm that will solve it faster?  //-Gerf//

<code c>
/**
 * Returns the floor form of binary logarithm for a 32 bit integer.
 * -1 is returned if n is 0.
 */
int floorLog2(unsigned int n) {
  int pos = 0;
  if (n >= 1<<16) { n >>= 16; pos += 16; }
  if (n >= 1<< 8) { n >>=  8; pos +=  8; }
  if (n >= 1<< 4) { n >>=  4; pos +=  4; }
  if (n >= 1<< 2) { n >>=  2; pos +=  2; }
  if (n >= 1<< 1) {           pos +=  1; }
  return ((n == 0) ? (-1) : pos);
}
</code>

==== Current Results ====

''bouyack_log2: 9 seconds''\\
''wikipedia_log2: 11 seconds''\\
''fake_log2: 5 seconds''\\

Here's the code I used for testing:

<code c>
time_t t1, t2;
volatile unsigned int unused;

t1 = time(NULL);
for(i=1;i!=0;i++)
	unused = bouyack_log2(i);
t2 = time(NULL);

printf("bouyack_log2: %d seconds\n",t2-t1);

t1 = time(NULL);
for(i=1;i!=0;i++)
	unused = wikipedia_log2(i);
t2 = time(NULL);

printf("wikipedia_log2: %d seconds\n",t2-t1);

t1 = time(NULL);
for(i=1;i!=0;i++)
	unused = fake_log2(i);
t2 = time(NULL);
	
printf("fake_log2: %d seconds\n",t2-t1);
</code>

The ''volatile unsigned int unused'' keeps the compiler from optimizing away the function calls, which it would since they don't actually do anything. Before I added this all three of them took 2 seconds.