tl:dr; _BitScanReverse or __builtin_clz is the fastest non-portable MSB algorithm, and de Bruijn multiplication is the fastest portable algorithm.
All the other answers in this thread either run much more poorly than their authors suggest, or don't calculate the result correctly, or both. Let's benchmark them all, and let's verify that they do what they claim to do.
Here's a simple C++11 harness to test all these implementations. It compiles clean on Visual Studio but should work on all modern compilers. It allows you to run the benchmark in performance mode (bVerifyResults = false) and in checking mode (bVerifyResults = true).
Here are the results in verification mode:
Verification failed for msbNative64: input was 0; output was 818af060; expected 0
Verification failed for msbFfs: input was 22df; output was 0; expected d
Verification failed for msbPerformanceJunkie32: input was 0; output was ffffffff; expected 0
Verification failed for msbNative32: input was 0; output was 9ab07060; expected 0
The "performance junkie" and the Microsoft native implementations do different things when the input is zero. msbPerformanceJunkie32 produces -1 and Microsoft produces a random number. Also the msbPerformanceJunkie32 implementation produces a result that is off by one from all the other answers.
Here are the results in performance mode, running on my i7-4600 laptop:
msbLoop64 took 4.59326 seconds
msbNative64 took 0.296473 seconds
msbLoop32 took 3.55306 seconds
msbFfs took 0.562097 seconds
msbPerformanceJunkie32 took 1.10708 seconds
msbDeBruijn32 took 0.263309 seconds
msbNative32 took 0.259938 seconds
The de Bruijn version likely beats the other implementations because it is branchless, and therefore it runs well against inputs that produce an evenly distributed set of outputs. All the other versions are slower against arbitrary inputs because of the penalties of branch misprediction on modern CPUs. The smbFfs function produces incorrect results so it can be ignored.
Some of the implementations work on 32 bit inputs, and some work on 64 bit inputs. A template will help us compare apples to apples, regardless of the input size.
Here's the code. Download and run the benchmarks yourself if you like.
#include <iostream>
#include <chrono>
#include <random>
#include <cassert>
#include <string>
#include <limits>
#ifdef _MSC_VER
#define MICROSOFT_COMPILER 1
#include <intrin.h>
#endif // _MSC_VER
const int iterations = 100000000;
bool bVerifyResults = false;
std::random_device rd;
std::default_random_engine re( rd() );
typedef unsigned int u32;
typedef unsigned long long u64;
class Timer
{
public:
Timer() : beg_( clock_::now() ) {}
void reset() {
beg_ = clock_::now();
}
double elapsed() const {
return std::chrono::duration_cast<second_>
( clock_::now() - beg_ ).count();
}
private:
typedef std::chrono::high_resolution_clock clock_;
typedef std::chrono::duration<double, std::ratio<1> > second_;
std::chrono::time_point<clock_> beg_;
};
unsigned int msbPerformanceJunkie32( u32 x )
{
static const unsigned int bval[] =
{ 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };
unsigned int r = 0;
if ( x & 0xFFFF0000 ) {
r += 16 / 1;
x >>= 16 / 1;
}
if ( x & 0x0000FF00 ) {
r += 16 / 2;
x >>= 16 / 2;
}
if ( x & 0x000000F0 ) {
r += 16 / 4;
x >>= 16 / 4;
}
return r + bval[x];
}
#define FFS(t) \
{ \
register int n = 0; \
if (!(0xffff & t)) \
n += 16; \
if (!((0xff << n) & t)) \
n += 8; \
if (!((0xf << n) & t)) \
n += 4; \
if (!((0x3 << n) & t)) \
n += 2; \
if (!((0x1 << n) & t)) \
n += 1; \
return n; \
}
unsigned int msbFfs32( u32 x )
{
FFS( x );
}
unsigned int msbLoop32( u32 x )
{
int r = 0;
if ( x < 1 ) return 0;
while ( x >>= 1 ) r++;
return r;
}
unsigned int msbLoop64(u64 x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
u32 msbDeBruijn32( u32 v )
{
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27];
}
#ifdef MICROSOFT_COMPILER
u32 msbNative32( u32 val )
{
unsigned long result;
_BitScanReverse( &result, val );
return result;
}
u32 msbNative64( u64 val )
{
unsigned long result;
_BitScanReverse64(&result, val);
return result;
}
#endif // MICROSOFT_COMPILER
template <typename InputType>
void test( unsigned int msbFunc( InputType ),
const std::string &name,
const std::vector< InputType > &inputs,
std::vector< unsigned int > &results,
bool bIsReference = false
)
{
Timer t;
if (bIsReference)
{
int i = 0;
for (int i = 0; i < iterations; i++)
results[ i ] = msbFunc( inputs[i] );
}
unsigned int result;
bool bNotified = false;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
if (bVerifyResults && ( result != results[i]) && !bNotified)
{
std::cout << "Verification failed for " << name << ": "
<< "input was " << std::hex << inputs[i]
<< "; output was " << result
<< "; expected " << results[i]
<< std::endl;
bNotified = true;
}
}
double elapsed = t.elapsed();
std::cout << name << " took " << elapsed << " seconds" << std::endl;
}
void main()
{
std::uniform_int_distribution <u64> dist64(0,
std::numeric_limits< u64 >::max());
std::uniform_int_distribution <u32> shift64(0, 63);
std::vector< u64 > inputs64;
for (int i = 0; i < iterations; i++)
{
inputs64.push_back(dist64(re) >> shift64(re));
}
std::vector< u32 > results64;
results64.resize(iterations);
test< u64 >( msbLoop64, "msbLoop64", inputs64, results64, true);
#ifdef MICROSOFT_COMPILER
test< u64 >( msbNative64, "msbNative64", inputs64, results64, false );
#endif // MICROSOFT_COMPILER
std::cout << std::endl;
std::uniform_int_distribution <u32> dist32(0,
std::numeric_limits< u32 >::max());
std::uniform_int_distribution <u32> shift32(0, 31);
std::vector< u32 > inputs32;
for (int i = 0; i < iterations; i++)
inputs32.push_back(dist32(re) >> shift32(re));
std::vector< u32 > results32;
results32.resize(iterations);
test< u32 >( msbLoop32, "msbLoop32", inputs32, results32, true);
test< u32 >( msbFfs32, "msbFfs", inputs32, results32, false);
test< u32 >( msbPerformanceJunkie32, "msbPerformanceJunkie32",
inputs32, results32, false);
test< u32 >( msbDeBruijn32, "msbDeBruijn32", inputs32, results32, false);
#ifdef MICROSOFT_COMPILER
test< u32 >( msbNative32, "msbNative32", inputs32, results32, false);
#endif // MICROSOFT_COMPILER
}