Hispanopedia Wiki
Articulo de referencia

Encuentra el primer conjunto

En software y hardware informático, encontrar el primer conjunto ( ffs ) o encontrar el primer uno es una operación de bits que devuelve el índice o la posición del bit menos si...

Hispanopedia WikiContenido en espanolLectura gratuita

En software y hardware informático, encontrar el primer conjunto ( ffs ) o encontrar el primer uno es una operación de bits que devuelve el índice o la posición del bit menos significativo establecido a uno en la palabra contando desde la posición del bit menos significativo. Una operación casi equivalente es contar los ceros finales ( ctz ) o número de ceros finales ( ntz ), que cuenta el número de bits cero que siguen al bit uno menos significativo. La operación complementaria que encuentra el índice o la posición del bit establecido más significativo es el logaritmo en base 2 , llamado así porque calcula el logaritmo binario ⌊log 2 (x)⌋ . [ 1 ] Esto está estrechamente relacionado con contar los ceros iniciales ( clz ) o número de ceros iniciales ( nlz ), que cuenta el número de bits cero que preceden al bit uno más significativo. [ nb 1 ] Hay dos variantes comunes de find first set, 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 modernas de conjuntos de instrucciones de CPU proporcionan uno o más de estos operadores de hardware; para aquellos que no están disponibles, generalmente se proporciona una emulación por software, ya sea como funciones intrínsecas del compilador o en bibliotecas del sistema .

Ejemplos

Dada la siguiente palabra de 32 bits:

0000 0000 0000 0000 1000 0000 0000 1000

La operación de contar ceros finales devolvería 3, mientras que la de contar ceros iniciales devolvería 16. Esta operación depende del tamaño de la palabra: si esta palabra de 32 bits se truncara a una de 16 bits, la operación de contar ceros iniciales devolvería cero. La operación de encontrar el primer conjunto devolvería 4, lo que indica la cuarta posición desde la derecha. El logaritmo en 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 es:

1111 1111 1111 1111 0111 1111 1111 0111

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 (ningún bit está activado), tanto `count lead-zeros` como `count trailing zeros` devuelven el número de bits de la palabra, mientras que `ffs` devuelve cero. Las implementaciones de `find first set` basadas en logaritmo en base 2 y en base cero generalmente devuelven un resultado indefinido para la palabra cero.

Soporte de hardware

Muchas arquitecturas incluyen instrucciones para realizar rápidamente la búsqueda del primer conjunto y/o operaciones 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 términos de ella (véase Propiedades y relaciones ).

En algunas plataformas Alpha, CTLZ y CTTZ se emulan mediante software.

Soporte para herramientas y bibliotecas

Varios proveedores de compiladores y bibliotecas ofrecen funciones intrínsecas de compilador o funciones de biblioteca para realizar operaciones de búsqueda del primer conjunto y/o relacionadas, que con frecuencia se implementan en términos de las instrucciones de hardware mencionadas anteriormente:

Propiedades y relaciones

Si los bits se etiquetan comenzando en 1 (que es la convención utilizada en este artículo), entonces las operaciones de contar ceros finales y encontrar el primer conjunto están relacionadas por ctz( x ) = ffs( x ) − 1 (excepto cuando la entrada es cero). Si los bits se etiquetan comenzando en 0 , entonces las operaciones de contar ceros finales y encontrar el primer conjunto son exactamente equivalentes. Dado w bits por palabra, el log 2 se calcula fácilmente a partir del clz y viceversa mediante log 2 ( x ) = w − 1 − clz( x ) .

Como se muestra en el ejemplo anterior, las operaciones de encontrar el primer cero, contar los unos iniciales y contar los unos finales se pueden implementar negando la entrada y utilizando las operaciones de encontrar 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:

ctz( x ) = log 2 ( x & −x )

donde & denota la operación AND bit a bit y −x denota el complemento a dos de x . La expresión x & −x borra todos los bits excepto el bit 1 menos significativo , de modo que el bit 1 más significativo y el menos significativo son iguales.

