stringtranslate.com

Encuentra el primer conjunto

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 .

Ejemplos

Dada la siguiente palabra de 32 bits:

0000 0000 0000 0000 1000 0000 0000 1000

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:

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 (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.

Soporte de hardware

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.

Soporte de herramientas y bibliotecas

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:

Propiedades y relaciones

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:

ctz( x ) = logaritmo 2 ( x y −x )

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:

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

Por el contrario, en máquinas sin operadores log 2 o clz , clz se puede calcular utilizando ctz , aunque de manera 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 de ponderación de Hamming (conteo de población) eficiente, como SPARC POPC[35] [ 36] o Blackfin [37] , ONEShay :

ctz( x ) = recuento de población(( x & −x ) − 1) , [38] [39] o ctz( x ) = recuento de población(~( x | −x )) ,
ffs( x ) = recuento de población( x ^ ~− x ) [35]
clz = 32 − recuento de población(2 ⌈log 2 ( x )⌉ − 1)

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.

Emulación de software

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.

2norte

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 + 1

Por favor

Dado 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.

ZTC

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).

CLZ

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               

Aplicaciones

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]

Véase también

Notas

  1. ^ El uso de operaciones de bits en palabras de máquina que no sean sin signo puede producir resultados indefinidos.
  2. ^ Estas cuatro operaciones también tienen versiones negadas (mucho menos comunes):
    • encuentra el primer cero ( ffz ), que identifica el índice del bit cero menos significativo;
    • contar los unos finales , que cuenta la cantidad de bits uno que siguen al bit cero menos significativo.
    • contar los primeros , que cuenta el número de bits uno 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 .

