c - bitwise - bits manipulation
Encuentra el bit más significativo(más a la izquierda) que se establece en una matriz de bits (15)
Tengo una implementación de matriz de bits donde el 0 ° índice es el MSB del primer byte en una matriz, el 8 ° índice es el MSB del segundo byte, etc.
¿Cuál es una forma rápida de encontrar el primer bit que se establece en esta matriz de bits? Todas las soluciones relacionadas que he buscado encuentran el primer bit menos significativo, pero necesito el primero más significativo. Entonces, dado 0x00A1, quiero 8 (ya que es el noveno bit de la izquierda).
¡Añadiré uno!
typedef unsigned long long u64;
typedef unsigned int u32;
typedef unsigned char u8;
u8 findMostSignificantBit (u64 u64Val)
{
u8 u8Shift;
u8 u8Bit = 0;
assert (u64Val != 0ULL);
for (u8Shift = 32 ; u8Shift != 0 ; u8Shift >>= 1)
{
u64 u64Temp = u64Val >> u8Shift;
if (u64Temp)
{
u8Bit |= u8Shift; // notice not using +=
u64Val = u64Temp;
}
}
return u8Bit;
}
Por supuesto, esto está trabajando en un número de 64 bits (sin signo de larga duración), y no en una matriz. Además, mucha gente ha señalado a funciones incorporadas de g ++ que no conocía. Que interesante.
De todos modos, esto encuentra el bit más significativo en 6 iteraciones y da una afirmación si pasó 0 a la función. No es la mejor función para usar si tiene acceso a una instrucción del chipset.
También estoy usando | = en vez de + = porque estos son siempre potencias de dos, y O es (clásicamente) más rápido que la suma. Como solo estoy agregando poderes únicos de 2 juntos, nunca me volqué.
Esta es una búsqueda binaria, lo que significa que siempre encuentra el resultado en 6 iteraciones.
Nuevamente, esto es mejor:
u8 findMostSignificantBit2 (u64 u64Val)
{
assert (u64Val != 0ULL);
return (u8) (__builtin_ctzll(u64Val));
}
Aquí hay un algoritmo de fuerza bruta simple para una matriz de bytes de tamaño arbitrario:
int msb( unsigned char x); // prototype for function that returns
// most significant bit set
unsigned char* p;
for (p = arr + num_elements; p != arr;) {
--p;
if (*p != 0) break;
}
// p is with pointing to the last byte that has a bit set, or
// it''s pointing to the first byte in the array
if (*p) {
return ((p - arr) * 8) + msb( *p);
}
// what do you want to return if no bits are set?
return -1;
Lo dejaré como un ejercicio para que el lector msb() una función apropiada de msb() así como la optimización para trabajar en grietas de datos de long long o long long .
Aquí hay un fragmento de código que explica __builtin_clz ()
////// go.c ////////
#include <stdio.h>
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) /
? (1U << POS_OF_HIGHESTBITclz(a)) /
: 0)
int main()
{
unsigned ui;
for (ui = 0U; ui < 18U; ++ui)
printf("%i /t %i/n", ui, NUM_OF_HIGHESTBITclz(ui));
return 0;
}
Busque la instrucción BSR (Bit scan reverse) x86 asm para obtener la forma más rápida de hacerlo. Desde el documento de Intel: Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand). Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand).
Como adicto al rendimiento, he intentado un montón de variaciones para el conjunto de MSB, el siguiente es el más rápido que he encontrado,
unsigned int msb32(unsigned int 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];
}
Dos mejores maneras en que sé hacer esto en C pura:
Primero busque linealmente el conjunto de bytes / palabras para encontrar el primer byte / palabra que no sea cero, luego realice una búsqueda binaria desenrollada del byte / palabra que encuentre.
if (b>=0x10)
if (b>=0x40)
if (b>=0x80) return 0;
else return 1;
else
if (b>=0x20) return 2;
else return 3;
else
if (b>=0x4)
if (b>=0x8) return 4;
else return 5;
else
if (b>=0x2) return 6;
else return 7;
3 (BTW eso es log2 (8)) saltos condicionales para obtener la respuesta. En las modernas máquinas x86, la última se optimizará para un movimiento condicional.
Alternativamente, use una tabla de búsqueda para asignar el byte al índice del primer bit que se establece.
Un tema relacionado que quizás desee buscar es funciones enteras de log2. Si mal no recuerdo, ffmpeg tiene una buena implementación.
Editar: Puedes hacer la búsqueda binaria anterior en una búsqueda binaria sin sucursales, pero no estoy seguro de si sería más eficiente en este caso ...
Hay varias formas de hacer esto, y el rendimiento relativo de las diferentes implementaciones es algo dependiente de la máquina (por casualidad, he comparado esto en cierta medida con un propósito similar). En algunas máquinas incluso hay una instrucción incorporada para esto (use una si está disponible y se puede tratar la portabilidad).
Vea algunas implementaciones here (en "base de registro entero 2"). Si está utilizando GCC, revise las funciones __builtin_clz y __builtin_clzl (que hacen esto para las __builtin_clz no __builtin_clz y las que no tienen cero, respectivamente). El "clz" significa "conteo de ceros a la izquierda", que es otra forma de describir el mismo problema.
Por supuesto, si su matriz de bits no encaja en una palabra de máquina adecuada, necesita repetir las palabras en la matriz para buscar la primera palabra distinta de cero y luego realizar este cálculo solo en esa palabra.
He trabajado con una serie de funciones para obtener el bit más significativo, pero los problemas generalmente surgen moviéndose entre números de 32 y 64 bits o moviéndose entre los cuadros x86_64 y x86. Las funciones __builtin_clz , __builtin_clzl y __builtin_clzll funcionan bien para números de 32/64 bit y en máquinas x86_64 y x86. Sin embargo, se requieren tres funciones. He encontrado un MSB simple que depende del desplazamiento a la derecha que manejará todos los casos para números positivos. Al menos para el uso que hago de él, ha tenido éxito donde otros han fallado:
int
getmsb (unsigned long long x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
Al designar la entrada como unsigned long long , puede manejar todas las clases de números, desde unsigned char hasta unsigned long long y dada la definición estándar, es compatible en las versiones x86_64 y x86. El caso para 0 se define para devolver 0 , pero se puede cambiar según sea necesario. Una prueba simple y salida son:
int
main (int argc, char *argv[]) {
unsigned char c0 = 0;
unsigned char c = 216;
unsigned short s = 1021;
unsigned int ui = 32768;
unsigned long ul = 3297381253;
unsigned long long ull = 323543844043;
int i = 32767;
printf (" %16u MSB : %d/n", c0, getmsb (c0));
printf (" %16u MSB : %d/n", c, getmsb (c));
printf (" %16u MSB : %d/n", s, getmsb (s));
printf (" %16u MSB : %d/n", i, getmsb (i));
printf (" %16u MSB : %d/n", ui, getmsb (ui));
printf (" %16lu MSB : %d/n", ul, getmsb (ul));
printf (" %16llu MSB : %d/n", ull, getmsb (ull));
return 0;
}
Salida:
0 MSB : 0
216 MSB : 7
1021 MSB : 9
32767 MSB : 14
32768 MSB : 15
3297381253 MSB : 31
323543844043 MSB : 38
NOTA: para consideraciones de velocidad, usar una sola función para lograr lo mismo centrado en __builtin_clzll es aún más rápido por un factor de aproximadamente 6.
No es el más rápido, pero funciona ...
//// C program
#include <math.h>
#define POS_OF_HIGHESTBIT(a) /* 0th position is the Least-Signif-Bit */ /
((unsigned) log2(a)) /* thus: do not use if a <= 0 */
#define NUM_OF_HIGHESTBIT(a) ((!(a)) /
? 0 /* no msb set*/ /
: (1 << POS_OF_HIGHESTBIT(a) ))
// could be changed and optimized, if it is known that the following NEVER holds: a <= 0
int main()
{
unsigned a = 5; // 0b101
unsigned b = NUM_OF_HIGHESTBIT(a); // 4 since 4 = 0b100
return 0;
}
Si está utilizando x86, puede vencer prácticamente cualquier solución de byte a byte o palabra por palabra usando las operaciones SSE2, combinadas con las instrucciones de búsqueda de primer bit, que (en el mundo gcc) se pronuncian "ffs "para el bit más bajo y" fls "para el bit más alto. Perdóneme por tener problemas (! @ # $% ^) Formateando el código "C" en una respuesta; echa un vistazo: http://mischasan.wordpress.com/2011/11/03/sse2-bit-trick-ffsfls-for-xmm-registers/
Um, tu etiqueta indica 32 bits pero parece que los valores que estás usando son de 16 bits. Si significaba 32 bits, entonces creo que la respuesta para 0x00a1 debería ser 24 y no 8.
Suponiendo que está buscando el índice de bit MSB desde el lado izquierdo y sabe que solo tratará con uint32_t, aquí está el algoritmo obvio y simple:
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t test_value = 0x00a1;
int i;
for (i=0; i<32; ++i)
{
if (test_value & (0x80000000 >> i))
{
printf("i = %d/n", i);
exit(0);
}
}
return 0;
}
tl: dr; Para 32 bits, use la multiplicación de Bruijn .
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 devuelven resultados incorrectos cuando la entrada es cero.
En x86-64, la multiplicación de Bruijn se ejecuta a una velocidad comparable a las instrucciones de hardware equivalentes (defectuosas) , con una diferencia de rendimiento de solo 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 hilo funcionan mucho peor que lo que sugieren sus autores, o no calculan el resultado correctamente, o ambas cosas. 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).
Aquí están los resultados en 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 "adicto al 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.
Estos son los resultados en modo de rendimiento, que se ejecutan en mi portátil i7-4600, compilados 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 supera ampliamente a las otras implementaciones porque no tiene sucursales y, por lo tanto, funciona bien con 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
}
GCC tiene __builtin_clz que se traduce a BSR en x86 / x64, CLZ en ARM, etc. y emula la instrucción si el hardware no la implementa.
Visual C ++ 2005 y _BitScanReverse posteriores tiene _BitScanReverse .
#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; /
/
n; /
})