Proposed by Bouyack on 04/25/2008

This one is deceptively simple sounding. Write an function that finds the floor of log₂ 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!

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!

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;
}

This code is listed on the Wikipedia page for the 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

/**
 * 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);
}

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

Here's the code I used for testing:

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

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.