tl: dr; Para 32 bits, use de Bruijn multiplication.
Es el algoritmo portátil "fastest". Es sustancialmente más rápido y más correcto que todos los otros algoritmos portátiles de MSB de 32 bits en este hilo.
El algoritmo de Bruijn también devuelve un resultado correcto cuando la entrada es cero.Las instrucciones __builtin_clz y _BitScanReverse return incorrect results cuando la entrada es cero.
en x86-64, de Bruijn multiplicación funciona a una velocidad comparable a las instrucciones de hardware (equivalentes defectuosos), con una diferencia de rendimiento de sólo alrededor del 3%.
Aquí está el código.
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];
}
Todas las otras respuestas en este tema, ya sea funcionan mucho peor que sus autores sugieren, o no calculan el resultado correctamente, o ambos. Analicemos todos y verifiquemos que hagan lo que dicen hacer.
Aquí hay un arnés C++ 11 simple para probar todas estas implementaciones. Compila limpio en Visual Studio pero debería funcionar en todos los compiladores modernos. Le permite ejecutar el punto de referencia en el modo de rendimiento (bVerifyResults = false) y en el modo de comprobación (bVerifyResults = true).
Éstos son los resultados en el modo de verificación:
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
El "drogadicto de rendimiento" y las implementaciones nativas de Microsoft hacen cosas diferentes cuando la entrada es cero. msbPerformanceJunkie32 produce -1, y _BitScanReverse de Microsoft produce un número aleatorio, consistente con la instrucción de hardware subyacente. Además, la implementación msbPerformanceJunkie32 produce un resultado que está desactivado por una de todas las otras respuestas.
Éstos son los resultados en el modo de ejecución, que se ejecuta en mi ordenador portátil i7-4600, compilado en modo de lanzamiento:
msbLoop64 took 2.56751 seconds
msbNative64 took 0.222197 seconds
msbLoop32 took 1.43456 seconds
msbFfs took 0.525097 seconds
msbPerformanceJunkie32 took 1.07939 seconds
msbDeBruijn32 took 0.224947 seconds
msbNative32 took 0.218275 seconds
La versión de Bruijn es mejor que la de otras implementaciones profundamente porque es sin sucursales, y por lo tanto funciona bien contra las entradas que producen un conjunto de salidas uniformemente distribuidas. Todas las demás versiones son más lentas frente a las entradas arbitrarias debido a las penalizaciones de errores de predicción en las CPU modernas. La función smbFfs produce resultados incorrectos, por lo que puede ignorarse.
Algunas de las implementaciones funcionan en entradas de 32 bits, y algunas funcionan en entradas de 64 bits. Una plantilla nos ayudará a comparar manzanas con manzanas, independientemente del tamaño de la entrada.
Aquí está el código. Descargue y ejecute los puntos de referencia usted mismo si lo desea.
#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
)
{
if (bIsReference)
{
int i = 0;
for (int i = 0; i < iterations; i++)
results[i] = msbFunc(inputs[i]);
}
InputType result;
if (bVerifyResults)
{
bool bNotified = false;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
if ((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;
}
}
}
else
{
Timer t;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
}
double elapsed = t.elapsed();
if (!bIsReference)
std::cout << name << " took " << elapsed << " seconds" << std::endl;
if (result == -1.0f)
std::cout << "this comparison only exists to keep the compiler from " <<
"optimizing out the benchmark; this branch will never be called";
}
}
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);
test<u64>(msbLoop64, "msbLoop64", inputs64, results64, false);
#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>(msbLoop32, "msbLoop32", inputs32, results32, false);
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
}
No es el bit 7 del bit más significativo establecido en 0x00a1 (suponiendo que el bit menos significativo es el bit 0)? –
¿Su matriz de bits tiene una longitud arbitraria, o cabe en una palabra de máquina? –
Estaba contando desde la izquierda. En binario obtengo "0000 | 0000 | 1010 | 0001", así que ese es el noveno bit, con el índice 8. Me equivoqué, debería ser 8, no 9. – Claudiu