En software y hardware de computadoras, buscar el primer conjunto ( ffs ) o buscar el primero es una operación de bit que, dada una palabra de máquina sin signo , [nb 1] designa el índice o la posición del bit menos significativo establecido en uno en la palabra contando desde la posición del bit menos significativo. Una operación casi equivalente es contar ceros finales ( ctz ) o número de ceros finales ( ntz ), que cuenta el número de bits cero que siguen al bit menos significativo. La operación complementaria que encuentra el índice o la posición del bit del conjunto más significativo es log base 2 , llamada así porque calcula el logaritmo binario ⌊log 2 (x)⌋ . [1] Esto está estrechamente relacionado con contar ceros iniciales ( clz ) o número de ceros iniciales ( nlz ), que cuenta el número de bits cero que preceden al bit más significativo. [nb 2] Hay dos variantes comunes de buscar el primer conjunto, la definición POSIX que comienza la indexación de bits en 1, [2] aquí denominada ffs, y la variante que comienza la indexación de bits en cero, que es equivalente a ctz y por lo tanto se llamará con ese nombre.
La mayoría de las arquitecturas de conjuntos de instrucciones de CPU modernas proporcionan uno o más de estos como operadores de hardware; generalmente se proporciona emulación de software para cualquiera que no esté disponible, ya sea como intrínsecos del compilador o en bibliotecas del sistema .
Dada la siguiente palabra de 32 bits:
La operación de contar los ceros finales devolvería 3, mientras que la operación de contar los ceros iniciales devolvería 16. La operación de contar los ceros iniciales depende del tamaño de la palabra: si esta palabra de 32 bits se truncara a una palabra de 16 bits, contar los ceros iniciales devolvería cero. La operación de buscar el primer conjunto devolvería 4, lo que indica la cuarta posición desde la derecha. El logaritmo base 2 truncado es 15.
De manera similar, dada la siguiente palabra de 32 bits, la negación bit a bit de la palabra anterior:
La operación de contar los unos finales devolvería 3, la operación de contar los unos iniciales devolvería 16 y la operación de encontrar el primer cero ffz devolvería 4.
Si la palabra es cero (no hay bits establecidos), count los ceros iniciales y count los ceros finales devuelven la cantidad de bits de la palabra, mientras que ffs devuelve cero. Las implementaciones de find first set en base logarítmica 2 y en base cero generalmente devuelven un resultado indefinido para la palabra cero.
Muchas arquitecturas incluyen instrucciones para ejecutar rápidamente operaciones de búsqueda del primer conjunto y/o relacionadas, que se enumeran a continuación. La operación más común es contar los ceros iniciales (clz), probablemente porque todas las demás operaciones se pueden implementar de manera eficiente en función de ella (consulte Propiedades y relaciones).
En algunas plataformas Alpha, CTLZ y CTTZ se emulan en software.
Varios proveedores de compiladores y bibliotecas suministran funciones intrínsecas de compilador o funciones de biblioteca para realizar la búsqueda del primer conjunto y/o operaciones relacionadas, que frecuentemente se implementan en términos de las instrucciones de hardware anteriores:
Si los bits se etiquetan a partir de 1 (que es la convención utilizada en este artículo), entonces contar los ceros finales y encontrar el primer conjunto de operaciones están relacionadas por ctz( x ) = ffs( x ) − 1 (excepto cuando la entrada es cero). Si los bits se etiquetan a partir de 0 , entonces contar los ceros finales y encontrar el primer conjunto son operaciones exactamente equivalentes. Dados w bits por palabra, el log 2 se calcula fácilmente a partir de clz y viceversa por log 2 ( x ) = w − 1 − clz( x ) .
Como se demuestra en el ejemplo anterior, las operaciones de buscar el primer cero, contar los primeros unos y contar los últimos unos se pueden implementar negando la entrada y utilizando buscar el primer conjunto, contar los ceros iniciales y contar los ceros finales. Lo inverso también es cierto.
En plataformas con una operación log 2 eficiente como M68000, ctz se puede calcular mediante:
donde & denota AND bit a bit y −x denota el complemento a dos de x . La expresión x & −x borra todos los bits excepto el menos significativo , de modo que el bit más y el menos significativo son iguales.
En plataformas con una operación eficiente de conteo de ceros iniciales, como ARM y PowerPC, ffs se puede calcular mediante:
Por el contrario, en máquinas sin operadores log 2 o clz , clz se puede calcular utilizando ctz , aunque de manera ineficiente:
En plataformas con una operación de ponderación de Hamming (conteo de población) eficiente, como SPARC POPC[35] [ 36] o Blackfin [37] , ONEShay :
donde ^ denota OR exclusivo bit a bit, | denota OR bit a bit y ~ denota negación bit a bit.
El problema inverso (dado i , producir una x tal que ctz( x ) = i ) se puede calcular con un desplazamiento a la izquierda ( 1 << i ).
La búsqueda del primer conjunto y las operaciones relacionadas se pueden extender a matrices de bits de cualquier tamaño de una manera sencilla, comenzando por un extremo y continuando hasta que se encuentre una palabra que no sea todo cero (para ffs , ctz , clz ) o que no sea todo uno (para ffz , clo , cto ). Una estructura de datos en forma de árbol que utilice mapas de bits de forma recursiva para rastrear qué palabras no son cero puede acelerar este proceso.
La mayoría de las CPU que datan de finales de la década de 1980 en adelante tienen operadores de bits para ffs o equivalentes, pero algunas modernas, como algunas de la serie ARM-Mx, no los tienen. En lugar de operadores de hardware para ffs, clz y ctz, el software puede emularlos con turnos, aritmética de números enteros y operadores de bits. Hay varios enfoques según la arquitectura de la CPU y, en menor medida, la semántica del lenguaje de programación y la calidad de generación de código del compilador. Los enfoques pueden describirse libremente como búsqueda lineal , búsqueda binaria , búsqueda + búsqueda en tabla, multiplicación de De Bruijn, conversión de punto flotante/extracción de exponente y métodos de operador de bits (sin ramificaciones). Existen compensaciones entre el tiempo de ejecución y el espacio de almacenamiento, así como la portabilidad y la eficiencia.
Las emulaciones de software suelen ser deterministas. Devuelven un resultado definido para todos los valores de entrada; en particular, el resultado para una entrada de todos los bits cero suele ser 0 para ffs y la longitud de bits del operando para las demás operaciones.
Si uno tiene un hardware clz o equivalente, ctz se puede calcular eficientemente con operaciones de bits, pero lo inverso no es cierto: clz no es eficiente para calcular en ausencia de un operador de hardware.
La función 2 ⌈log 2 (x)⌉ (redondear a la potencia de dos más cercana) que utiliza desplazamientos y OR bit a bit [40] no es eficiente de calcular como en este ejemplo de 32 bits y es aún más ineficiente si tenemos un operando de 64 o 128 bits:
función pow2(x): si x = 0 devuelve inválido // inválido es la implementación definida (no en [0,63]) x ← x - 1 para cada y en {1, 2, 4, 8, 16}: x ← x | (x >> y) devuelve x + 1Dado que ffs = ctz + 1 (POSIX) o ffs = ctz (otras implementaciones), se pueden usar los algoritmos aplicables para ctz, con un posible paso final de agregar 1 al resultado y devolver 0 en lugar de la longitud del operando para la entrada de todos los bits cero.
El algoritmo canónico es un bucle que cuenta ceros comenzando en el LSB hasta que se encuentra un bit 1:
función ctz1(x) si x = 0 devuelve w ← 1 r ← 0 mientras (x & t) = 0 t ← t << 1 r ← r + 1 volver r
Este algoritmo ejecuta O ( n ) veces y operaciones, y es poco práctico en la práctica debido a una gran cantidad de ramas condicionales.
Una tabla de búsqueda puede eliminar la mayoría de las ramas:
tabla[0..2 n -1] = ctz(i) para i en 0..2 n -1 función ctz2 (x) si x = 0 devuelve w r ← 0 bucle si (x & (2 n -1)) ≠ 0 devuelve r + tabla[x & (2 n -1)] x ← x >> n r ← r + n
El parámetro n es fijo (normalmente 8) y representa una compensación entre tiempo y espacio . El bucle también puede desenrollarse por completo . Pero como búsqueda lineal, este enfoque sigue siendo O(n) en cuanto a la cantidad de bits en el operando.
Una implementación de búsqueda binaria toma un número logarítmico de operaciones y ramas, como en esta versión de 32 bits: [41] [42] Este algoritmo también puede ser asistido por una tabla, reemplazando las tres declaraciones "if" inferiores con una tabla de búsqueda de 256 entradas usando el primer byte distinto de cero encontrado como índice.
función ctz3(x) si x = 0 devuelve 32 n ← 0 si (x y 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16 si (x y 0x000000FF) = 0: n ← n + 8, x ← x >> 8 si (x y 0x0000000F) = 0: n ← n + 4, x ← x >> 4 si (x y 0x00000003) = 0: n ← n + 2, x ← x >> 2 si (x y 0x00000001) = 0: n ← n + 1 devuelve n
Si el hardware tiene un operador clz, el enfoque más eficiente para calcular ctz es el siguiente:
función ctz4(x) x y= -x devuelve w - (clz(x) + 1)
Un algoritmo para ctz de 32 bits utiliza secuencias de Bruijn para construir una función hash perfecta mínima que elimina todas las ramas. [43] [44] Este algoritmo supone que el resultado de la multiplicación se trunca a 32 bits.
para i de 0 a 31: tabla[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i // tabla [0..31] función inicializada ctz5 (x) devuelve tabla[((x & -x) * 0x077CB531) >> 27]
La expresión (x & -x) vuelve a aislar el bit menos significativo. Por lo tanto, solo hay 32 palabras posibles, que se multiplican sin signo y se desplazan a la posición correcta en la tabla. (Este algoritmo no maneja la entrada de cero).
El algoritmo canónico examina un bit a la vez, comenzando desde el MSB hasta que se encuentra un bit distinto de cero, como se muestra en este ejemplo. Se ejecuta en tiempo O(n), donde n es la longitud de bits del operando, y no es un algoritmo práctico para uso general.
función clz1(x) si x = 0 devuelve w t ← 1 << (w - 1) r ← 0 mientras (x & t) = 0 t ← t >> 1 r ← r + 1 volver r
Una mejora del enfoque de bucle anterior examina ocho bits a la vez y luego utiliza una tabla de búsqueda de 256 (2 8 ) entradas para el primer byte distinto de cero. Sin embargo, este enfoque sigue siendo O(n) en tiempo de ejecución.
función clz2(x) si x = 0 devuelve w t ← 0xff << (w - 8) r ← 0 mientras (x & t) = 0 t ← t >> 8 r ← r + 8 devuelve r + tabla[x >> (w - 8 - r)]
La búsqueda binaria puede reducir el tiempo de ejecución a O(log 2 n):
función clz3(x) si x = 0 devuelve 32 n ← 0 si (x y 0xFFFF0000) = 0: n ← n + 16, x ← x << 16 si (x y 0xFF000000) = 0: n ← n + 8, x ← x << 8 si (x y 0xF0000000) = 0: n ← n + 4, x ← x << 4 si (x y 0xC0000000) = 0: n ← n + 2, x ← x << 2 si (x y 0x80000000) = 0: n ← n + 1 devuelve n
Los métodos portátiles más rápidos para simular clz son una combinación de búsqueda binaria y búsqueda en tabla: una búsqueda en tabla de 8 bits (2 8 = 256 entradas de 1 byte) puede reemplazar las 3 ramas inferiores en la búsqueda binaria. Los operandos de 64 bits requieren una rama adicional. Se puede utilizar una búsqueda de mayor ancho, pero el tamaño máximo práctico de la tabla está limitado por el tamaño de la caché de datos L1 en los procesadores modernos, que es de 32 KB para muchos. Guardar una rama se ve más que compensado por la latencia de una falla de caché L1 .
Un algoritmo similar a la multiplicación de De Bruijn para CTZ funciona para CLZ, pero en lugar de aislar el bit más significativo, redondea al entero más cercano de la forma 2 n −1 usando desplazamientos y OR bit a bit: [45]
tabla[0..31] = {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}función clz4(x) para cada y en {1, 2, 4, 8, 16}: x ← x | (x >> y) devolver tabla[((x * 0x07C4ACDD) >> 27) % 32]Para procesadores con pipelines profundos, como Prescott y procesadores Intel posteriores, puede ser más rápido reemplazar ramas por operadores AND y OR bit a bit (aunque se requieren muchas más instrucciones) para evitar vaciados de pipelines por ramas mal predichas (y estos tipos de ramas son inherentemente impredecibles):
función clz5(x) r = (x > 0xFFFF) << 4; x >>= r; q = (x > 0xFF ) << 3; x >>= q; r |= q; q = (x > 0xF ) << 2; x >>= q; r |= q; q = (x > 0x3 ) << 1; x >>= q; r |= q; r |= (x >> 1); devuelve r;
En las plataformas que ofrecen conversión de hardware de números enteros a coma flotante, el campo exponencial se puede extraer y restar de una constante para calcular el recuento de ceros iniciales. Se necesitan correcciones para tener en cuenta los errores de redondeo. [41] [46] La conversión de coma flotante puede tener una latencia considerable. Este método es altamente no portable y no suele recomendarse.
int x ; int r ; unión { unsigned int u [ 2 ]; doble d ; } t ; t . u [ LE ] = 0x43300000 ; // LE es 1 para little-endian t . u [ ! LE ] = x ; t . d -= 4503599627370496.0 ; r = ( t . u [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // CLZ La operación de contar ceros a la izquierda (clz) se puede utilizar para implementar de manera eficiente la normalización , que codifica un entero como m × 2 e , donde m tiene su bit más significativo en una posición conocida (como la posición más alta). Esto a su vez se puede utilizar para implementar la división de Newton-Raphson , realizar la conversión de enteros a coma flotante en software y otras aplicaciones. [41] [47]
El conteo de ceros a la izquierda (clz) se puede utilizar para calcular el predicado de 32 bits "x = y" (cero si es verdadero, uno si es falso) a través de la identidad clz(x − y) >> 5 , donde ">>" es un desplazamiento a la derecha sin signo. [48] Se puede utilizar para realizar operaciones de bits más sofisticadas, como encontrar la primera cadena de n 1 bits. [49] La expresión clz(x − y)1 << (16 − clz(x − 1)/2) es una estimación inicial eficaz para calcular la raíz cuadrada de un entero de 32 bits utilizando el método de Newton . [50] CLZ puede implementar de manera eficiente la supresión de nulos , una técnica de compresión de datos rápida que codifica un entero como el número de bytes de cero a la izquierda junto con los bytes distintos de cero. [51] También puede generar de manera eficiente números enteros distribuidos exponencialmente tomando el clz de números enteros uniformemente aleatorios . [41]
El logaritmo en base 2 se puede utilizar para anticipar si una multiplicación se desbordará, ya que ⌈log 2 (xy)⌉ ≤ ⌈log 2 (x)⌉ + ⌈log 2 (y)⌉ . [52]
El conteo de ceros iniciales y el conteo de ceros finales se pueden utilizar juntos para implementar el algoritmo de detección de bucles de Gosper, [53] que puede encontrar el período de una función de rango finito utilizando recursos limitados. [42]
El algoritmo binario MCD emplea muchos ciclos en eliminar los ceros finales; esto se puede reemplazar por un recuento de ceros finales (ctz) seguido de un desplazamiento. Un bucle similar aparece en los cálculos de la secuencia de granizo .
Se puede utilizar una matriz de bits para implementar una cola de prioridad . En este contexto, la función de búsqueda del primer conjunto (ffs) resulta útil para implementar de manera eficiente la operación "extraer" o "extraer el elemento de mayor prioridad". El planificador en tiempo real del núcleo de Linuxsched_find_first_bit() utiliza internamente esta función. [54]
La operación de contar los ceros finales proporciona una solución óptima simple al problema de la Torre de Hanoi : los discos se numeran desde cero y, en el movimiento k , el disco número ctz( k ) se mueve la distancia mínima posible hacia la derecha (dando la vuelta hacia la izquierda según sea necesario). También puede generar un código Gray tomando una palabra arbitraria y cambiando el bit ctz( k ) en el paso k . [42]
Clang admite varias funciones de biblioteca integradas con la misma sintaxis que GCC.