Peso de Hamming

El peso de Hamming de una cadena es el número de símbolos que difieren del símbolo cero del alfabeto utilizado. Por lo tanto, es equivalente a la distancia de Hamming con respecto a la cadena compuesta únicamente por ceros de la misma longitud. Para el caso más típico, dado un conjunto de bits , este es el número de bits establecidos a 1, o la suma de los 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 denomina recuento de población , ^{[ 1 ]} popcount , suma lateral , ^{[ 2 ]} o suma de bits . ^{[ 3 ]}

El peso de Hamming recibe su nombre del matemático estadounidense Richard Hamming , aunque él no fue quien originó el concepto. ^{[ 5 ]} 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 . ^{[ 6 ]} Irving S. Reed introdujo un concepto, equivalente al peso de Hamming en el caso binario, en 1954. ^{[ 7 ]}

El peso de Hamming se utiliza en varias disciplinas, incluyendo la teoría de la información , la teoría de la codificación y la criptografía . Algunos ejemplos de aplicaciones del peso de Hamming son:

• En la exponenciación modular por elevación al cuadrado , el número de multiplicaciones modulares necesarias para un exponente e es log₂ _e + peso( e ). Por esta razón, el valor de clave pública e utilizado en RSA se suele elegir como un número de bajo peso de Hamming. ^{[ 8 ]}
• El peso de Hamming determina las longitudes de ruta entre nodos en tablas hash distribuidas de Chord . ^{[ 9 ]}
• Las búsquedas de IrisCode en bases de datos biométricas se implementan típicamente calculando la distancia de Hamming a cada registro almacenado. ^{[ 10 ]}
• En los programas de ajedrez por computadora que utilizan una representación de tablero de bits , el peso de Hamming de un tablero de bits indica la cantidad de piezas de un tipo dado que quedan en la partida, o la cantidad de casillas del tablero controladas por las piezas de un jugador, y por lo tanto es un término importante que contribuye al valor de una posición. ^{[ 11 ]}
• El peso de Hamming se puede utilizar para calcular eficientemente el primer conjunto mediante la identidad ffs(x) = pop(x ^ (x - 1)). Esto es útil en plataformas como SPARC que tienen instrucciones de hardware para el peso de Hamming pero no para encontrar el primer conjunto. ^{[ 12 ] [ 1 ]}
• La operación de peso de Hamming puede interpretarse como una conversión del sistema numérico unario a números binarios . ^{[ 13 ]}

El recuento de población de una cadena de bits se necesita con frecuencia 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 A xor B. ^{[ 1} ]

El problema de cómo implementarlo de manera eficiente ha sido ampliamente estudiado. Algunos procesadores disponen de una única operación para el cálculo, o de operaciones paralelas sobre vectores de bits . Para los procesadores que carecen de estas características, las mejores soluciones conocidas se basan en la suma de conteos en un patrón de árbol. Por ejemplo, para contar el número de bits 1 en el número binario de 16 bits a  =  0110  1100  1011  1010, se pueden realizar las siguientes operaciones:

Aquí, las operaciones son como en el lenguaje de programación C , por lo que X >> Ysignifica desplazar X a la derecha Y bits, X & Y significa la operación AND bit a bit de X e Y, y + es la suma ordinaria. Los mejores algoritmos conocidos para este problema se basan en el concepto ilustrado anteriormente y se presentan aquí: ^{[ 1 ]}

