Peso de Hamming
número de símbolos distintos de cero en una cadena
El peso de Hamming de una cadena de caracteres 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 de la cadena de 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 el caso binario, también se denomina recuento de población,[4] suma lateral,[5] o suma de bits.[6]
| Cadena de caracteres | Peso de Hamming |
|---|---|
| 11101 | 4 |
| 11101000 | 4 |
| 00000000 | 0 |
| 678012340567 | 10 |
Historia y uso
editarLa función lleva el nombre de Richard Hamming, aunque él no originó el concepto.[7] El peso de Hamming de los números binarios ya fue utilizado en 1899 por James W. L. 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 Stoy Reed también introdujo en 1954 un concepto equivalente en el caso binario.[9]
El peso de Hamming se usa en varias disciplinas, incluidas la teoría de la información, la teoría de códigos y la criptografía. Ejemplos de aplicaciones del peso de Hamming incluyen:
- La exponenciación binaria modular; el número de multiplicaciones modulares necesarias para un exponente e es log2 e + peso(e). Esta es la razón por la que el valor de la clave pública e que se utiliza en RSA normalmente se elige como un número de bajo peso de Hamming.[10]
- El peso de Hamming determina las longitudes de ruta entre nodos en las tablas del algoritmo Chord.[11]
- Las técnicas de reconocimiento de iris en las bases de datos biométricas se implementan normalmente calculando la distancia de Hamming de cada registro almacenado.
- En los programas de ajedrez por computadora que utilizan una representación bitboard, 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 controlado 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 encontrar el primer conjunto de manera eficiente usando la identidad ffs(x) = pop(x ^ (x - 1)). Esto es útil en plataformas como Sun SPARC que tienen instrucciones de peso de Hamming de hardware pero ninguna instrucción de primer conjunto de búsqueda de hardware.[12][4]
- La operación de peso de Hamming se puede interpretar como una conversión del sistema de numeración unario al sistema binario.[13]
- En el manejo de algunas estructuras de datos sucintas como los vectores de bits y los árboles de ondas.
Cálculo eficiente
editarEl conteo de población de un flujo de datos a menudo se necesita en criptografía y otras aplicaciones. La distancia de Hamming de dos palabras A y B se puede calcular como el peso de Hamming de exclusivamente A o B.[4]
El problema de cómo determinarlo de manera eficiente ha sido ampliamente estudiado. Una sola operación para el cálculo, u operaciones paralelas sobre vectores de bits son disponible en algunos procesadores. Para los procesadores que carecen de esas funciones, las mejores soluciones conocidas se basan en agregar cuentas 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 | Binaria | Decimal | Comentario | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
a
|
01 | 10 | 11 | 00 | 10 | 11 | 10 | 10 | El número 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 otro bit de a |
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 a |
c= b0 + b1
|
01 | 01 | 10 | 00 | 01 | 10 | 01 | 01 | 1, 1, 2, 0, 1, 2, 1, 1 | Recuento de unos en cada porción de 2 bits de a |
d0= (c >> 0) & 0011 0011 0011 0011
|
0001 | 0000 | 0010 | 0001 | 1, 0, 2, 1 | Todos los demás contados desde c | ||||
d2= (c >> 2) & 0011 0011 0011 0011
|
0001 | 0010 | 0001 | 0001 | 1, 2, 1, 1 | Los restantes contados desde c | ||||
e= d0 + d2
|
0010 | 0010 | 0011 | 0010 | 2, 2, 3, 2 | Recuento de unos en cada porción de 4 bits de a | ||||
f0= (e >> 0) & 00001111 00001111
|
00000010 | 00000010 | 2, 2 | Todos los demás contados desde e | ||||||
f4= (e >> 4) & 00001111 00001111
|
00000010 | 00000011 | 2, 3 | El resto contados desde e | ||||||
g= f0 + f4
|
00000100 | 00000101 | 4, 5 | Recuento de unos en cada segmento de 8 bits de a | ||||||
h0= (g >> 0) & 0000000011111111
|
0000000000000101 | 5 | Todos los demás contados desde g | |||||||
h8= (g >> 8) & 0000000011111111
|
0000000000000100 | 4 | El resto contados desde g | |||||||
i= h0 + h8
|
0000000000001001 | 9 | Recuento de unos en una palabra completa de 16 bits | |||||||
Aquí, las operaciones son como en lenguaje de programación C, por lo que X >> Y significa desplazar X a la derecha en Y bits, X & 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 proporcionan aquí:[4]
//Tipos de variables y constantes usados en las siguientes funciones
//uint64_t es un tipo de variable entera de 64 bits sin signo (definida en la versión C99 del lenguaje C)
const uint64_t m1= 0x5555555555555555; //binary: 0101...
const uint64_t m2= 0x3333333333333333; //binary: 00110011..
const uint64_t m4= 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
const uint64_t m8= 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...
const uint64_t m16= 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32= 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01= 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
//Esto es un ejemplo simple, que se muestra a modo de comparación,
//y para ayudar a comprender mejor las funciones.
//El algoritmo utiliza 24 operaciones aritméticas (shift, add, and).
int popcount64a(uint64_t x)
{
x= (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits
x= (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits
x= (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits
x= (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits
x= (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
x= (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits
return x;
}
//Este ejemplo usa menos operaciones aritméticas que cualquier otra aplicación
//conocida en máquinas con multiplicación lenta.
//El algoritmo utiliza 17 operaciones aritméticas.
int popcount64b(uint64_t x)
{
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x= (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x= (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
x += x >> 8; //put count of each 16 bits into their lowest 8 bits
x += x >> 16; //put count of each 32 bits into their lowest 8 bits
x += x >> 32; //put count of each 64 bits into their lowest 8 bits
return x & 0x7f;
}
//Este ejemplo usa menos operaciones aritméticas que cualquier otra aplicación
//conocida en máquinas con multiplicación rápida.
//El algoritmo utiliza 12 operaciones aritméticas, una de las cuales es una multiplicación.
int popcount64c(uint64_t x)
{
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x= (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x= (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
return (x * h01) >> 56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
Las aplicaciones 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 Wegner describió en 1960,[14] el operador a nivel de bits de x con x - 1 difiere de x solo en poner a cero el bit distinto de cero menos significativo: restar 1 cambia el bit más a la derecha de la cadena de 0s a 1s, y cambia el 1 más a la derecha a un 0. Si x originalmente tenía n bits que eran 1, entonces después de solo n iteraciones de esta operación, x se reducirá a cero. El siguiente ejemplo se basa en este principio.
//Esta aplicación es mejor cuando la mayoría de los bits en x son 0
//El algoritmo funciona igual para todos los tamaños de datos.
//Usa 3 operaciones aritméticas y 1 comparación/rama por "1" bit en x.
int popcount64d(uint64_t x)
{
int count;
for (count=0; x; count++)
x &= x - 1;
return count;
}
Si se permite un mayor uso de memoria, se puede calcular el peso de Hamming más rápidamente que con los métodos anteriores. Con memoria ilimitada, se podría simplemente crear una gran tabla de búsqueda del peso de Hamming de cada entero de 64 bits. Si se puede almacenar una tabla de búsqueda de la función de Hamming de cada entero de 16 bits, se puede hacer lo siguiente para calcular el peso de Hamming de cada entero de 32 bits.
static uint8_t wordbits[65536]= {/* bitcounts of integers 0 through 65535, inclusive */ };
//Este algoritmo utiliza 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 rellenarse usando esta función
int popcount32e_init(void)
{
uint32_t i;
uint16_t x;
int count;
for (i=0; i <= 0xFFFF; i++)
{
x= i;
for (count=0; x; count++) // borrowed from popcount64d() above
x &= x - 1;
wordbits[i]= count;
}
}
Muła et al.[15] demostraron que una versión vectorizada de popcount64b puede ejecutarse más rápido que las instrucciones dedicadas (por ejemplo, popcnt en los procesadores x64).
Peso mínimo
editarEn código de corrección de errores, el peso de Hamming mínimo, comúnmente denominado peso mínimo wmin 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ódigos de bloque el peso mínimo es también la distancia de Hamming (dmin) y define la capacidad de corrección de errores del código. Si wmin = n, entonces (dmin = n) y el código corregirá hasta (dmin/2) errores.[16]
Lenguajes de programación que disponen de conteo de unos
editar- Algunos compiladores de C proporcionan funciones intrínsecas que brindan funciones de conteo de bits. Por ejemplo, GCC (desde la versión 3.4 en abril de 2004) incluye una función integrada
__builtin_popcountque utilizará una instrucción de procesador si está disponible o una aplicación de biblioteca eficiente en caso contrario.[17] LLVM-GCC ya incluía esta función desde la versión 1.5 en junio de 2005.[18]
- En la Standard Template Library, la estructura de datos de matriz de bits
bitsettiene un métodocount()que cuenta el número de bits que se establecen. En C++20 se agregó un nuevo encabezado<bit>que contiene las funcionesstd::popcountystd::has_single_bit, tomando argumentos de tipos enteros sin signo.
- En Java, la estructura de datos de matriz de bits ampliable BitSet tiene un método BitSet.cardinality() 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 clase de enteros de precisión arbitraria BigInteger también tiene un método BigInteger.bitCount() que cuenta bits.
- En Python, el tipo
inttiene un métodobit_count()para contar el número de bits establecidos. Esta funcionalidad se introdujo en Python 3.10, lanzado en octubre de 2021.[19]
- En Common Lisp, la función
logcount, dado un número entero no negativo, devuelve el número de bits que son 1 (para enteros negativos, devuelve el número de bits que son 0 en notación de complemento a 2). En cualquier caso, el entero puede ser BIGNUM.
- A partir de GHC 7.4, el paquete base Haskell tiene una función
popCountdisponible en todos los tipos que son instancias de la claseBits(disponible en el móduloData.Bits).[20]
- Fortran dispone de la función elemental estándar e intrínseca
popcnt, que devuelve el número de bits distintos de cero dentro de un entero (o matriz de enteros).[22]
- Algunas calculadoras de bolsillo científicas programables cuentan con comandos especiales para calcular el número de bits establecidos, como por ejemplo
#Ben la HP-16C[6][23] y WP 43S,[24][25]#BITS[26][27] oBITSUM[28][29] en emuladores HP-16C ynBITSen WP 34S.[30][31]
- Free Pascal implementa la orden popcnt desde la versión 3.0.[32]
Compatibilidad con procesadores
editar- La computadora IBM 7030 en la década de 1960 calculaba el número de bits establecidos, así como el número de ceros a la izquierda como subproducto de todas las operaciones lógicas.[4]
- Las supercomputadoras Cray Inc. al principio presentaban un recuento de población en código máquina, que se rumoreaba que había sido solicitado específicamente por la Agencia de Seguridad Nacional del gobierno de EE. UU. para las aplicaciones de criptoanálisis.[4]
- Las máquinas de las series 6000 y Cyber 70/170 de Control Data Corporation (CDC) incluían una instrucción de conteo de población; en el modelo COMPASS esta instrucción se codificó como
CXi. - La arquitectura Sun SPARC versión 9 de 64 bits definió una instrucción
POPC,[12][4], pero la mayoría de las sistemas implantados no disponen de ella, lo que requiere que el sistema operativo la emule.[33] - La computadora MMIX de Donald Knuth, diseñada para reemplazar al modelo MIX, se menciona en su libro The Art of Computer Programming que tiene una instrucción
SADDdesde 1999.SADD a,b,ccuenta todos los bits que son 1 en b y 0 en c y escribe el resultado en a. - El Alpha 21264 de Compaq, lanzado en 1999, fue el primer diseño de CPU de la serie Alpha que tenía la extensión de conteo (
CIX). - Los procesadores Blackfin de Analog Devices cuentan con la instrucción
ONESpara realizar un conteo de población de 32 bits.[34] - La arquitectura Barcelona de AMD introdujo la manipulación avanzada de bits (ABM) ISA al incorporar la instrucción
POPCNTcomo parte de las extensiones SSE4 en 2007. - Los procesadores Intel Core introdujeron una instrucción
POPCNTcon la extensión SSE4 del conjunto de instrucciones, disponible por primera vez en un procesador Nehalem basado en el Core i7, lanzado en noviembre de 2008. - La arquitectura ARM introdujo la instrucción
VCNTcomo parte de las extensiones Advanced SIMD (NEON). - La arquitectura RISC-V introdujo la instrucción
PCNTcomo parte de la extensión de manipulación de bits (B).[35]
Véase también
editarReferencias
editar- ↑ [1] Archivado el 30 de septiembre de 2019 en Wayback Machine., written in Fōrmulæ. The Fōrmulæ wiki. Retrieved 2019-09-30.
- ↑ A solution to the task Population count. Retrieved 2019-09-30.
- ↑ Rosetta Code. Retrieved 2019-09-30.
- ↑ a b c d e f g Warren Jr., Henry S. (2013 (1ª Ed 2002)). Hacker's Delight (2 edición). Addison-Wesley - Pearson Education, Inc. pp. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
- ↑ Knuth, Donald Ervin (2009). «Bitwise tricks & techniques; Binary Decision Diagrams». The Art of Computer Programming. 4, Fascicle 1. Addison-Wesley. ISBN 978-0-321-58050-4. (NB. Borrador de Fascículo 1b Archivado el 12 de marzo de 2016 en Wayback Machine. disponible para descargar.)
- ↑ a b Hewlett-Packard HP-16C Computer Scientist Owner's Handbook. Hewlett-Packard. April 1982. 00016-90001. Archivado desde el original el 28 de marzo de 2017. Consultado el 28 de marzo de 2017.
- ↑ Thompson, Thomas M. (1983). From Error-Correcting Codes through Sphere Packings to Simple Groups. The Carus Mathematical Monographs #21. Mathematical Association of America. p. 33.
- ↑ Glaisher, James Whitbread Lee (1899). «On the residue of a binomial-theorem coefficient with respect to a prime modulus». The Quarterly Journal of Pure and Applied Mathematics 30: 150-156. (Nota: véase en particular el último párrafo de la pág. 156.)
- ↑ Reed, Irving Stoy (1954). «A Class of Multiple-Error-Correcting Codes and the Decoding Scheme». Institute of Electrical and Electronics Engineers (Institute of Radio Engineers (IRE)). PGIT-4: 38-49.
- ↑ Cohen, Gérard D.; Lobstein, Antoine; Naccache, David; Zémor, Gilles (1998). «How to improve an exponentiation black-box». En Nyberg, Kaisa, ed. Advances in Cryptology – EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 – June 4, 1998, Proceeding. Lecture Notes in Computer Science 1403. Springer. pp. 211-220. doi:10.1007/BFb0054128.
- ↑ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D. R.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (February 2003). «Chord: a scalable peer-to-peer lookup protocol for internet applications». IEEE/ACM Transactions on Networking 11 (1): 17-32. S2CID 221276912. doi:10.1109/TNET.2002.808407. «Section 6.3: "In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query."».
- ↑ a b SPARC International, Inc. (1992). «A.41: Population Count. Programming Note». The SPARC architecture manual: version 8 (Version 8 edición). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 0-13-825001-4.
- ↑ Blaxell, David (1978). «Record linkage by bit pattern matching». En Hogben, David; Fife, Dennis W., eds. Computer Science and Statistics--Tenth Annual Symposium on the Interface. NBS Special Publication (Departamento de Comercio de los Estados Unidos / Instituto Nacional de Estándares y Tecnología) 503: 146-156.
- ↑ Wegner, Peter (May 1960). «A technique for counting ones in a binary computer». Communications of the ACM 3 (5): 322. S2CID 31683715. doi:10.1145/367236.367286.
- ↑ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (January 2018). «Faster Population Counts Using AVX2 Instructions». Computer Journal 61 (1): 111-120. S2CID 540973. arXiv:1611.07612. doi:10.1093/comjnl/bxx046.
- ↑ Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
- ↑ «GCC 3.4 Release Notes». GNU Project.
- ↑ «LLVM 1.5 Release Notes». LLVM Project.
- ↑ «What's New In Python 3.10». python.org.
- ↑ «GHC 7.4.1 release notes». Documentación de GHC.
- ↑ «Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual».
- ↑ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4.
- ↑ Schwartz, Jake; Grevelle, Rick (2003-10-20 (1ª Ed. 1993)). HP16C Emulator Library for the HP48S/SX. 1.20 (1 edición). Consultado el 15 de agosto de 2015. (Nota: esta biblioteca también funciona en HP48 (066)/GX/G+. Más allá del conjunto de funciones de HP-16C, este paquete también admite cálculos para coma flotante binarios, octales y hexadecimales en notación científica, además de los números decimales de coma flotante habituales.)
- ↑ Bonin, Walter (2019 (1ªEd. 2015)). WP 43S Owner's Manual. 0.12 (draft edición). p. 135. ISBN 978-1-72950098-9. Consultado el 5 de agosto de 2019. [2] [3] (314 páginas)
- ↑ Bonin, Walter (2019 (1ªEd.2015)). WP 43S Reference Manual. 0.12 (draft edición). pp. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Consultado el 5 de agosto de 2019. [4] [5] (271 páginas)
- ↑ Martin, Ángel M.; McClure, Greg J. (5 de septiembre de 2015). «HP16C Emulator Module for the HP-41CX - User's Manual and QRG». Archivado desde el original el 27 de abril de 2017. Consultado el 27 de abril de 2017. (Nota: más allá del conjunto de funciones HP-16C, esta biblioteca personalizada para HP-41 amplía la funcionalidad de la calculadora en unas 50 funciones adicionales.)
- ↑ (076)Martin, Ángel M. (7 de septiembre de 2015). «HP-41: New HP-16C Emulator available». 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). «Ladybug Documentation» (release 0A edición). Consultado el 29 de enero de 2017. [6]
- ↑ «New HP-41 module available: Ladybug». 10 de enero de 2017. Archivado desde el original el 29 de enero de 2017. Consultado el 29 de enero de 2017.
- ↑ Dale, Paul; Bonin, Walter (2012 (1ªEd. 2008)). «WP 34S Owner's Manual» (3.1 edición). Consultado el 27 de abril de 2017.)
- ↑ Bonin, Walter (2015 (1ªEd. 2008)). WP 34S Owner's Manual (3.3 edición). ISBN 978-1-5078-9107-0.
- ↑ «Free Pascal documentation popcnt». Consultado el 7 de diciembre de 2019.
- ↑ «JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h». Java bug database. 30 de enero de 2006.
- ↑ Blackfin Instruction Set Reference (Preliminary edición). Analog Devices. 2001. pp. 8-24. Part Number 82-000410-14.
- ↑ Wolf, Claire (22 de marzo de 2019). «RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37». Github.
Lecturas adicionales
editar- Beeler, Michael; Gosper, Ralph William; Schroeppel, Richard C. (29 de febrero de 1972). HAKMEM (report). Artificial Intelligence Laboratory, Instituto de Tecnología de Massachusetts, Cambridge, Massachusetts, USA. MIT AI Memo 239. (Item 169 Archivado el 8 de noviembre de 2020 en Wayback Machine.: código ensamblado de conteo de población para PDP/6-10).
Enlaces externos
editar- Aggregate Magic Algorithms. Optimized population count and other algorithms explained with sample code.
- Bit Twiddling Hacks Several algorithms with code for counting bits set.
- Necessary and Sufficient Archivado el 23 de septiembre de 2017 en Wayback Machine. - by Damien Wintour - Has code in C# for various Hamming Weight implementations.
- Best algorithm to count the number of set bits in a 32-bit integer? - Stackoverflow
Datos: Q5645805
