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 firmar , [nb 1] designa el índice o posición del conjunto de bits menos significativo a uno en la palabra contando 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 la posición del bit establecido más significativo eslog base 2 , llamado así porque calcula el logaritmo binario ⌊log 2 (x) ⌋ . [1] Esto está estrechamente relacionado con el recuento de ceros iniciales ( clz ) o el 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 find first set, la definición POSIX que comienza a indexar bits en 1, [2] aquí etiquetada como ffs, y la variante que comienza a indexar bits en cero, que es equivalente a ctz y así será llamado por 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; La emulación de software generalmente se proporciona para cualquiera que no esté disponible, ya sea como elementos intrínsecos del compilador o en bibliotecas del sistema.
Ejemplos de
Dada la siguiente palabra de 32 bits:
- 0000 0000 0000 0000 1000 0000 0000 1000
La operación de contar ceros a la izquierda devolvería 3, mientras que la operación de contar ceros a la izquierda devolvería 16. La operación de contar ceros a la izquierda depende del tamaño de la palabra: si esta palabra de 32 bits se trunca a una palabra de 16 bits, la operación de contar ceros a la izquierda devolvería cero . La operación de buscar el primer conjunto devolvería 4, lo que indica la cuarta posición desde la derecha. La base logarítmica 2 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 recuento de los últimos devolvería 3, la operación de recuento de los primeros devolvería 16 y la operación de encontrar el primer cero ffz devolvería 4.
Si la palabra es cero (sin bits establecidos), contar los ceros iniciales y los ceros finales, ambos devuelven el número de bits de la palabra, mientras que ffs devuelve cero. Tanto las implementaciones log base 2 como las basadas en cero del primer conjunto de buscar 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 ceros a la izquierda (clz), probablemente porque todas las demás operaciones se pueden implementar de manera eficiente en términos de ella (ver Propiedades y relaciones ).
Plataforma | Mnemotécnico | Nombre | Anchos de operando | Descripción | En aplicación a 0 |
---|---|---|---|---|---|
ARM ( arquitectura ARMv5T y posterior ) excepto Cortex-M0 / M0 + / M1 / M23 | clz [3] | Contar ceros iniciales | 32 | clz | 32 |
ARM ( arquitectura ARMv8-A ) | clz | Contar ceros iniciales | 32, 64 | clz | Ancho de operando |
AVR32 | clz [4] | Contar ceros iniciales | 32 | clz | 32 |
DEC Alpha | ctlz [5] | Contar ceros iniciales | 64 | clz | 64 |
cttz [5] | Contar ceros finales | 64 | ctz | 64 | |
Intel 80386 y posterior | bsf [6] | Exploración de bits hacia adelante | 16, 32, 64 | ctz | Indefinido; establece bandera cero |
bsr [6] | Exploración de bits inversa | 16, 32, 64 | Base de troncos 2 | Indefinido; establece bandera cero | |
x86 compatible con BMI1 o ABM | lzcnt [7] | Contar ceros iniciales | 16, 32, 64 | clz | Ancho de operando; conjuntos llevan bandera |
x86 compatible con BMI1 | tzcnt [8] | Contar ceros finales | 16, 32, 64 | ctz | Ancho de operando; conjuntos llevan bandera |
Itanium | clz [9] | Contar ceros iniciales | 64 | clz | 64 |
MIPS | clz [10] [11] | Contar ceros iniciales en Word | 32, 64 | clz | Ancho de operando |
clo [10] [11] | Cuente los líderes en Word | 32, 64 | clo | Ancho de operando | |
Motorola 68020 y posterior | bfffo [12] | Encuentra el primero en el campo de bits | Arbitrario | Base de troncos 2 | Desplazamiento de campo + ancho de campo |
PDP-10 | jffo | Saltar si encuentra el primero | 36 | ctz | 0; No operacion |
POWER / PowerPC / Power ISA | cntlz / cntlzw / cntlzd [13] | Contar ceros iniciales | 32, 64 | clz | Ancho de operando |
Power ISA 3.0 y posterior | cnttzw / cnttzd [14] | Contar ceros finales | 32, 64 | ctz | Ancho de operando |
RISC-V (Extensión "B") (borrador) | clz [15] | Contar ceros iniciales | 32, 64 | clz | Ancho de operando |
ctz [15] | Contar ceros finales | 32, 64 | ctz | Ancho de operando | |
SPARC Oracle Architecture 2011 y posterior | lzcnt (sinónimo: lzd) [16] | Líder en conteo cero | 64 | clz | 64 |
VAX | ffs [17] | Encontrar el primer conjunto | 0–32 | ctz | Ancho de operando; establece bandera cero |
IBM z / Arquitectura | flogr [18] | Encontrar uno más a la izquierda | 64 | clz | 64 |
vclz [18] | Recuento de vectores a la izquierda | 8, 16, 32, 64 | clz | Ancho de operando | |
vctz [18] | Recuento de vectores ceros finales | 8, 16, 32, 64 | ctz | Ancho de operando |
En algunas plataformas Alpha, CTLZ y CTTZ se emulan en software.
Soporte de herramientas y biblioteca
Varios proveedores de compiladores y bibliotecas proporcionan funciones intrínsecas del compilador o de biblioteca para realizar la búsqueda del primer conjunto y / o operaciones relacionadas, que se implementan con frecuencia en términos de las instrucciones de hardware anteriores:
Herramienta / biblioteca | Nombre | Tipo | Tipo (s) de entrada | Notas | En aplicación a 0 |
---|---|---|---|---|---|
POSIX .1 compatible con libc 4.3BSD libc OS X 10.3 libc [2] [19] | ffs | Función de biblioteca | En t | Incluye glibc . POSIX no suministra la base logarítmica complementaria 2 / clz. | 0 |
FreeBSD 5.3 libc OS X 10.4 libc [19] | ffsl fls flsl | Función de biblioteca | int, largo | fls ("buscar el último conjunto") calcula (base de registro 2) + 1. | 0 |
FreeBSD 7.1 libc [20] | ffsll flsll | Función de biblioteca | largo largo | 0 | |
CGC 3.4.0 [21] [22] Clang 5.x [23] [24] | __builtin_ffs[l,ll,imax] __builtin_clz[l,ll,imax] __builtin_ctz[l,ll,imax] | Funciones integradas | unsigned int, unsigned long, unsigned long long, uintmax_t | La documentación de GCC considera el resultado clz indefinido y ctz en 0. | 0 (ffs) |
Visual Studio 2005 | _BitScanForward [25] _BitScanReverse [26] | Elementos intrínsecos del compilador | unsigned long, unsigned __int64 | Valor de retorno separado para indicar entrada cero | Indefinido |
Visual Studio 2008 | __lzcnt [27] | Compilador intrínseco | unsigned short, unsigned int, unsigned __int64 | Se basa en el soporte de hardware para la instrucción lzcnt introducida en BMI1 o ABM . | Ancho de operando |
Compilador Intel C ++ | _bit_scan_forward _bit_scan_reverse [28] [29] | Elementos intrínsecos del compilador | En t | Indefinido | |
NVIDIA CUDA [30] | __clz | Funciones | 32 bits, 64 bits | Compila con menos instrucciones en la serie GeForce 400 | 32 |
__ffs | 0 | ||||
LLVM | llvm.ctlz.* llvm.cttz.* [31] | Intrínseco | 8, 16, 32, 64, 256 | Lenguaje ensamblador LLVM | Ancho del operando, si el segundo argumento es 0; indefinido de lo contrario |
GHC 7.10 (base 4.8), en Data.Bits [ cita requerida ] | countLeadingZeros countTrailingZeros | Función de biblioteca | FiniteBits b => b | Lenguaje de programación Haskell | Ancho de operando |
Biblioteca estándar de C ++ 20 , en el encabezado [32] [33] | bit_ceil bit_floor bit_width countl_zero countl_one countr_zero countr_one | Función de biblioteca | unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long |
Propiedades y relaciones
Si los bits están etiquetados comenzando en 1 (que es la convención utilizada en este artículo), las operaciones de contar ceros finales y buscar el primer conjunto están relacionadas por ctz ( x ) = ffs ( x ) - 1 (excepto cuando la entrada es cero). Si los bits están etiquetados comenzando en 0 , entonces contar los ceros finales y buscar 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 demostró en el ejemplo anterior, las operaciones de buscar el primer cero, contar los primeros y contar los últimos se pueden implementar negando la entrada y usando buscar el primer conjunto, contar los ceros a la izquierda y contar los ceros al final. Lo contrario también es cierto.
En plataformas con una operación eficiente de log 2 [ ¿cuál? ] como M68000, ctz se puede calcular mediante:
- ctz ( x ) = log 2 ( x y −x )
donde & denota AND bit a bit y −x denota el complemento a dos de x . La expresión x y -x borra todos pero el menos significativo 1 bits, por lo que el MOST y el menos significativo 1 bits son los mismos.
En plataformas con una operación eficiente de contar ceros a la cabeza, como ARM y PowerPC, ffs se puede calcular mediante:
- ffs ( x ) = w - clz ( x y −x ) .
Por el contrario, en máquinas sin operadores log 2 o clz , clz se puede calcular usando 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 eficiente de peso Hamming (recuento de población) como SPARC 's POPC
[34] [35] o Blackfin 's ONES
, [36] hay:
- ctz ( x ) = popcount (( x & −x ) - 1) , [37] [38] o ctz ( x ) = popcount (~ ( x | −x )) ,
- ffs ( x ) = popcount ( x ^ ~ - x ) [34]
- clz = 32 - recuento de pop (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 , produce una x tal que ctz ( x ) = i ) se puede calcular con un desplazamiento a la izquierda ( 1 << i ).
Encuentra primer conjunto y las operaciones conexas pueden extenderse a arbitrariamente grandes matrices de bits de una manera directa por comenzando en un extremo y siguiendo hasta una palabra que no es de todo ceros (por FFS , CTZ , CLZ ) o no todo-uno (para FFZ , clo , cto ). Una estructura de datos de árbol que utiliza de forma recursiva mapas de bits para rastrear qué palabras son distintas de cero puede acelerar esto.
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 algunos modernos como algunos de la serie ARM-Mx no los tienen. En lugar de operadores de hardware para ffs, clz y ctz, el software puede emularlos con cambios, aritmética de enteros y operadores bit a bit. Existen 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 del código del compilador. Los enfoques pueden describirse libremente como búsqueda lineal , búsqueda binaria , búsqueda + búsqueda de tabla, multiplicación 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 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 otras operaciones.
Si uno tiene un hardware clz o equivalente, ctz se puede calcular de manera eficiente con operaciones de bits, pero lo contrario no es cierto: clz no es eficiente para calcular en ausencia de un operador de hardware.
2 n
La función 2 ⌈log 2 (x) ⌉ (redondear a la potencia más cercana de dos) usando desplazamientos y OR bit a bit [39] no es eficiente para calcular como en este ejemplo de 32 bits y aún más ineficiente si tenemos un 64- operando de bits o de 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
FFS
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 sumar 1 al resultado y devolver 0 en lugar de la longitud del operando para la entrada de todos los bits cero.
CTZ
El algoritmo canónico es un ciclo que cuenta ceros comenzando en el LSB hasta que se encuentra un bit de 1:
función ctz1 (x) si x = 0 devuelve w t ← 1 r ← 0 mientras (x & t) = 0 t ← t << 1 r ← r + 1 volver r
Este algoritmo ejecuta O (n) tiempos y operaciones, y no es práctico en la práctica debido a una gran cantidad de ramificaciones 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 return r + tabla [x & (2 n -1)] x ← x >> n r ← r + n
El parámetro n es fijo (típicamente 8) y representa una compensación espacio-temporal . 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 toma un número logarítmico de operaciones y ramificaciones, como en esta versión de 32 bits: [40] [41] Este algoritmo también puede ser asistido por una tabla, reemplazando las tres últimas declaraciones "if" con una entrada de 256 tabla de búsqueda utilizando el primer byte distinto de cero encontrado como índice.
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 devuelve n
Si el hardware tiene un operador clz, el enfoque más eficiente para calcular ctz es:
función ctz4 (x) x & = -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. [42] [43] Este algoritmo asume 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) vuelve a aislar el bit 1 menos significativo. Entonces hay solo 32 palabras posibles, que la multiplicación sin signo y el hash de desplazamiento a la posición correcta en la tabla. (Este algoritmo no maneja la entrada 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 en el enfoque de bucle anterior examina ocho bits a la vez y luego utiliza una tabla de búsqueda de entrada de 256 ( 28 ) para el primer byte distinto de cero. Este enfoque, sin embargo, todavía está 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 return 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 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 usar una búsqueda de mayor ancho, pero el tamaño de tabla práctico máximo 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 está más que compensado por la latencia de una falta de caché L1 .
Un algoritmo similar a la multiplicación de Bruijn para CTZ funciona para CLZ, pero en lugar de aislar el bit más significativo, redondea al número entero más cercano de la forma 2 n −1 usando desplazamientos y OR bit a bit: [44]
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) devuelve la 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 ramas por operadores AND y OR bit a bit (aunque se requieren muchas más instrucciones) para evitar descargas de tuberías 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); return r;
En las plataformas que proporcionan conversión por 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. [40] [45] La conversión de punto flotante puede tener una latencia sustancial. Este método es altamente no portátil y generalmente no se recomienda.
int x ; int r ; union { 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 usar para implementar de manera eficiente 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, puede usarse para implementar la división Newton-Raphson , realizar conversión de entero a punto flotante en software y otras aplicaciones. [40] [46]
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 tiene signo. Giro a la derecha. [47] Se puede utilizar para realizar operaciones de bits más sofisticadas, como encontrar la primera cadena de n 1 bits. [48] La expresión clz (x - y) 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 . [49] CLZ puede implementar eficientemente 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 cero a la izquierda junto con los bytes distintos de cero. [50] También puede generar eficientemente enteros distribuidos exponencialmente tomando la clz de enteros uniformemente aleatorios . [40]
La base logarítmica 2 puede usarse para anticipar si una multiplicación se desbordará, ya que ⌈log 2 (xy) ⌉ ≤ ⌈log 2 (x) ⌉ + ⌈log 2 (y) ⌉ . [51]
Contar ceros a la izquierda y contar ceros a la derecha se pueden usar juntos para implementar el algoritmo de detección de bucles de Gosper , [52] que puede encontrar el período de una función de rango finito usando recursos limitados. [41]
El algoritmo binario GCD pasa muchos ciclos eliminando ceros finales; esto puede ser reemplazado por un recuento de ceros finales (ctz) seguido de un desplazamiento. Aparece un bucle similar 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 la operación "pop" o "extraer el elemento de mayor prioridad" de manera eficiente. El programador en tiempo real del kernel de Linux lo utiliza internamente sched_find_first_bit()
para este propósito. [53]
La operación de contar 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 alrededor de la 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 . [41]
Ver también
- Conjuntos de instrucciones de manipulación de bits (BMI) para procesadores basados en Intel y AMD x86
- Cero final
- Líder cero
- Dígito final
- Dígito principal
Notas
- ^ El uso de operaciones de bits en una palabra de máquina que no sea sin firmar puede producir resultados no definidos.
- ^ Estas cuatro operaciones también tienen versiones negadas (mucho menos comunes):
- encuentre el primer cero ( ffz ), que identifica el índice del bit cero menos significativo;
- contar los últimos , que cuenta el número de bits uno que sigue al bit cero menos significativo.
- contar los primeros , que cuenta el número de bits uno que preceden al bit cero más significativo;
- Encuentre el índice del bit cero más significativo, que es una versión invertida del logaritmo binario .
Referencias
- ^ Anderson . Encuentre la base logarítmica 2 de un número entero con el MSB N establecido en operaciones O (N) (la forma obvia) .
- ^ a b "FFS (3)" . Manual del programador de Linux . Los archivos del kernel de Linux . Consultado el 2 de enero de 2012 .
- ^ "Referencia de instrucciones ARM> Instrucciones generales de procesamiento de datos ARM> CLZ" . Guía del ensamblador de ARM Developer Suite . BRAZO . Consultado el 3 de enero de 2012 .
- ^ "Documento de arquitectura AVR32" (PDF) (CORP072610 ed.). Atmel Corporation . 2011. 32000D – 04/201. Archivado desde el original (PDF) el 25 de octubre de 2017 . Consultado el 22 de octubre de 2016 .
- ^ a b Manual de referencia de la arquitectura Alpha (PDF) . Compaq . 2002. págs. 4-32, 4-34.
- ^ a b Manual para desarrolladores de software de arquitecturas Intel 64 e IA-32 . Volumen 2A. Intel . págs. 3-92-3-97.
|volume=
tiene texto extra ( ayuda ) Número de pedido 325383. - ^ Manual del programador de la arquitectura AMD64 Volumen 3: Propósito general e instrucciones del sistema (PDF) . 3 . Microdispositivos avanzados (AMD). 2011. págs. 204–205. Publicación No. 24594.
- ^ "Manual del programador de la arquitectura AMD64, volumen 3: instrucciones de uso general y del sistema" (PDF) . Tecnología AMD64 (Versión 3.28 ed.). Microdispositivos avanzados (AMD). Septiembre de 2019 [2013]. Publicación núm. 24594. Archivado (PDF) desde el original el 30 de septiembre de 2019 . Consultado el 2 de enero de 2014 .
- ^ Manual del desarrollador de software de la arquitectura Intel Itanium. Volumen 3: Conjunto de instrucciones de Intel Itanium . 3 . Intel . 2010. págs. 3:38. Archivado desde el original el 26 de junio de 2019.
- ^ a b Arquitectura MIPS para programadores. Volumen II-A: El conjunto de instrucciones MIPS32 (Revisión 3.02 ed.). Tecnologías MIPS . 2011. págs. 101-102.
- ^ a b Arquitectura MIPS para programadores. Volumen II-A: El conjunto de instrucciones MIPS64 (Revisión 3.02 ed.). Tecnologías MIPS . 2011. págs. 105, 107, 122, 123.
- ^ Manual de referencia del programador de la familia M68000 (incluye instrucciones de 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.
- ^ Frey, Brad. "Capítulo 3.3.11 Instrucciones lógicas de punto fijo". Libro de arquitectura de PowerPC (Versión 2.02 ed.). IBM . pag. 70.
- ^ "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.
- ^ a b Wolf, Clifford (22 de marzo de 2019). Extensión de manipulación de bits "RISC-V" B "para RISC-V" (PDF) . Github (borrador) (v0.37 ed.) . Consultado el 9 de enero de 2020 .
- ^ Arquitectura Oracle SPARC 2011 . Oracle . 2011.
- ^ Manual de referencia de arquitectura VAX (PDF) . Corporación de Equipos Digitales (DEC). 1987. págs. 70–71. Archivado (PDF) desde el original el 29 de septiembre de 2019 . Consultado el 9 de enero de 2020 .
- ^ a b c "Capítulo 22. Instrucciones de enteros vectoriales". IBM z / Architecture Principles of Operation (PDF) (undécima ed.). IBM . Marzo de 2015. págs. 7-219–22-10. SA22-7832-10 . Consultado el 10 de enero de 2020 .
- ^ a b "FFS (3)" . Mac OS X Developer Library . Apple, Inc. 19 de abril de 1994 . Consultado el 4 de enero de 2012 .
- ^ "FFS (3)" . Manual de funciones de la biblioteca FreeBSD . El Proyecto FreeBSD . Consultado el 4 de enero de 2012 .
- ^ "Otras funciones integradas proporcionadas por GCC" . Usando la colección de compiladores GNU (GCC) . Free Software Foundation, Inc. Consultado el 14 de noviembre de 2015 .
- ^ "GCC 3.4.0 ChangeLog" . GCC 3.4.0 . Free Software Foundation, Inc. Consultado el 14 de noviembre de 2015 .
- ^ "Extensiones de lenguaje Clang - capítulo Funciones integradas" . El equipo de Clang . Consultado el 9 de abril de 2017 .
Clang admite una serie de funciones de biblioteca integradas con la misma sintaxis que GCC
- ^ "Código fuente de Clang" . Equipo LLVM, Universidad de Illinois en Urbana-Champaign . Consultado el 9 de abril de 2017 .
- ^ "_BitScanForward, _BitScanForward64" . Visual Studio 2008: Visual C ++: intrínsecos del compilador . Microsoft . Consultado el 21 de mayo de 2018 .
- ^ "_BitScanReverse, _BitScanReverse64" . Visual Studio 2008: Visual C ++: intrínsecos del compilador . Microsoft . Consultado el 21 de mayo de 2018 .
- ^ "__lzcnt16, __lzcnt, __lzcnt64" . Visual Studio 2008: Visual C ++: intrínsecos del compilador . Microsoft . Consultado el 3 de enero de 2012 .
- ^ "Guía de intrínsecos de Intel" . Intel . Consultado el 3 de abril de 2020 .
- ^ Compilador Intel C ++ para referencia intrínseca de Linux . Intel . 2006. p. 21.
- ^ Guía de programación de NVIDIA CUDA (PDF) (Versión 3.0 ed.). NVIDIA . 2010. p. 92.
- ^ " ' 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 .
- ^ Smith, Richard (1 de abril de 2020). Borrador de trabajo N4861, Estándar para lenguaje de programación C ++ (PDF) . ISO / IEC. págs. 1150-1153 . Consultado el 25 de mayo de 2020 .
- ^ "Encabezado de biblioteca estándar " . cppreference.com . Consultado el 25 de mayo de 2020 .
- ^ a b SPARC International, Inc. (1992). "A.41: Conteo de población. Nota de programación" (PDF) . El manual de arquitectura SPARC: versión 8 (Versión 8 ed.). Englewood Cliffs, Nueva Jersey, EE.UU .: Prentice Hall . págs. 231 . ISBN 978-0-13-825001-0.
- ^ 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.
- ^ Referencia del conjunto de instrucciones Blackfin (edición preliminar). Dispositivos analógicos . 2001. págs. 8-24. Número de pieza 82-000410-14.
- ^ Dietz, Henry Gordon . "Los algoritmos mágicos agregados" . Universidad de Kentucky . Archivado desde el original el 31 de octubre de 2019.
- ^ Isenberg, Gerd (3 de noviembre de 2019) [2012]. "BitScanProtected" . Wiki de programación de ajedrez (CPW) . Archivado desde el original el 9 de enero de 2020 . Consultado el 9 de enero de 2020 .
- ^ Anderson . Redondea a la siguiente potencia más alta de 2 .
- ^ a b c d Warren . Capítulo 5-3: Contar ceros iniciales.
- ^ a b c Warren . Capítulo 5-4: Contar ceros finales.
- ^ Leiserson, Charles E .; Prokop, Harald ; Randall, Keith H. (7 de julio de 1998). "Uso de secuencias 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) desde el original el 9 de enero de 2020 . Consultado el 9 de enero de 2020 .
- ^ Busch, Philip (1 de marzo de 2009) [21 de febrero de 2009]. "Cómputo CÓMO de ceros finales" (PDF) . Archivado (PDF) desde el original el 1 de agosto de 2016 . Consultado el 9 de enero de 2020 .
- ^ Anderson . Encuentre la base logarítmica 2 de un entero de N bits en operaciones O (lg (N)) con multiplicar y buscar .
- ^ Anderson . Encuentre la base de registro de enteros 2 de un entero con un flotante IEEE de 64 bits .
- ^ Sloss, Andrew N .; Symes, Dominic; Wright, Chris (2004). Guía del desarrollador del sistema ARM para diseñar y optimizar el software del sistema (1 ed.). San Francisco, CA, EE.UU .: Morgan Kaufmann . págs. 212-213. ISBN 978-1-55860-874-0.
- ^ Warren . Capítulo 2-11: Predicados de comparación.
- ^ Warren . Capítulo 6-2: Encuentre la primera cadena de 1 bits de una longitud determinada.
- ^ Warren . Capítulo 11-1: Raíz cuadrada entera.
- ^ Schlegel, Benjamin; Gemulla, Rainer ; Lehner, Wolfgang (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 (DaMoN 2010) . págs. 34–40. CiteSeerX 10.1.1.230.6379 . doi : 10.1145 / 1869389.1869394 . ISBN 978-1-45030189-3.
- ^ Warren . Capítulo 2-12: Detección de desbordamiento.
- ^ Gosper, Bill (abril de 1995) [29 de febrero de 1972]. Baker, Jr., Henry Givens (ed.). "Detector de bucle" . HAKMEM (reescrito y convertido ed.). Cambridge, Massachusetts, EE.UU .: Laboratorio de Inteligencia Artificial , Instituto de Tecnología 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 .
- ^ Aas, Josh (17 de febrero de 2005). Comprensión del programador de CPU de Linux 2.6.8.1 (PDF) . Silicon Graphics, Inc. (SGI). pag. 19. Archivado (PDF) desde el original el 19 de mayo de 2017 . Consultado el 9 de enero de 2020 .
Otras lecturas
- 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 desde el original el 8 de enero de 2020 . Consultado el 3 de enero de 2012 .(NB. Enumera varias implementaciones de C de dominio público eficientes para contar ceros finales y base logarítmica 2 ).
enlaces externos
- Guía de intrínsecos de Intel
- Wiki de programación de ajedrez: BitScan : una explicación detallada de varios métodos de implementación para ffs (llamado LS1B) y log base 2 (llamado MS1B).