Code:
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef unsigned char U8;
U8 log2a(U8 n)
{
static const U8 table[129] = { 0,
0, 1,
0, 2,
0, 0, 0, 3,
0, 0, 0, 0, 0, 0, 0, 4,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7 };
return table[n];
}
U8 log2b(U8 n)
{
U8 logv = 0;
while(n >>= 1) logv++;
return logv;
}
U8 log2c(U8 n)
{
if (n >= 16)
{
if (n >= 64)
{
if (n >= 128)
return 7;
return 6;
}
else
{
if (n >= 32)
return 5;
return 4;
}
}
// Less than 16.
else
{
if (n >= 4)
{
if (n >= 8)
return 3;
return 2;
}
else
{
if (n <= 1)
return 0;
return 1;
}
}
return 100;
}
const double constlog2 = log(2.0);
U8 log2d(U8 n)
{
return static_cast<int>(log(static_cast<double>(n)+0.0001) / constlog2);
}
U8 log2n(U8 n)
{
return ((n & (n-1)) == 0) * (((n-1) * 134480385) & 4581298449LL) % 15 % 9;
}
#define _FUNC(x) { x, #x, 0.0 }
#define FUNC(x) _FUNC(log2##x)
struct funcs
{
U8 (*fn)(U8 n);
char *name;
double kiterspersec;
};
funcs functab[] =
{
FUNC(a),
FUNC(b),
FUNC(c),
FUNC(d),
FUNC(n)
};
const int functabsize = sizeof(functab) / sizeof(functab[0]);
const double mintime = 3.1;
void timedLoop(funcs &f)
{
int n = 1000; // Starting value.
double t = 0;
clock_t c;
do
{
c = clock();
for(int iter = 0; iter < n; ++iter)
{
for(U8 i = 1; i; i <<= 1)
{
f.fn(i);
}
}
t = static_cast<double>(clock() - c) / CLOCKS_PER_SEC;
if (t < mintime)
{
if (t == 0)
{
n <<= 2;
}
else
{
n = static_cast<int>(mintime / t * n + 2.0);
}
}
} while(t < mintime);
f.kiterspersec = (n / (t * 1000.0)) ;
cout << f.name << " does " << f.kiterspersec << "k iterations per second"
<< endl;
}
int main()
{
// First, validate results.
int err = 0;
for(U8 i = 1; i; i <<= 1)
{
U8 r = functab[0].fn(i);
U8 p;
for(int j = 0; j < functabsize; j++)
{
p = functab[j].fn(i);
if (p != r)
{
cout << "func " << functab[j].name << " is different for "
<< static_cast<int>(i)
<< " expected " << static_cast<int>(r)
<< " got " << static_cast<int>(p) << endl;
err++;
}
}
}
if(err)
{
cout << "Error found" << endl;
// exit(1);
}
double best = 0.0;
int bestindex = 0;
for(int i = 0; i < functabsize; i++)
{
timedLoop(functab[i]);
if (functab[i].kiterspersec > best)
{
best = functab[i].kiterspersec;
bestindex = i;
}
}
cout << "Best function: " << functab[bestindex].name << " with "
<< functab[bestindex].kiterspersec
<< "k iterations per second" << endl;
return 0;
}
I tried rewriting log2b() as assembler, but it was only a tiny bit faster.