En software y hardware de computadora, encontrar el primer conjunto ( ffs ) o encontrar el primero es una operación de bit que, dada una palabra de máquina sin signo , [nb 1] designa el índice o posición del bit menos significativo establecido en uno en la palabra que cuenta desde la posición de bit menos significativa. Una operación casi equivalente es contar los ceros finales ( ctz ) o el 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 posición del bit conjunto más significativo es log base 2 , llamada así porque calcula el logaritmo binario ⌊log 2 (x)⌋ . [1] Esto está estrechamente relacionado con el recuento de ceros a la izquierda ( clz ) o el número de ceros a la izquierda ( nlz ), que cuenta el número de bits de cero que preceden al bit más significativo. [nb 2] Hay dos variantes comunes de buscar 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 así será llamado con ese nombre.
La mayoría de las arquitecturas modernas de conjuntos de instrucciones de CPU proporcionan uno o más de estos como operadores de hardware; La emulación de software generalmente se proporciona para aquellos que no están disponibles, ya sea como elementos intrínsecos del compilador o en bibliotecas del sistema .
Dada la siguiente palabra de 32 bits:
La operación de conteo de ceros a la izquierda devolvería 3, mientras que la operación de conteo de ceros a la izquierda devuelve 16. La operación de conteo de ceros a la izquierda depende del tamaño de la palabra: si esta palabra de 32 bits se truncara a una palabra de 16 bits, contar los ceros a la izquierda devolvería cero . La operación de búsqueda del primer conjunto devolvería 4, lo que indica la cuarta posición desde la derecha. La base del registro truncado 2 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 conteo de los siguientes devolvería 3, la operación de conteo de los primeros devolvería 16 y la operación de búsqueda del primer cero ffz devolvería 4.
Si la palabra es cero (no hay bits establecidos), contar los ceros iniciales y contar los ceros finales devuelven el número de bits de la palabra, mientras que ffs devuelve cero. Tanto las implementaciones de base logarítmica 2 como las de base cero de buscar el primer conjunto generalmente devuelven un resultado indefinido para la palabra cero.
Muchas arquitecturas incluyen instrucciones para realizar rápidamente operaciones de búsqueda del primer conjunto y/o operaciones relacionadas, que se enumeran a continuación. La operación más común es contar ceros a la izquierda (clz), probablemente porque todas las demás operaciones se pueden implementar de manera eficiente en términos de ella (consulte Propiedades y relaciones).
En algunas plataformas Alpha, CTLZ y CTTZ se emula en software.
Varios proveedores de compiladores y bibliotecas proporcionan funciones intrínsecas del compilador o funciones de biblioteca para realizar búsquedas del primer conjunto y/o operaciones relacionadas, que frecuentemente se implementan en términos de las instrucciones de hardware anteriores:
Si los bits están etiquetados comenzando en 1 (que es la convención utilizada en este artículo), entonces cuente los ceros finales y encuentre las operaciones del primer conjunto que están relacionadas por ctz( x ) = ffs( x ) − 1 (excepto cuando la entrada es cero). Si los bits están etiquetados comenzando en 0 , 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 mediante log 2 ( x ) = w − 1 − clz( x ) .
Como se demuestra en el ejemplo anterior, las operaciones de encontrar el primer cero, contar los primeros y contar los finales se pueden implementar negando la entrada y usando buscar el primer conjunto, contar los ceros iniciales y contar los ceros finales. Lo contrario 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 todo excepto el bit menos significativo , de modo que el bit más y el menos significativo son iguales.
En plataformas con una operación eficiente de recuento de ceros a la izquierda, como ARM y PowerPC, los ffs se pueden calcular mediante:
Por el contrario, en máquinas sin operadores log 2 o clz , clz se puede calcular usando ctz , aunque de manera ineficiente:
En plataformas con una operación eficiente de peso Hamming (recuento de población) como SPARC [ POPC35] [36] o BlackfinONES , [ 37 ] hay:
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 ).
Las operaciones de búsqueda del primer conjunto y relacionadas se pueden extender a matrices de bits arbitrariamente grandes de una manera sencilla comenzando en un extremo y continuando hasta una palabra que no sea completamente cero (para ffs , ctz , clz ) o no sea completamente uno (para ffz) . , clo , cto ) se encuentra. Una estructura de datos de árbol que utiliza mapas de bits de forma recursiva para rastrear qué palabras son distintas de cero puede acelerar esto.
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 operadores de desplazamientos, aritmética de enteros y bits. Existen varios enfoques dependiendo de la arquitectura de la CPU y, en menor medida, de la semántica del lenguaje de programación y la calidad de generación del código del compilador. Los enfoques pueden describirse vagamente 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 ramas). Existen compensaciones entre el tiempo de ejecución y el espacio de almacenamiento, así como entre 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 de una entrada de todos los bits cero suele ser 0 para ffs y la longitud de bits del operando para las otras operaciones.
Si uno tiene un hardware clz o equivalente, ctz se puede calcular eficientemente con operaciones de bits, pero lo contrario 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) usando 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 procesador de 64 bits. Operando de bits o de 128 bits:
función pow2(x): si x = 0 return invalid // invalid 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 sumar 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 encontrar un bit de 1:
función ctz1 (x) si x = 0 devolver w t ← 1 r ← 0 mientras (x y t) = 0 t ← t << 1 r ← r + 1 volver r
Este algoritmo ejecuta operaciones y tiempos O ( n ) y no es práctico en la práctica debido a la 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 retorno r + tabla[x & (2 n -1)] x ← x >> norte r ← r + norte
El parámetro n es fijo (normalmente 8) y representa una compensación tiempo-espacio . El bucle también se puede desenrollar por completo . Pero como búsqueda lineal, este enfoque sigue siendo O(n) en el número de bits del operando.
Una implementación de búsqueda binaria requiere 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 entrada 256 tabla de búsqueda utilizando el primer byte distinto de cero encontrado como índice.
función ctz3 (x) si x = 0 regresa 32 norte ← 0 si (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16 si (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8 si (x & 0x0000000F) = 0 : n ← n + 4, x ← x >> 4 si (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2 si (x & 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&=-x devolver 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) tabla de retorno [((x & -x) * 0x077CB531) >> 27]
La expresión (x & -x) aísla nuevamente el bit menos significativo. Entonces solo hay 32 palabras posibles, que se multiplican sin signo y se desplazan mediante hash a la posición correcta en la tabla. (Este algoritmo no maneja la entrada 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 devolver w t ← 1 << (w - 1) r ← 0 mientras (x y t) = 0 t ← t >> 1 r ← r + 1 volver r
Una mejora con respecto al método 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 todavía es O(n) en el tiempo de ejecución.
función clz2 (x) si x = 0 devolver w t ← 0xff << (w - 8) r ← 0 mientras (x y t) = 0 t ← t >> 8 r ← r + 8 devolver 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 norte ← 0 si (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16 si (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8 si (x & 0xF0000000) = 0 : n ← n + 4, x ← x << 4 si (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2 si (x & 0x80000000) = 0: n ← n + 1 devuelve n
Los enfoques portátiles más rápidos para simular clz son una combinación de búsqueda binaria y búsqueda de tabla: una búsqueda de 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 para muchos es de 32 KB. Guardar una rama está más que compensado por la latencia de una pérdida 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) tabla de retorno [((x * 0x07C4ACDD) >> 27) % 32]Para procesadores con canalizaciones profundas, como Prescott y procesadores Intel posteriores, puede ser más rápido reemplazar las ramas por operadores AND y OR bit a bit (aunque se requieren muchas más instrucciones) para evitar vaciados de canalizaciones para ramas mal predichas (y estos tipos de ramas son inherentemente impredecible):
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); devolver r;
En plataformas que proporcionan conversión de hardware de números enteros a punto flotante, el campo exponente se puede extraer y restar de una constante para calcular el recuento de ceros a la izquierda. Se necesitan correcciones para tener en cuenta los errores de redondeo. [41] [46] La conversión de punto flotante puede tener una latencia sustancial. Este método no es portátil y normalmente no se recomienda.
intx ; intr ; unión { unsigned int u [ 2 ]; doble d ; } t ; t . tu [ LE ] = 0x43300000 ; // LE es 1 para t little-endian . tú [ ! LE ] = x ; t . re- = 4503599627370496.0 ; r = ( t . u [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // CLZ La operación de conteo de ceros a la izquierda (clz) se puede utilizar para implementar eficientemente la normalización , que codifica un número 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 números enteros a coma flotante en software y otras aplicaciones. [41] [47]
El recuento 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 ">>" no está firmado Giro a la derecha. [48] Puede usarse 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 suposición inicial efectiva para calcular la raíz cuadrada de un entero de 32 bits utilizando el método de Newton . [50] CLZ puede implementar eficientemente la supresión de nulos , una técnica rápida de compresión de datos que codifica un número entero como el número de bytes cero iniciales junto con los bytes distintos de cero. [51] También puede generar eficientemente números enteros distribuidos exponencialmente tomando el clz de números enteros uniformemente aleatorios . [41]
La base logarítmica 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 a la izquierda y el conteo de ceros a la derecha se pueden usar 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 usando recursos limitados. [42]
El algoritmo binario GCD pasa muchos ciclos eliminando ceros finales; esto se puede reemplazar por un recuento de ceros a la derecha (ctz) seguido de un desplazamiento. Un bucle similar aparece en los cálculos de la secuencia del granizo .
Se puede utilizar una matriz de bits para implementar una cola de prioridad . En este contexto, buscar el primer conjunto (ffs) es útil para implementar eficientemente la operación "pop" o "extraer elemento de mayor prioridad". El programador en tiempo real del kernel de Linuxsched_find_first_bit() se utiliza internamente para este propósito. [54]
La operación de conteo de 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 número de disco ctz( k ) se mueve la distancia mínima posible hacia la derecha (dando vueltas hacia la derecha). dejado 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