//tipos y constantes utilizados en las funciones siguientes //uint64_t es un tipo de variable entera sin signo de 64 bits (definida 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 elevado 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 utiliza 24 operaciones aritméticas (desplazamiento, suma y AND). int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); //coloca el conteo de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //coloca el conteo de cada 4 bits en esos 4 bits x = ( x & m4 ) + (( x >> 4 ) & m4 ); //coloca el conteo de cada 8 bits en esos 8 bits x = ( x & m8 ) + (( x >> 8 ) & m8 ); //coloca el conteo 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 ); //Coloca el recuento de cada 64 bits en esos 64 bits return x ; }//Este algoritmo utiliza 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 ; //Coloca el conteo de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //Coloca el conteo de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; //Coloca el conteo de cada 8 bits en esos 8 bits x += x >> 8 ; //Coloca el conteo de cada 16 bits en sus 8 bits menos significativos x += x >> 16 ; //Coloca el conteo de cada 32 bits en sus 8 bits menos significativos x += x >> 32 ; //Coloca el conteo de cada 64 bits en sus 8 bits menos significativos return x & 0x7f ; }//Este algoritmo utiliza 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 ; //coloca el conteo de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //coloca el conteo de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; //coloca el conteo de cada 8 bits en esos 8 bits return ( x * h01 ) >> 56 ; //devuelve los 8 bits izquierdos 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 usar algoritmos que cuenten estos bits uno por uno. Como describió Wegner en 1960, ^{[ 14 ]} la operación AND bit a bit de x con x − 1 difiere de x solo en que anula el bit distinto de cero menos significativo: restar 1 cambia la cadena de 0s 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, entonces después 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 utiliza 3 operaciones aritméticas y 1 comparación/salto por cada bit "1" en x. int popcount64d ( uint64_t x ) { int count ; for ( count = 0 ; x ; count ++ ) x &= x - 1 ; return count ; }

Resulta interesante observar la estrecha relación entre Popcount, FFS y CLZ.

Si se permite un mayor uso de memoria, podemos calcular el peso de Hamming más rápido que con los métodos anteriores. Con memoria ilimitada, podríamos simplemente crear una tabla de búsqueda grande del peso de Hamming para cada entero de 64 bits. Si podemos almacenar una tabla de búsqueda de la función de Hamming para cada entero de 16 bits, podemos hacer lo siguiente para calcular el peso de Hamming para cada entero de 32 bits.

static uint8_t wordbits [ 65536 ] = { /* recuento de bits de los enteros del 0 al 65535, ambos 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 llenarse 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 ++ ) // tomado de popcount64d() anterior x &= x - 1 ; wordbits [ i ] = count ; } }

^{En Donovan y Kernighan [ 15 ]} se presenta un algoritmo recursivo.

/* El peso de i puede diferir del peso de i / 2 solo en el bit menos significativo de i */ int popcount32e_init ( void ) { int i ; for ( i = 1 ; sizeof wordbits / sizeof * wordbits > i ; ++ i ) wordbits [ i ] = wordbits [ i >> 1 ] + ( 1 & i ); }

Muła et al. ^{[ 16 ]} 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).

El algoritmo Harley-Seal ^{[ 17 ]} es uno de los más rápidos que además solo necesita operaciones con números enteros. ^{[ 18 ]}

En la codificación de 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 con el peso más bajo. El peso w de una palabra de código es el número de unos que contiene. Por ejemplo, la palabra 11001010 tiene un peso de 4.

En un código de bloques lineal, el peso mínimo es también la distancia de Hamming mínima ( d _min ) y define la capacidad de corrección de errores del código. Si w _min  = n , entonces d _min = n y el código corregirá hasta d _min /2 errores. ^{[ 19 ]}   

Algunos compiladores de C proporcionan funciones intrínsecas que ofrecen facilidades para el 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 del procesador si está disponible o una implementación de biblioteca eficiente en caso contrario. ^{[ 20 ]} LLVM-GCC ha incluido esta función desde la versión 1.5 en junio de 2005. ^{[ 21 ]}

En la biblioteca estándar de C++ , la estructura de datos de matriz de bits bitsettiene un count()método que cuenta el número de bits que están activados. En C++20<bit> , se agregó un nuevo encabezado que contiene las funciones std::popcounty std::has_single_bit, que aceptan argumentos de tipo entero sin signo.

En Java, la estructura de datos de matriz de bits de tamaño variable BitSettiene un BitSet.cardinality()método que cuenta la cantidad de bits activados. Además, existen Integer.bitCount(int)funciones Long.bitCount(long)para contar bits en enteros primitivos de 32 y 64 bits, respectivamente. Asimismo, la BigIntegerclase de enteros de precisión arbitraria también tiene un BigInteger.bitCount()método para contar bits.