En plataformas con una operación eficiente de conteo de ceros iniciales, como ARM y PowerPC, el ffs se puede calcular mediante:

ffs( x ) = w − clz( x & −x ) .

Por el contrario, en máquinas sin operadores log 2 o clz , clz se puede calcular usando ctz , aunque de forma ineficiente:

clz = w − ctz(2 ⌈log 2 ( x )⌉ ) (que depende de que ctz devuelva w para la entrada cero)

En plataformas con una operación eficiente de peso de Hamming (conteo de población) como SPARC POPC[ 42 ] [ 43 ] o BlackfinONES [ 44 ] hay:

ctz( x ) = popcount(( x & −x ) − 1) , [ 45 ] [ 46 ] o ctz( x ) = popcount(~( x | −x )) ,
ffs( x ) = popcount( x ^ ~− x ) [ 42 ]
clz = 32 − popcount(2 ⌈log 2 ( x )⌉ − 1)

donde ^ denota OR exclusivo a nivel de bits, | denota OR a nivel de bits y ~ denota negación a nivel de bits.

El problema inverso (dado i , producir un 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 pueden extenderse a matrices de bits arbitrariamente grandes de forma sencilla comenzando por un extremo y continuando hasta encontrar una palabra que no sea completamente cero (para ffs , ctz , clz ) o completamente uno (para ffz , clo , cto ). Una estructura de datos de árbol que utiliza recursivamente mapas de bits para rastrear qué palabras no son cero puede acelerar este proceso.

Emulación de software

La mayoría de las CPU desde finales de la década de 1980 en adelante cuentan con 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 desplazamientos, aritmética de enteros y operadores bit a bit. Existen varios enfoques que dependen de la arquitectura de la CPU y, en menor medida, de la semántica del lenguaje de programación y la calidad de la generación de código del compilador. Estos enfoques pueden describirse, a grandes rasgos, como búsqueda lineal , búsqueda binaria , búsqueda + consulta de tabla , multiplicación de De Bruijn , conversión de punto flotante/extracción de exponente y métodos de operadores de bits (sin bifurcaciones). 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 para una entrada de todos los bits a cero suele ser 0 para ffs, y la longitud en bits del operando para las demás operaciones.

Si se dispone de un operador de hardware clz o equivalente, ctz se puede calcular de forma eficiente con operaciones de bits, pero lo contrario no es cierto: no es eficiente calcular clz en ausencia de un operador de hardware.

2 n

La función 2 ⌈log 2 (x)⌉ (redondeo a la potencia de dos más cercana) usando desplazamientos y OR bit a bit [ 47 ] no es eficiente de calcular como en este ejemplo de 32 bits y aún más ineficiente si tenemos un operando de 64 bits o 128 bits:

función pow2(x): si x = 0, devolver inválido // inválido está definido por la implementación (no está en [0,63]) x ← x - 1 para cada y en {1, 2, 4, 8, 16}: x ← x | (x >> y) devolver x + 1

FFS

Dado que ffs = ctz + 1 (POSIX) o ffs = ctz (otras implementaciones), se pueden utilizar 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 entradas de todos los bits cero.

CTZ

El algoritmo canónico es un bucle que cuenta ceros comenzando en el bit menos significativo (LSB) hasta que se encuentra un bit 1:

función ctz1 (x) si x = 0 devolver w t ← 1 r ← 0 mientras (x & t) = 0 t ← t << 1 r ← r + 1 devolver r

Este algoritmo se ejecuta en tiempo y operaciones O ( w ), y resulta poco práctico en la práctica debido a la gran cantidad de bifurcaciones condicionales.

Una excepción se da cuando las entradas están distribuidas uniformemente. En ese caso, podemos confiar en que la mitad de los valores de retorno serán 0, una cuarta parte será 1, y así sucesivamente. El número promedio de iteraciones del bucle por llamada a la función es 1, y el algoritmo se ejecuta en un tiempo promedio de O (1).

Una tabla de búsqueda puede eliminar la mayoría de las ramificaciones:

tabla[1..2 n -1] = ctz(i) para i en 1..2 n -1 función ctz2 (x) si x = 0 retornar w r ← 0 mientras (x & (2 n −1)) ≠ 0 x ← x >> n r ← r + n devolver r + tabla[x & (2 n −1)]

El parámetro n es fijo (normalmente 8) y representa una compensación entre tiempo y espacio . El bucle también puede desplegarse por completo . Sin embargo, como búsqueda lineal, este enfoque sigue siendo O(n) en función del número de bits del operando.

Si se elige n = 4, la tabla de 16 entradas de 2 bits se puede codificar en una única constante de 32 bits utilizando técnicas SIMD dentro de un registro :

// binario 00 01 00 10 00 01 00 11 00 01 00 10 00 01 00 xx tabla ← 0x12131210 función ctz2a (x) si x = 0 devolver w r ← 0 mientras (x & 15) = 0 x ← x >> 4 r ← r + 4 devolver r + ((tabla >> 2*(x & 15)) & 3);

Esta técnica es bastante práctica en aplicaciones como el algoritmo MCD binario , donde los valores de x están distribuidos uniformemente, por lo que el bucle iterativo no es necesario en 15/16 de las ocasiones y sufre una penalización mínima por predicción errónea de bifurcación .

Una implementación de búsqueda binaria requiere un número logarítmico de operaciones y bifurcaciones, como en esta versión de 32 bits: [ 48 ] [ 49 ]

función ctz3 (x) si x = 0 devuelve 32 n ← 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 // Equivalentemente, n ← n + 1 - (x & 1) return n

Este algoritmo también puede ser asistido por una tabla, reemplazando las últimas 2 o 3 declaraciones if con una tabla de búsqueda de 16 o 256 entradas utilizando los bits menos significativos como xíndice.

Como se menciona en el apartado §  Propiedades y relaciones , si el hardware dispone de un operador clz, el enfoque más eficiente para calcular ctz es el siguiente:

función ctz4 (x) si x = 0 retornar w // Aísla el bit menos significativo x ← x y −x devolver w − 1 − clz(x)

Una técnica similar puede aprovechar una instrucción de conteo de población :

función ctz4a (x) si x = 0 devuelve w // Crea una máscara de los bits menos significativos x ← x ^ (x − 1) devolver popcount(x) − 1

Un algoritmo para ctz de 32 bits utiliza una secuencia de De Bruijn para construir una función hash perfecta mínima que elimina todas las ramas. [ 50 ] [ 51 ] Este algoritmo supone que el resultado de la multiplicación se trunca a 32 bits.

para i de 0 a 31: tabla[ 0x077CB531 << i >> 27 & 31 ] ← i // tabla [0..31] función ctz5 inicializada (x) si x = 0 devolver 32 devolver tabla[((x & −x) * 0x077CB531) >> 27 & 31]

La expresión (x & −x)aísla nuevamente el bit menos significativo (1). Por lo tanto, solo hay 32 palabras posibles, que la multiplicación sin signo y el desplazamiento hash colocan en la posición correcta en la tabla. Este algoritmo no tiene bifurcaciones si no necesita manejar la entrada cero.

La técnica se puede extender a palabras de 64 bits. [ 52 ]

Una variante menor utiliza la expresión (x & (x−1))para calcular una máscara de n unos finales, como en el método popcount , y un multiplicador hash perfecto mínimo diferente. [ 52 ] Esto permite que la tabla de búsqueda se comparta con una implementación de conteo de ceros iniciales .

Esto también permite una implementación plegada mediante una multiplicación de ancho medio. [ 53 ] Después de calcular la máscara, la operación XOR bit a bit de las mitades superior e inferior es suficiente para identificar de forma única la máscara original. Un multiplicador adecuado produce un hash perfecto mínimo que puede decodificarse mediante una tabla de búsqueda:

para i de 0 a 31: tabla[ ((0xffff0000 >> i) * 0x70a7) >> 11 & 31 ] ← 31 - i // tabla [0..31] inicializada función ctz5 (x) si x = 0 retornar 32 x ← x ^ (x - 1) x ← x ^ (x >> 16) return table[(x * 0x70a7) >> 11 & 31] // 0x70d3 también funciona

Esto es ventajoso si la multiplicación más estrecha ahorra más tiempo del que añade el paso de plegado. La técnica también se puede extender a palabras de 64 bits, utilizando los multiplicadores de 32 bits 0x783a9b23, 0x78291d9b, 0x782c8d4f, o 0x78291acf. [ 53 ]

CLZ

El algoritmo canónico examina un bit a la vez, comenzando por el bit más significativo (MSB), hasta encontrar un bit distinto de cero, como se muestra en este ejemplo. Su ejecución tiene una complejidad temporal de O(n), donde n es la longitud en bits del operando, y no resulta práctico para uso general.

función clz1 (x) si x = 0 devolver w t ← 1 << (w - 1) r ← 0 mientras (x & t) = 0 t ← t >> 1 r ← r + 1 devolver r

Una mejora del enfoque iterativo anterior examina ocho bits a la vez y luego utiliza una tabla de búsqueda de 256 (2⁸ ) entradas para el primer byte distinto de cero. Sin embargo, este enfoque sigue teniendo un tiempo de ejecución de O(n).

función clz2 (x) si x = 0 devolver w t ← 0xff << (w - 8) r ← 0 mientras (x & 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 n ← 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 Retornar n

Los métodos portátiles más rápidos para simular clz combinan la búsqueda binaria y la consulta de tablas: una consulta de tabla de 8 bits (2⁸ = 256 entradas de 1 byte) puede reemplazar las tres ramas inferiores de la búsqueda binaria. Los operandos de 64 bits requieren una rama adicional. Se puede usar una consulta de mayor tamaño, 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. El ahorro de una rama se ve más que compensado por la latencia de un fallo 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 a nivel de bits: [ 54 ]

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 tuberías profundas, como Prescott y los procesadores Intel posteriores, puede ser más rápido reemplazar las bifurcaciones por operadores AND y OR a nivel de bits (aunque se requieran muchas más instrucciones) para evitar el vaciado de la tubería por bifurcaciones mal predichas (y este tipo de bifurcaciones 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); devolver r;

En plataformas que ofrecen conversión por hardware de enteros a coma flotante, el campo del exponente se puede extraer y restar de una constante para calcular el número de ceros iniciales. Se requieren correcciones para compensar los errores de redondeo. [ 48 ] [ 55 ] La conversión a coma flotante puede presentar una latencia considerable. Este método es altamente poco portable y no suele recomendarse.

int x ; int r ; unión { int unsigned u [ 2 ]; double 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

Aplicaciones

La operación de conteo de ceros iniciales (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 conversiones de enteros a punto flotante en software y otras aplicaciones. [ 48 ] [ 56 ]

El conteo de ceros iniciales (clz) se puede usar para calcular el predicado de 32 bits "x = y" (cero si es verdadero, uno si es falso) mediante la identidad clz(x − y) >> 5 , donde ">>" es un desplazamiento a la derecha sin signo. [ 57 ] Se puede usar para realizar operaciones de bits más sofisticadas, como encontrar la primera cadena de n 1 bits. [ 58 ] La expresión 1 << (16 − clz(x − 1)/2) es una estimación inicial efectiva para calcular la raíz cuadrada de un entero de 32 bits usando el método de Newton . [ 59 ] CLZ puede implementar eficientemente la supresión de nulos , una técnica rápida de compresión de datos que codifica un entero como el número de bytes cero iniciales junto con los bytes distintos de cero. [ 60 ] También puede generar eficientemente enteros con distribución exponencial tomando el clz de enteros aleatorios uniformes . [ 48 ]    

El logaritmo en base 2 se puede utilizar para anticipar si una multiplicación producirá un desbordamiento, ya que ⌈log 2 (xy)⌉ ≤ ⌈log 2 (x)⌉ + ⌈log 2 (y)⌉ . [ 61 ]

El conteo de ceros iniciales y el conteo de ceros finales se pueden usar juntos para implementar el algoritmo de detección de bucles de Gosper , [ 62 ] que puede encontrar el período de una función de rango finito usando recursos limitados. [ 49 ]

El algoritmo binario MCD consume muchos ciclos eliminando los ceros finales; esto puede reemplazarse por un conteo de ceros finales (ctz) seguido de un desplazamiento. Un bucle similar aparece en los cálculos de la secuencia de granizo .

Se puede usar una matriz de bits para implementar una cola de prioridad . En este contexto, la función `find first set` (ffs) es útil para implementar de manera eficiente la operación de "extraer" o "extraer el elemento de mayor prioridad". El planificador en tiempo real del kernel de Linuxsched_find_first_bit() la utiliza internamente para este propósito. [ 63 ]

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 disco ctz( k ) se mueve la distancia mínima posible hacia la derecha (volviendo a 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 . [ 49 ]

Véase también

Notas

  1. ↑ Estas cuatro operaciones también tienen versiones negadas (mucho menos comunes):
    • encontrar el primer cero ( ffz ), que identifica el índice del bit cero menos significativo;
    • cuenta los unos finales , que cuenta el número de bits unos que siguen al bit cero menos significativo.
    • cuenta los unos iniciales , que cuenta el número de bits unos que preceden al bit cero más significativo;
    • encuentra el índice del bit cero más significativo, que es una versión invertida del logaritmo binario .
  2. El uso de operaciones de bits en palabras que no sean palabras de máquina sin signo puede producir resultados indefinidos.
Error de cita: No se utiliza en el contenido una referencia definida en una lista llamada "NB1" (consulte la página de ayuda ).

Referencias

  1. ↑ Anderson . Encuentra el logaritmo en base 2 de un entero con el bit más significativo N establecido en O(N) operaciones (la forma obvia) .
  2. 1 2 "FFS(3)" . Manual del programador de Linux . Archivos del kernel de Linux . Consultado el 2 de enero de 2012 .
  3. ↑ "Referencia de instrucciones ARM > Instrucciones generales de procesamiento de datos ARM > CLZ" . Guía del ensamblador de ARM Developer Suite . ARM . Consultado el 3 de enero de 2012 .
  4. ↑ "Documento de arquitectura AVR32" (PDF) (ED . CORP072610). Atmel Corporation . 2011. 32000D–04/201. Archivado del original (PDF) el 25/10/2017 . Consultado el 22/10/2016 . 
  5. 1 2 Manual de referencia de la arquitectura Alpha (PDF) . Compaq . 2002. págs. 4-32 , 4-34 . 
  6. 1 2 Manual del desarrollador de software para arquitecturas Intel 64 e IA-32 . Vol. 2A. Intel . págs. 3 - 92–3 - 97.  Número de pedido 325383.
  7. ↑ Manual del programador de la arquitectura AMD64, volumen 3: instrucciones generales y del sistema (PDF) . Vol. 3. Advanced Micro Devices (AMD). 2011. págs. 204–205 . Publicación n.° 24594.  
  8. ↑ "Manual del programador de la arquitectura AMD64, volumen 3: instrucciones de propósito general y del sistema" (PDF) . Tecnología AMD64 ( edición versión 3.28). Advanced Micro Devices (AMD). Septiembre de 2019 [2013]. Publicación n.° 24594. Archivado (PDF) del original el 30 de septiembre de 2019. Consultado el 2 de enero de 2014 . 
  9. ↑ Manual del desarrollador de software de la arquitectura Intel Itanium. Volumen 3: Conjunto de instrucciones Intel Itanium . Vol. 3. Intel . 2010. págs. 3:38. Archivado del original el 26 de junio de 2019.  
  10. 1 2 Arquitectura MIPS para programadores. Volumen II-A: El conjunto de instrucciones MIPS32 ( edición de revisión 3.02). Tecnologías MIPS . 2011. págs. 101–102 . Archivado del original el 7 de noviembre de 2017. Recuperado el 4 de enero de 2012 .  
  11. 1 2 Arquitectura MIPS para programadores. Volumen II-A: El conjunto de instrucciones MIPS64 (edición de revisión 3.02 ). Tecnologías MIPS . 2011. págs. 105, 107, 122, 123. Archivado del original el 7 de noviembre de 2017. Recuperado el 4 de enero de 2012 .  
  12. ↑ Manual de referencia del programador de la familia M68000 (incluye instrucciones para la CPU32) (PDF) (1.ª ed., revisión ). Motorola . 1992. págs. 4-43–4-45 . M68000PRM/AD. Archivado del original (PDF) el 8 de diciembre de 2019.  
  13. ↑ Frey, Brad. "Capítulo 3.3.11 Instrucciones lógicas de punto fijo". PowerPC Architecture Book (Edición versión 2.02 ). IBM . pág. 70.  
  14. ↑ "Capítulo 3.3.13 Instrucciones lógicas de punto fijo - Capítulo 3.3.13.1 Instrucciones lógicas de punto fijo de 64 bits". Power ISA Versión 3.0B . IBM . págs. 95, 98. 
  15. 1 2 Wolf, Clifford (22-03-2019). "Extensión de manipulación de bits "B" de RISC-V para RISC-V" (PDF) . Github (borrador) ( ed. v0.37) . Recuperado el 09-01-2020 . 
  16. ↑ Arquitectura Oracle SPARC 2011. Oracle . 2011.
  17. ↑ Manual de referencia de la arquitectura VAX (PDF) . Digital Equipment Corporation (DEC). 1987. págs. 70–71 . Archivado (PDF) del original el 29/09/2019 . Consultado el 09/01/2020 . 
  18. 1 2 3 "Capítulo 22. Instrucciones de enteros vectoriales". Principios de funcionamiento de la arquitectura IBM z (PDF) (Undécima edición). IBM . Marzo de 2015. págs. 7 - 219–22 - 10. SA22-7832-10. Archivado del original (PDF) el 9 de enero de 2020. Consultado el 10 de enero de 2020 .  
  19. ^ Meneide, JeanHeyd; Wiedijk, Freek (22 de febrero de 2024). Tecnología de la información - Lenguajes de programación - C, borrador de trabajo N3220 (PDF) . ISO/CEI. págs . 305–308 . Consultado el 7 de agosto de 2025 . 
  20. ↑ "Encabezado de la biblioteca estándar <stdbit.h> (C23)" . cppreference.com . Consultado el 7 de agosto de 2025 .
  21. ↑ Smith, Richard (1 de abril de 2020). Borrador de trabajo N4861, estándar para el lenguaje de programación C++ (PDF) . ISO/IEC. págs. 1150–1153 . Recuperado el 25 de mayo de 2020 . 
  22. ↑ "Encabezado de biblioteca estándar <bit>" . cppreference.com . Consultado el 25 de mayo de 2020 .
  23. 1 2 " FFS(3)" . Biblioteca para desarrolladores de Mac OS X. Apple, Inc. 1994-04-19 . Recuperado el 2012-01-04 .
  24. ↑ "FFS(3)" . Manual de funciones de la biblioteca FreeBSD . El proyecto FreeBSD . Consultado el 4 de enero de 2012 .
  25. ↑ "Otras funciones integradas proporcionadas por GCC" . Uso de la colección de compiladores GNU (GCC) . Free Software Foundation, Inc. Consultado el 14 de noviembre de 2015 .
  26. ↑ "GCC 3.4.0 ChangeLog" . GCC 3.4.0 . Free Software Foundation, Inc. Consultado el 14 de noviembre de 2015 .
  27. ↑ "Extensiones del lenguaje Clang - capítulo Funciones integradas" . El equipo de Clang . Consultado el 9 de abril de 2017. Clang admite varias funciones de biblioteca integradas con la misma sintaxis que GCC.
  28. ↑ "Código fuente de Clang" . Equipo LLVM, Universidad de Illinois en Urbana-Champaign . Consultado el 9 de abril de 2017 .
  29. ↑ "_BitScanForward, _BitScanForward64" . Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . 16 de noviembre de 2012. Consultado el 21 de mayo de 2018 .
  30. ↑ "_BitScanReverse, _BitScanReverse64" . Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . 16 de noviembre de 2012. Consultado el 21 de mayo de 2018 .
  31. ↑ "__lzcnt16, __lzcnt, __lzcnt64" . Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . Consultado el 3 de enero de 2012 .
  32. ↑ "ARM intrinsics" . Visual Studio 2012: Visual C++: Compiler Intrinsics . Microsoft . 2012-08-20 . Consultado el 2022-05-09 .
  33. ↑ "Guía de Intel Intrinsics" . Intel . Consultado el 3 de abril de 2020 .
  34. ↑ Referencia de intrínsecos del compilador Intel C++ para Linux . Intel . 2006. pág. 21. 
  35. ↑ Guía de programación de NVIDIA CUDA (PDF) (Edición versión 3.0 ). NVIDIA . 2010. pág. 92.  
  36. ↑ "'llvm.ctlz.*' Intrínseco, 'llvm.cttz.*' Intrínseco" . Manual de referencia del lenguaje LLVM . La infraestructura del compilador LLVM . Consultado el 23 de febrero de 2016 .
  37. ↑ "i32 - Rust" . doc.rust-lang.org . Consultado el 18 de noviembre de 2025 .
  38. ↑ "u32 - Rust" . doc.rust-lang.org . Consultado el 18 de noviembre de 2025 .
  39. ↑ "NonZero en std::num - Rust" . doc.rust-lang.org . Consultado el 18 de noviembre de 2025 .
  40. ↑ "Documentación - El lenguaje de programación Zig" . ziglang.org . Consultado el 18 de noviembre de 2025 .
  41. ↑ "Documentación - El lenguaje de programación Zig" . ziglang.org . Consultado el 18 de noviembre de 2025 .
  42. 1 2 SPARC International, Inc. (1992). "A.41: Conteo de población. Nota de programación". Manual de la arquitectura SPARC: versión 9 (PDF) (Edición versión 9 ). Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice Hall . pp . 205. ISBN   978-0-13-825001-0.
  43. ↑ Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2.ª ed.). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8. 0-321-84268-5.
  44. ↑ Referencia del conjunto de instrucciones de Blackfin ( edición preliminar). Analog Devices . 2001. págs. 8–24 . Número de pieza 82-000410-14.  
  45. ↑ Dietz, Henry Gordon . "Los algoritmos mágicos agregados" . Universidad de Kentucky . Archivado del original el 31 de octubre de 2019.
  46. ↑ Isenberg, Gerd (2019-11-03) [2012]. "BitScan: Índice de LS1B por Popcount" . Chess Programming Wiki (CPW) . Archivado del original el 2020-01-09 . Recuperado el 2020-01-09 .
  47. ↑ Anderson . Redondea a la siguiente potencia de 2 más alta .
  48. 1 2 3 4 Warren . Capítulo 5-3: Contando los ceros iniciales.
  49. 1 2 3 Warren . Capítulo 5-4: Contando los ceros finales.
  50. ↑ Leiserson, Charles E. ; Prokop, Harald ; Randall, Keith H. (1998-07-07). "Uso de secuencias de De Bruijn para indexar un 1 en una palabra de computadora" (PDF) . Laboratorio de Ciencias de la Computación del MIT, Cambridge, MA, EE. UU. Archivado (PDF) del original el 09-01-2020 . Recuperado el 09-01-2020 .
  51. ↑ Busch, Philip (1 de marzo de 2009) [21 de febrero de 2009]. "Cómo calcular ceros finales" (PDF) . Archivado (PDF) del original el 1 de agosto de 2016. Consultado el 9 de enero de 2020 .
  52. 1 2 Isenberg, Gerd (2019-11-03) [2012]. "BitScan: De Bruijn Multiplication" . Chess Programming Wiki (CPW) . Archivado del original el 2020-01-09 . Recuperado el 2020-01-09 .
  53. 1 2 Isenberg, Gerd (2019-11-03) [2012]. "BitScan: el truco de plegado de Matt Taylor" . Chess Programming Wiki (CPW) . Archivado del original el 2020-01-09 . Recuperado el 2026-04-17 .
  54. ↑ Anderson . Encuentra el logaritmo en base 2 de un entero de N bits en O(lg(N)) operaciones con multiplicación y búsqueda .
  55. ↑ Anderson . Encuentra el logaritmo en base 2 de un entero con un número de coma flotante IEEE de 64 bits .
  56. ↑ Sloss, Andrew N.; Symes, Dominic; Wright, Chris (2004). Guía del desarrollador de sistemas ARM: diseño y optimización de software de sistema (1.ª ed.). San Francisco, CA, EE. UU.: Morgan Kaufmann . págs. 212–213 . ISBN   978-1-55860-874-0.
  57. ↑ Warren . Capítulo 2-11: Predicados de comparación.
  58. ↑ Warren . Capítulo 6-2: Encontrar la primera cadena de 1 bit de una longitud dada.
  59. ↑ Warren . Capítulo 11-1: Raíz cuadrada entera.
  60. ↑ Schlegel, Benjamin; Gemulla, Rainer; Lehner, Wolfgang [en alemán] (junio de 2010). «Compresión rápida de enteros mediante instrucciones SIMD». Actas del Sexto Taller Internacional sobre Gestión de Datos en Nuevo Hardware . págs. 34–40 . CiteSeerX 10.1.1.230.6379 . doi : 10.1145/1869389.1869394 . ISBN   978-1-45030189-3. S2CID 7545142 . 
  61. ↑ Warren . Capítulo 2-12: Detección de desbordamiento.
  62. ↑ Gosper, Bill (abril de 1995) [1972-02-29]. Baker, Henry Givens Jr. (ed.). "Detector de bucle" . HAKMEM ( edición remecanografiada y convertida). Cambridge, Massachusetts, EE. UU.: Laboratorio de Inteligencia Artificial , Instituto Tecnológico de Massachusetts (MIT). Memorando de IA 239, artículo 132. Archivado del original el 8 de octubre de 2019. Recuperado el 9 de enero de 2020 . 
  63. ↑ Aas, Josh (17 de febrero de 2005). Comprensión del planificador de CPU de Linux 2.6.8.1 (PDF) . Silicon Graphics, Inc. (SGI). pág. 19. Archivado (PDF) del original el 19 de mayo de 2017. Recuperado el 9 de enero de 2020 . 

Lecturas adicionales

  • Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2.ª  ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
  • Anderson, Sean Eron (2005) [1997]. "Bit Twiddling Hacks" . Universidad de Stanford . Archivado del original el 8 de enero de 2020. Recuperado el 3 de enero de 2012 .(Nota: Se incluyen varias implementaciones eficientes en C de dominio público para contar ceros finales y logaritmo en base 2 ).
  • Guía de Intel Intrinsics
  • Wiki de programación de ajedrez: BitScan : Una explicación detallada de varios métodos de implementación para ffs (el índice del bit menos significativo "LS1B") y logaritmo en base 2 (el índice del bit más significativo "MS1B") de valores de 64 bits.