25 votos

Encontrar bit más significativo (a la izquierda) que se establece en una matriz de bit

Tengo un poco de la matriz de la aplicación donde el 0 índice es el MSB del primer byte de una matriz, el 8 de índice es el MSB del segundo byte, etc...

¿Cuál es una manera rápida de encontrar el primer bit que se establece en esta matriz de bit? Todas las soluciones relacionadas con la he buscado hasta encontrar el primer bit menos significativo, pero tengo el primero y más significativo. Por tanto, y dado 0x00A1, quiero 8 (ya que es el 9 de bits de la izquierda).

24voto

Andras Vass Puntos 8021

GCC ha __builtin_clz , que se traduce en BSR x86/x64, CLZ en el BRAZO, etc. y emula la instrucción si el hardware no lo implementan.
Visual C++ 2005 y hasta ha _BitScanReverse.

20voto

Sir Slick Puntos 91

Como un rendimiento adicto he intentado un montón de variaciones de MSB de conjunto, la siguiente es la más rápida 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];
}

9voto

Arkku Puntos 15523

Hay varias maneras de hacer esto, y el rendimiento relativo de las diferentes implementaciones es algo dependientes de máquina (se me ocurre para tener punto de referencia en cierta medida para un propósito similar). En algunas máquinas, incluso hay un built-en la instrucción de este (uso uno si está disponible y portabilidad puede ser tratado).

Echa un vistazo a algunas de las implementaciones de aquí (debajo de "entero de registro de la base 2"). Si usted está usando GCC, echa un vistazo a las funciones __builtin_clz y __builtin_clzl (que hacer esto para que no sea cero sin signo enteros y sin signo anhela, respectivamente). El "clz" significa "contar los ceros a la izquierda", que es otra manera de describir el mismo problema.

Por supuesto, si su matriz de bit no encaja en una palabra de máquina, usted necesita para iterar a través de las palabras en la matriz para encontrar el primer no-cero de word y, a continuación, realizar este cálculo sólo en la palabra.

3voto

ggiroux Puntos 2971

Buscar la BSR (Bits escaneo inverso) asm x86 instrucción de la manera más rápida de hacer esto. Desde Intel doc.: 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).

2voto

Martin Beckett Puntos 60406

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X