En Python , el inttipo tiene un bit_count()método para contar el número de bits activados. Esta funcionalidad se introdujo en Python 3.10, lanzado en octubre de 2021. ^{[ 22 ]}

En Common Lisp , la función logcount, dado un entero no negativo, devuelve el número de bits 1. (Para enteros negativos, devuelve el número de bits 0 en notación de complemento a dos). En cualquier caso, el entero puede ser un bignum .

A partir de GHC 7.4, el paquete base de Haskell tiene una popCountfunción disponible en todos los tipos que son instancias de la Bitsclase (disponible desde el Data.Bitsmódulo). ^{[ 23 ]}

La versión MySQL del lenguaje SQL proporciona BIT_COUNT()como función estándar. ^{[ 24 ]}

Fortran 2008 tiene la función elemental estándar e intrínseca popcntque devuelve el número de bits distintos de cero dentro de un entero (o matriz de enteros). ^{[ 25 ]}

Algunas calculadoras científicas de bolsillo programables incluyen comandos especiales para calcular el número de bits activados, por ejemplo, #Ben la HP-16C . ^{[ 3 ]}

FreePascal implementa popcnt desde la versión 3.0. ^{[ 26 ]}

• La computadora IBM STRETCH de la década de 1960 calculaba el número de bits activados, así como el número de ceros iniciales, como un subproducto de todas las operaciones lógicas. ^{[ 1 ]}
• Las supercomputadoras Cray incluían desde sus inicios una instrucción de máquina de conteo de población , que, según se rumorea, fue solicitada específicamente por la Agencia de Seguridad Nacional del gobierno estadounidense para aplicaciones de criptoanálisis . ^{[ 1 ]}
• 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 COMPASS , esta instrucción estaba codificada como CXi.
• La arquitectura SPARC versión 9 de 64 bits define una POPCinstrucción, ^{[ 12 ] [ 1 ]} pero la mayoría de las implementaciones no la implementan, lo que requiere que sea emulada por el sistema operativo. ^{[ 27 ]}
• El modelo de computadora MMIX de Donald Knuth , que va a reemplazar a MIX en su libro El arte de la programación de computadoras, tiene una SADDinstrucción desde 1999 SADD a,b,cque cuenta todos los bits que son 1 en b y 0 en c y escribe el resultado en a.
• El Alpha 21264A 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 incluyen la ONESinstrucción para realizar un conteo de población de 32 bits. ^{[ 28 ]}
• La arquitectura Barcelona de AMD introdujo el conjunto de instrucciones de manipulación avanzada de bits (ABM, por sus siglas en inglés), incorporando la POPCNTinstrucción como parte de las extensiones SSE4a en 2007.
• Los procesadores Intel Core introdujeron una POPCNTinstrucció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 esta VCNTinstrucción como parte de las extensiones Advanced SIMD ( NEON ).
• La arquitectura RISC-V introdujo la CPOPinstrucción como parte de la extensión de manipulación de bits (B). ^{[ 29 ]}

• Complemento de dos
• Abróchate

• Schroeppel, Richard C.; Orman, Hilarie K. (29 de febrero de 1972). "Compilación". HAKMEM . Por Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (informe). Laboratorio de Inteligencia Artificial , Instituto Tecnológico de Massachusetts , Cambridge, Massachusetts, EE. UU. MIT AI Memo 239.( Elemento 169 : Código de ensamblaje de recuento de población para el PDP/6-10.)

• Algoritmos mágicos agregados . Conteo de población optimizado y otros algoritmos explicados con código de ejemplo.
• Trucos de manipulación de bits Varios algoritmos con código para contar los bits activados.
• Necesario y suficiente Archivado el 23/09/2017 en Wayback Machine - por Damien Wintour - Contiene código en C# para varias implementaciones del peso de Hamming.
• ¿Cuál es el mejor algoritmo para contar el número de bits activados en un entero de 32 bits? - Stackoverflow