El peso Hamming de una cuerda es el número de símbolos que son diferentes del símbolo cero del alfabeto utilizado. Por lo tanto, es equivalente a la distancia de Hamming desde la cuerda todo ceros de la misma longitud. Para el caso más típico, una cadena de bits , este es el número de unos en la cadena, o la suma de dígitos de la representación binaria de un número dado y la norma ℓ ₁ de un vector de bits. En este caso binario, también se llama recuento de población , [1] recuento de pop , suma lateral , [2] osuma de bits . [3]
Cuerda | Peso de Hamming |
---|---|
111 0 1 | 4 |
111 0 1 000 | 4 |
00000000 | 0 |
678 0 1234 0 567 | 10 |
Un gráfico para el recuento de la población (peso de Hamming para números binarios) para números (decimales) del 0 al 256. [4] [5] [6] |
Historia y uso
El peso Hamming lleva el nombre de Richard Hamming, aunque él no originó la noción. [7] El peso de Hamming de los números binarios ya fue utilizado en 1899 por James WL Glaisher para dar una fórmula para el número de coeficientes binomiales impares en una sola fila del triángulo de Pascal . [8] Irving S. Reed introdujo un concepto, equivalente al peso de Hamming en el caso binario, en 1954. [9]
El peso Hamming se utiliza en varias disciplinas, incluida la teoría de la información , la teoría de la codificación y la criptografía . Ejemplos de aplicaciones del peso Hamming incluyen:
- En la exponenciación modular al elevar al cuadrado , el número de multiplicaciones modulares requeridas para un exponente e es log 2 e + peso ( e ). Esta es la razón por la que el valor de clave pública e utilizado en RSA se elige típicamente para que sea un número de peso Hamming bajo.
- El peso de Hamming determina las longitudes de ruta entre los nodos en las tablas hash distribuidas por Chord . [10]
- Las búsquedas de IrisCode en bases de datos biométricas se implementan normalmente calculando la distancia de Hamming a cada registro almacenado.
- En los programas informáticos de ajedrez que utilizan una representación de tablero de bits , el peso de Hamming de un tablero de bits da el número de piezas de un tipo determinado que quedan en el juego, o el número de casillas del tablero controladas por las piezas de un jugador, y por lo tanto es un término contribuyente importante. al valor de una posición.
- El peso de Hamming se puede usar para calcular de manera eficiente el primer conjunto de búsqueda usando la identidad ffs (x) = pop (x ^ (x-1)). Esto es útil en plataformas como SPARC que tienen instrucciones de peso Hamming de hardware, pero no hay instrucciones de primer conjunto de búsqueda de hardware. [11] [1]
- La operación de peso de Hamming se puede interpretar como una conversión del sistema de numeración unario a números binarios . [12]
- En la implementación de algunas estructuras de datos sucintas como vectores de bits y árboles de ondas .
Implementación eficiente
El recuento de población de una cadena de bits a menudo se necesita en criptografía y otras aplicaciones. La distancia de Hamming de dos palabras A y B puede ser calculada como el peso Hamming de A xor B . [1]
El problema de cómo implementarlo de manera eficiente ha sido ampliamente estudiado. En algunos procesadores están disponibles una sola operación para el cálculo u operaciones paralelas sobre vectores de bits . Para los procesadores que carecen de esas características, las mejores soluciones conocidas se basan en sumar recuentos en un patrón de árbol. Por ejemplo, para contar el número de 1 bits en el número binario de 16 bits a = 0110 1100 1011 1010, se pueden realizar estas operaciones:
Expresión | Binario | Decimal | Comentario | |||||||
---|---|---|---|---|---|---|---|---|---|---|
a | 01 | 10 | 11 | 00 | 10 | 11 | 10 | 10 | 27834 | El numero original |
b0 = (a >> 0) & 01 01 01 01 01 01 01 01 | 01 | 00 | 01 | 00 | 00 | 01 | 00 | 00 | 1, 0, 1, 0, 0, 1, 0, 0 | Cada dos pedazos de un |
b1 = (a >> 1) & 01 01 01 01 01 01 01 01 | 00 | 01 | 01 | 00 | 01 | 01 | 01 | 01 | 0, 1, 1, 0, 1, 1, 1, 1 | Los bits restantes de un |
c = b0 + b1 | 01 | 01 | 10 | 00 | 01 | 10 | 01 | 01 | 1, 1, 2, 0, 1, 2, 1, 1 | Cuenta de 1 en cada segmento de 2 bits de un |
d0 = (c >> 0) & 0011 0011 0011 0011 | 0001 | 0000 | 0010 | 0001 | 1, 0, 2, 1 | Cada otro cuenta de c | ||||
d2 = (c >> 2) & 0011 0011 0011 0011 | 0001 | 0010 | 0001 | 0001 | 1, 2, 1, 1 | Los restantes recuentos de c | ||||
e = d0 + d2 | 0010 | 0010 | 0011 | 0010 | 2, 2, 3, 2 | Cuenta de 1 en cada segmento de 4 bits de un | ||||
f0 = (e >> 0) & 00001111 00001111 | 00000010 | 00000010 | 2, 2 | Cada otro cuenta de e | ||||||
f4 = (e >> 4) & 00001111 00001111 | 00000010 | 00000011 | 2, 3 | El resto cuenta de e | ||||||
g = f0 + f4 | 00000100 | 00000101 | 4, 5 | Recuento de unos en cada segmento de 8 bits de un | ||||||
h0 = (g >> 0) & 0000000011111111 | 0000000000000101 | 5 | Cada otro cuenta de g | |||||||
h8 = (g >> 8) & 0000000011111111 | 0000000000000100 | 4 | Los restantes recuentos de g | |||||||
i = h0 + h8 | 0000000000001001 | 9 | Recuento de unos en una palabra completa de 16 bits |
Aquí, las operaciones son como en el lenguaje de programación C , por lo que X >> Y
significa desplazar X a la derecha en Y bits, X e Y significa el AND bit a bit de X e Y, y + es una suma ordinaria. Los mejores algoritmos conocidos para este problema se basan en el concepto ilustrado anteriormente y se dan aquí: [1]
// tipos y constantes utilizados en las funciones siguientes // uint64_t es un tipo de variable entera de 64 bits sin signo (definido en la versión C99 del lenguaje C) const uint64_t m1 = 0x5555555555555555 ; // binario: 0101 ... const uint64_t m2 = 0x3333333333333333 ; // binario: 00110011 .. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f ; // binario: 4 ceros, 4 unos ... const uint64_t m8 = 0x00ff00ff00ff00ff ; // binario: 8 ceros, 8 unos ... const uint64_t m16 = 0x0000ffff0000ffff ; // binario: 16 ceros, 16 unos ... const uint64_t m32 = 0x00000000ffffffff ; // binario: 32 ceros, 32 unos const uint64_t h01 = 0x0101010101010101 ; // la suma de 256 a la potencia de 0,1,2,3 ...// Esta es una implementación ingenua, mostrada para comparación, // y para ayudar a comprender las mejores funciones. // Este algoritmo usa 24 operaciones aritméticas (shift, add y). int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); // poner el recuento de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); // coloca el recuento de cada 4 bits en esos 4 bits x = ( x & m4 ) + (( x >> 4 ) & m4 ); // coloca el recuento de cada 8 bits en esos 8 bits x = ( x & m8 ) + (( x >> 8 ) & m8 ); // coloca el recuento de cada 16 bits en esos 16 bits x = ( x & m16 ) + (( x >> 16 ) & m16 ); // coloca el recuento de cada 32 bits en esos 32 bits x = ( x & m32 ) + (( x >> 32 ) & m32 ); // poner el recuento de cada 64 bits en esos 64 bits return x ; }// Esto usa menos operaciones aritméticas que cualquier otra // implementación conocida en máquinas con multiplicación lenta. // Este algoritmo utiliza 17 operaciones aritméticas. int popcount64b ( uint64_t x ) { x - = ( x >> 1 ) & m1 ; // poner el recuento de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); // coloca el recuento de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; // coloca el recuento de cada 8 bits en esos 8 bits x + = x >> 8 ; // coloca el recuento de cada 16 bits en sus 8 bits más bajos x + = x >> 16 ; // coloca el recuento de cada 32 bits en sus 8 bits más bajos x + = x >> 32 ; // coloca el recuento de cada 64 bits en sus 8 bits más bajos return x & 0x7f ; }// Esto usa menos operaciones aritméticas que cualquier otra // implementación conocida en máquinas con multiplicación rápida. // Este algoritmo utiliza 12 operaciones aritméticas, una de las cuales es una multiplicación. int popcount64c ( uint64_t x ) { x - = ( x >> 1 ) & m1 ; // poner el recuento de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); // coloca el recuento de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; // pone el recuento de cada 8 bits en esos 8 bits return ( x * h01 ) >> 56 ; // devuelve 8 bits a la izquierda de x + (x << 8) + (x << 16) + (x << 24) + ... }
Las implementaciones anteriores tienen el mejor comportamiento en el peor de los casos de cualquier algoritmo conocido. Sin embargo, cuando se espera que un valor tenga pocos bits distintos de cero, puede ser más eficiente utilizar algoritmos que cuenten estos bits de uno en uno. Como describió Wegner en 1960, [13] el AND bit a bit de x con x - 1 difiere de x solo en poner a cero el bit menos significativo distinto de cero: restar 1 cambia la cadena de ceros más a la derecha a 1s, y cambia el 1 más a la derecha a un 0 Si x originalmente tenía n bits que eran 1, luego de solo n iteraciones de esta operación, x se reducirá a cero. La siguiente implementación se basa en este principio.
// Esto es mejor cuando la mayoría de los bits en x son 0 // Este algoritmo funciona igual para todos los tamaños de datos. // Este algoritmo usa 3 operaciones aritméticas y 1 comparación / rama por "1" bit en x. int popcount64d ( uint64_t x ) { recuento int ; para ( cuenta = 0 ; x ; cuenta ++ ) x & = x - 1 ; recuento de devoluciones ; }
Si se permite un mayor uso de memoria, podemos calcular el peso de Hamming más rápido que los métodos anteriores. Con memoria ilimitada, podríamos simplemente crear una gran tabla de búsqueda del peso Hamming de cada entero de 64 bits. Si podemos almacenar una tabla de búsqueda de la función Hamming de cada entero de 16 bits, podemos hacer lo siguiente para calcular el peso Hamming de cada entero de 32 bits.
static uint8_t wordbits [ 65536 ] = { / * bitcounts de enteros 0 a 65535, inclusive * / }; // Este algoritmo usa 3 operaciones aritméticas y 2 lecturas de memoria. int popcount32e ( uint32_t x ) { return wordbits [ x & 0xFFFF ] + wordbits [ x >> 16 ]; }
// Opcionalmente, la tabla wordbits [] podría llenarse usando esta función int popcount32e_init ( void ) { uint32_t i ; uint16_t x ; int count ; para ( i = 0 ; i <= 0xFFFF ; i ++ ) { x = i ; for ( count = 0 ; x ; count ++ ) // tomado de popcount64d () arriba de x & = x - 1 ; bits de palabras [ i ] = contar ; } }
Muła y col. [14] han demostrado que una versión vectorizada de popcount64b puede ejecutarse más rápido que las instrucciones dedicadas (por ejemplo, popcnt en procesadores x64).
Peso mínimo
En la codificación con corrección de errores , el peso mínimo de Hamming, comúnmente denominado peso mínimo w min de un código, es el peso de la palabra de código distinta de cero de menor peso. El peso w de una palabra de código es el número de unos en la palabra. Por ejemplo, la palabra 11001010 tiene un peso de 4.
En un código de bloque lineal, el peso mínimo es también la distancia mínima de Hamming ( d min ) y define la capacidad de corrección de errores del código. Si w min = n , entonces d min = ny el código corregirá hasta d min / 2 errores. [15]
Ayuda de idioma
Algunos compiladores de C proporcionan funciones intrínsecas que proporcionan facilidades de conteo de bits. Por ejemplo, GCC (desde la versión 3.4 en abril de 2004) incluye una función incorporada __builtin_popcount
que usará una instrucción de procesador si está disponible o una implementación de biblioteca eficiente en caso contrario. [16] LLVM-GCC ha incluido esta función desde la versión 1.5 en junio de 2005. [17]
En C ++ STL , la estructura de datos de matriz de bits bitset
tiene un count()
método que cuenta el número de bits que se establecen. En C ++ 20 ,
se agregó un nuevo encabezado , que contiene funciones std::popcount
y std::has_single_bit
toma argumentos de tipos enteros sin signo.
En Java, la estructura de datos de matriz de bits que puede crecer BitSet
tiene un BitSet.cardinality()
método que cuenta el número de bits que se establecen. Además, existen funciones Integer.bitCount(int)
y Long.bitCount(long)
para contar bits en enteros primitivos de 32 y 64 bits, respectivamente. Además, la BigInteger
clase entera de precisión arbitraria también tiene un BigInteger.bitCount()
método que cuenta bits.
En Python , el int
tipo tiene un bit_count()
método para contar el número de bits establecidos. Esta funcionalidad es nueva en Python 3.10, cuyo lanzamiento está programado para 2021. [18]
En Common Lisp , la función logcount
, dado un entero no negativo, devuelve el número de 1 bits. (Para enteros negativos, devuelve el número de 0 bits en notación de complemento a 2). En cualquier caso, el entero puede ser un BIGNUM.
A partir de GHC 7.4, el paquete base de Haskell tiene una popCount
función disponible en todos los tipos que son instancias de la Bits
clase (disponible en el Data.Bits
módulo). [19]
La versión MySQL del lenguaje SQL proporciona BIT_COUNT()
una función estándar. [20]
Fortran 2008 tiene la función estándar, intrínseca y elemental que popcnt
devuelve el número de bits distintos de cero dentro de un entero (o matriz de enteros). [21]
Algunas calculadoras de bolsillo científicas programables cuentan con comandos especiales para calcular el número de bits establecidos, por ejemplo, #B
en HP-16C [3] [22] y WP 43S , [23] [24] #BITS
[25] [26] o BITSUM
[27] [28 ] en los emuladores HP-16C y nBITS
en el WP 34S . [29] [30]
FreePascal implementa popcnt desde la versión 3.0. [31]
Soporte de procesador
- La computadora IBM STRETCH en la década de 1960 calculó el número de bits establecidos así como el número de ceros a la izquierda como un subproducto de todas las operaciones lógicas. [1]
- Cray superordenadores desde el principio ofreció un recuento de la población instrucción de máquina , se rumorea que han sido solicitados específicamente por el gobierno de los EE.UU. Agencia de Seguridad Nacional de criptoanálisis aplicaciones. [1]
- Algunas de las máquinas de la serie Cyber 70/170 de Control Data Corporation (CDC) incluían una instrucción de conteo de población; en COMPASS , esta instrucción se codificó como .
CXi
- La arquitectura SPARC versión 9 de 64 bits define una
POPC
instrucción, [11] [1] pero la mayoría de las implementaciones no la implementan, requiriendo que sea emulada por el sistema operativo. [32] - El modelo de computadora MMIX de Donald Knuth que reemplazará a MIX en su libro The Art of Computer Programming tiene una
SADD
instrucción desde 1999.SADD a,b,c
cuenta todos los bits que son 1 en by 0 en cy escribe el resultado en a. - Compaq 's de Alpha 21264A , publicado en 1999, fue el primer diseño de la serie de la CPU alfa que tenía la extensión count (
CIX
). - Analog Devices ' Blackfin procesadores cuentan con la
ONES
instrucción de realizar un recuento de la población de 32 bits. [33] - La arquitectura de AMD en Barcelona introdujo la ISA de manipulación avanzada de bits (ABM) introduciendo la
POPCNT
instrucción como parte de las extensiones SSE4a en 2007. - Los procesadores Intel Core introdujeron una
POPCNT
instrucción con la extensión del conjunto de instrucciones SSE4.2 , disponible por primera vez en un procesador Core i7 basado en Nehalem , lanzado en noviembre de 2008. - La arquitectura ARM introdujo la
VCNT
instrucción como parte de las extensiones Advanced SIMD ( NEON ). - La arquitectura RISC-V introdujo la
PCNT
instrucción como parte de la extensión Bit Manipulation (B). [34]
Ver también
- Complemento a dos
- Personajes k más frecuentes
- Abanico
Referencias
- ↑ a b c d e f g Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. págs. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
- ^ Knuth, Donald Ervin (2009). "Trucos y técnicas bit a bit; Diagramas de decisión binarios". El arte de la programación informática . Volumen 4, fascículo 1. Addison – Wesley Professional . ISBN 978-0-321-58050-4.
|volume=
tiene texto extra ( ayuda )(NB. Borrador del fascículo 1b disponible para descargar). - ^ a b Manual del propietario del informático Hewlett-Packard HP-16C (PDF) . Compañía Hewlett-Packard . Abril de 1982. 00016-90001. Archivado (PDF) desde el original el 28 de marzo de 2017 . Consultado el 28 de marzo de 2017 .
- ^ [1] , escrito en Fōrmulæ. La wiki de Fōrmulæ . Consultado el 30 de septiembre de 2019.
- ^ Una solución a la tarea Recuento de población . Consultado el 30 de septiembre de 2019.
- ^ Código Rosetta . Consultado el 30 de septiembre de 2019.
- ^ Thompson, Thomas M. (1983). Desde códigos de corrección de errores a través de empaquetaduras de esferas hasta grupos simples . Las monografías matemáticas de Carus # 21. La Asociación Matemática de América . pag. 33.
- ^ Glaisher, James Whitbread Lee (1899). "Sobre el residuo de un coeficiente del teorema binomial con respecto a un módulo primo" . The Quarterly Journal of Pure and Applied Mathematics . 30 : 150-156. (NB. Véase en particular el último párrafo de la p. 156.)
- ^ Reed, Irving Stoy (1954). "Una clase de códigos de corrección de errores múltiples y el esquema de decodificación". Grupo Profesional IRE de Teoría de la Información . Instituto de Ingenieros de Radio (IRE). PGIT-4: 38–49.
- ^ Stoica, I .; Morris, R .; Liben-Nowell, D .; Karger, DR; Kaashoek, MF; Dabek, F .; Balakrishnan, H. (febrero de 2003). "Chord: un protocolo de búsqueda de igual a igual escalable para aplicaciones de Internet". Transacciones IEEE / ACM sobre redes . 11 (1): 17–32. doi : 10.1109 / TNET.2002.808407 . S2CID 221276912 .
Sección 6.3: "En general, el número de dedos que debemos seguir será el número de unos en la representación binaria de la distancia del nodo a la consulta".
- ^ a b SPARC International, Inc. (1992). "A.41: Conteo de población. Nota de programación" . El manual de arquitectura SPARC: versión 8 (Versión 8 ed.). Englewood Cliffs, Nueva Jersey, EE.UU .: Prentice Hall . págs. 231 . ISBN 0-13-825001-4.
- ^ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (eds.). "Registro de vinculación por coincidencia de patrón de bits" . Informática y Estadística - Décimo Simposio Anual sobre la Interfaz . Publicación especial de NBS. Departamento de Comercio de EE. UU. / Oficina Nacional de Normas . 503 : 146-156.
- ^ Wegner, Peter (mayo de 1960). "Una técnica para contar unos en una computadora binaria". Comunicaciones de la ACM . 3 (5): 322. doi : 10.1145 / 367236.367286 . S2CID 31683715 .
- ^ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (enero de 2018). "Conteo de población más rápido usando instrucciones AVX2". Revista informática . 61 (1): 111-120. arXiv : 1611.07612 . doi : 10.1093 / comjnl / bxx046 . S2CID 540973 .
- ^ Stern & Mahmoud, Diseño de sistemas de comunicaciones , Prentice Hall , 2004, p 477ff.
- ^ "Notas de la versión GCC 3.4" . Proyecto GNU .
- ^ "Notas de la versión LLVM 1.5" . Proyecto LLVM .
- ^ "Novedades de Python 3.10" . python.org .
- ^ "Notas de la versión GHC 7.4.1" . Documentación de GHC.
- ^ "Capítulo 12.11. Funciones de bits - Manual de referencia de MySQL 5.0" .
- ^ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Fortran moderno explicado . Prensa de la Universidad de Oxford . pag. 380. ISBN 978-0-19-960142-4.
- ^ Schwartz, Jake; Grevelle, Rick (20 de octubre de 2003) [1993]. Biblioteca del emulador HP16C para HP48S / SX . 1.20 (1 ed.) . Consultado el 15 de agosto de 2015 .(Nota: esta biblioteca también funciona en HP 48G / GX / G + . Más allá del conjunto de funciones de HP-16C, este paquete también admite cálculos para números de coma flotante binarios, octales y hexadecimales en notación científica además del decimal habitual Números de punto flotante.)
- ^ Bonin, Walter (2019) [2015]. Manual del propietario del WP 43S (PDF) . 0.12 (borrador ed.). pag. 135. ISBN 978-1-72950098-9. Consultado el 5 de agosto de 2019 . [2] [3] (314 páginas)
- ^ Bonin, Walter (2019) [2015]. Manual de referencia de WP 43S (PDF) . 0.12 (borrador ed.). págs. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Consultado el 5 de agosto de 2019 . [4] [5] (271 páginas)
- ^ Martín, Ángel M .; McClure, Greg J. (5 de septiembre de 2015). "Módulo emulador HP16C para HP-41CX - Manual de usuario y QRG" (PDF) . Archivado (PDF) desde el original el 27 de abril de 2017 . Consultado el 27 de abril de 2017 .(NB. Más allá del conjunto de funciones de HP-16C , esta biblioteca personalizada para la HP-41CX amplía la funcionalidad de la calculadora en aproximadamente 50 funciones adicionales).
- ^ Martín, Ángel M. (7 de septiembre de 2015). "HP-41: Nuevo emulador HP-16C disponible" . Archivado desde el original el 27 de abril de 2017 . Consultado el 27 de abril de 2017 .
- ^ Thörngren, Håkan (10 de enero de 2017). "Documentación de Ladybug" (versión 0A ed.) . Consultado el 29 de enero de 2017 . [6]
- ^ "Nuevo módulo HP-41 disponible: Ladybug" . 2017-01-10. Archivado desde el original el 29 de enero de 2017 . Consultado el 29 de enero de 2017 .
- ^ Dale, Paul; Bonin, Walter (2012) [2008]. "Manual del propietario del WP 34S" (PDF) (3.1 ed.) . Consultado el 27 de abril de 2017 .
- ^ Bonin, Walter (2015) [2008]. Manual del propietario del WP 34S (3.3 ed.). ISBN 978-1-5078-9107-0.
- ^ "Documentación popcnt libre de Pascal" . Consultado el 7 de diciembre de 2019 .
- ^ "JDK-6378821: bitCount () debería usar POPC en procesadores SPARC y AMD + 10h" . Base de datos de errores de Java . 2006-01-30.
- ^ Referencia del conjunto de instrucciones Blackfin (edición preliminar). Dispositivos analógicos . 2001. págs. 8-24. Número de pieza 82-000410-14.
- ^ Wolf, Clifford (22 de marzo de 2019). Extensión de manipulación de bits "RISC-V" B "para RISC-V, borrador v0.37" (PDF) . Github .
Otras lecturas
- Schroeppel, Richard C .; Orman, Hilarie K. (29 de febrero de 1972). "Compilacion". HAKMEM . Por Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (informe). Laboratorio de Inteligencia Artificial , Instituto de Tecnología de Massachusetts , Cambridge, Massachusetts, EE. UU. MIT AI Memo 239.( Ítem 169 : Código de ensamblaje de conteo de población para el PDP / 6-10.)
enlaces externos
- Algoritmos mágicos agregados . Recuento de población optimizado y otros algoritmos explicados con código de muestra.
- Bit Twiddling Hacks Varios algoritmos con código para contar bits establecidos.
- Necesario y suficiente - por Damien Wintour - Tiene código en C # para varias implementaciones de Hamming Weight.
- ¿El mejor algoritmo para contar el número de bits establecidos en un entero de 32 bits? - Desbordamiento de pila