Referencias

  1. ^ Anderson. Halla el logaritmo en base 2 de un entero con el MSB N establecido en O(N) operaciones (la forma obvia).
  2. ^ ab "FFS(3)". Manual del programador de Linux . Archivos del núcleo 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) (CORP072610 ed.). Atmel Corporation . 2011. 32000D–04/201. Archivado desde el original (PDF) el 2017-10-25 . Consultado el 2016-10-22 .
  5. ^ Manual de referencia de la arquitectura Alpha (PDF) . Compaq . 2002. págs. 4-32, 4-34.
  6. ^ ab Manual para desarrolladores de software de 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. Número de publicación 24594.
  8. ^ "Manual del programador de la arquitectura AMD64, volumen 3: instrucciones generales y del sistema" (PDF) . Tecnología AMD64 (versión 3.28 ed.). Advanced Micro Devices (AMD). Septiembre de 2019 [2013]. Número de publicación 24594. Archivado (PDF) desde el 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 desde el original el 26 de junio de 2019.
  10. ^ ab Arquitectura MIPS para programadores. Volumen II-A: El conjunto de instrucciones MIPS32 (edición de revisión 3.02). MIPS Technologies . 2011. págs. 101–102. Archivado desde el original el 7 de noviembre de 2017. Consultado el 4 de enero de 2012 .
  11. ^ ab Arquitectura MIPS para programadores. Volumen II-A: El conjunto de instrucciones MIPS64 (Revisión 3.02 ed.). MIPS Technologies . 2011. págs. 105, 107, 122, 123.
  12. ^ Manual de referencia del programador de la familia M68000 (incluye instrucciones CPU32) (PDF) (revisión 1.ª ed.). Motorola . 1992. págs. 4-43–4-45. M68000PRM/AD. Archivado desde el 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 (versión 2.02 ed.). 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. ^ ab Wolf, Clifford (22 de marzo de 2019). "RISC-V "B" Bit Manipulation Extension for RISC-V" (PDF) . Github (borrador) (edición v0.37) . Consultado el 9 de enero de 2020 .
  16. ^ Arquitectura Oracle SPARC 2011. Oracle . 2011.
  17. ^ Manual de referencia de arquitectura VAX (PDF) . Digital Equipment Corporation (DEC). 1987. págs. 70–71. Archivado (PDF) desde el original el 29 de septiembre de 2019 . Consultado el 9 de enero de 2020 .
  18. ^ abc "Capítulo 22. Instrucciones de enteros vectoriales". Principios de funcionamiento de IBM z/Architecture (PDF) (undécima edición). IBM . Marzo de 2015. págs. 7-219–22-10. SA22-7832-10. Archivado desde el original (PDF) el 2020-01-09 . Consultado el 2020-01-10 .
  19. ^ ab "FFS(3)". Biblioteca para desarrolladores de Mac OS X. Apple, Inc. 19 de abril de 1994. Consultado el 4 de enero de 2012 .
  20. ^ "FFS(3)". Manual de funciones de biblioteca de FreeBSD . El proyecto FreeBSD . Consultado el 4 de enero de 2012 .
  21. ^ "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 .
  22. ^ "Registro de cambios de GCC 3.4.0". GCC 3.4.0 . Free Software Foundation, Inc. Consultado el 14 de noviembre de 2015 .
  23. ^ "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 .
  24. ^ "Código fuente de Clang". Equipo LLVM, Universidad de Illinois en Urbana-Champaign . Consultado el 9 de abril de 2017 .
  25. ^ "_BitScanForward, _BitScanForward64". Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . Consultado el 21 de mayo de 2018 .
  26. ^ "_BitScanReverse, _BitScanReverse64". Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . Consultado el 21 de mayo de 2018 .
  27. ^ "__lzcnt16, __lzcnt, __lzcnt64". Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . Consultado el 3 de enero de 2012 .
  28. ^ "Intrínsecos de ARM". Visual Studio 2012: Visual C++: Intrínsecos del compilador . Microsoft . Consultado el 9 de mayo de 2022 .
  29. ^ "Guía de intrínsecos de Intel". Intel . Consultado el 3 de abril de 2020 .
  30. ^ Referencia de intrínsecos del compilador Intel C++ para Linux. Intel . 2006. pág. 21.
  31. ^ Guía de programación NVIDIA CUDA (PDF) (versión 3.0 ed.). NVIDIA . 2010. pág. 92.
  32. ^ "'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 .
  33. ^ 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 . Consultado el 25 de mayo de 2020 .
  34. ^ "Encabezado de biblioteca estándar <bit>". cppreference.com . Consultado el 25 de mayo de 2020 .
  35. ^ ab SPARC International, Inc. (1992). "A.41: Recuento de población. Nota de programación" (PDF) . Manual de arquitectura SPARC: versión 8 (versión 8 ed.). Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice Hall . pp. 231. ISBN. 978-0-13-825001-0.
  36. ^ Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2.ª edición). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8. 0-321-84268-5.
  37. ^ Referencia del conjunto de instrucciones Blackfin (edición preliminar). Analog Devices . 2001. págs. 8-24. Número de pieza 82-000410-14.
  38. ^ Dietz, Henry Gordon . "Los algoritmos mágicos agregados". Universidad de Kentucky . Archivado desde el original el 31 de octubre de 2019.
  39. ^ Isenberg, Gerd (2019-11-03) [2012]. «BitScanProtected». Wiki de programación de ajedrez (CPW) . Archivado desde el original el 2020-01-09 . Consultado el 2020-01-09 .
  40. ^ Anderson. Redondea hacia arriba hasta la siguiente potencia más alta de 2.
  41. ^ abcd Warren. Capítulo 5-3: Contando los ceros iniciales.
  42. ^ abc Warren. Capítulo 5-4: Contando los ceros finales.
  43. ^ Leiserson, Charles E. ; Prokop, Harald ; Randall, Keith H. (1998-07-07). "Uso de secuencias de Bruijn para indexar un 1 en una palabra de computadora" (PDF) . MIT Laboratory for Computer Science, Cambridge, MA, EE. UU. Archivado (PDF) desde el original el 2020-01-09 . Consultado el 2020-01-09 .
  44. ^ Busch, Philip (2009-03-01) [2009-02-21]. "Cómo calcular ceros finales" (PDF) . Archivado (PDF) desde el original el 2016-08-01 . Consultado el 2020-01-09 .
  45. ^ Anderson. Halla el logaritmo en base 2 de un entero de N bits en O(lg(N)) operaciones con multiplicación y búsqueda.
  46. ^ Anderson. Halla el logaritmo entero en base 2 de un entero con un punto flotante IEEE de 64 bits.
  47. ^ Sloss, Andrew N.; Symes, Dominic; Wright, Chris (2004). Guía para desarrolladores de sistemas ARM: diseño y optimización del software de sistemas (1.ª ed.). San Francisco, CA, EE. UU.: Morgan Kaufmann . pp. 212–213. ISBN 978-1-55860-874-0.
  48. ^ Warren. Capítulo 2-11: Predicados de comparación.
  49. ^ Warren. Capítulo 6-2: Encontrar la primera cadena de 1 bits de una longitud dada.
  50. ^ Warren. Capítulo 11-1: Raíz cuadrada entera.
  51. ^ Schlegel, Benjamin; Gemulla, Rainer; Lehner, Wolfgang [en alemán] (junio de 2010). "Compresión rápida de números enteros mediante instrucciones SIMD". Actas del Sexto Taller Internacional sobre Gestión de Datos en Nuevo Hardware . pp. 34–40. CiteSeerX 10.1.1.230.6379 . doi :10.1145/1869389.1869394. ISBN .  978-1-45030189-3.S2CID 7545142  .
  52. ^ Warren. Capítulo 2-12: Detección de desbordamiento.
  53. ^ Gosper, Bill (abril de 1995) [29 de febrero de 1972]. Baker, Henry Givens Jr. (ed.). "Loop detector". HAKMEM (edición reescrita y convertida). Cambridge, Massachusetts, EE. UU.: Laboratorio de Inteligencia Artificial , Instituto Tecnológico de Massachusetts (MIT). AI Memo 239, artículo 132. Archivado desde el original el 8 de octubre de 2019. Consultado el 9 de enero de 2020 .
  54. ^ Aas, Josh (17 de febrero de 2005). Understanding the Linux 2.6.8.1 CPU Scheduler (PDF) (Entendiendo el programador de CPU de Linux 2.6.8.1) (PDF) (en inglés) . Silicon Graphics, Inc. (SGI). pág. 19. Archivado (PDF) desde el original el 19 de mayo de 2017. Consultado el 9 de enero de 2020 .

Lectura adicional

Enlaces externos