El peso Hamming de una cadena es el número de símbolos que son diferentes del símbolo cero del alfabeto utilizado. Por tanto, es equivalente a la distancia de Hamming desde la cuerda totalmente cero 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 le llama recuento de población , [1] popcount , suma lateral , [2] o suma de bits . [3]
El peso Hamming lleva el nombre de Richard Hamming , aunque no fue él quien originó la idea. [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 de Hamming se utiliza en varias disciplinas, incluidas 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:
El recuento de población de una cadena de bits suele ser necesario 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 x o B. [1]
El problema de cómo implementarlo eficientemente ha sido ampliamente estudiado. En algunos procesadores está disponible 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 bits 1 en el número binario de 16 bits a = 0110 1100 1011 1010, se pueden realizar estas operaciones:
Aquí, las operaciones son como en el lenguaje de programación C , por lo que X >> Ysignifica desplazar X hacia 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 detallan aquí: [1]
//tipos y constantes utilizados en las funciones siguientes //uint64_t es un tipo de variable entero 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 elevado a 0,1,2,3... //Esta es una implementación ingenua, que se muestra para comparar //y para ayudar a comprender las mejores funciones. //Este algoritmo utiliza 24 operaciones aritméticas (desplazar, sumar 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 ); //poner el recuento de cada 4 bits en esos 4 bits x = ( x & m4 ) + (( x >> 4 ) & m4 ); //poner el recuento de cada 8 bits en esos 8 bits x = ( x & m8 ) + (( x >> 8 ) & m8 ); //poner el recuento de cada 16 bits en esos 16 bits x = ( x & m16 ) + (( x >> 16 ) & m16 ); //poner 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 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 ; //poner el recuento de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //poner el recuento de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; //poner el recuento de cada 8 bits en esos 8 bits x += x >> 8 ; //poner el recuento de cada 16 bits en sus 8 bits más bajos x += x >> 16 ; //poner el recuento de cada 32 bits en sus 8 bits más bajos x += x >> 32 ; //poner el recuento de cada 64 bits en sus 8 bits más bajos return x & 0x7f ; } //Esto 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 ; //poner el recuento de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //poner el recuento de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; //poner el recuento de cada 8 bits en esos 8 bits return ( x * h01 ) >> 56 ; //devuelve los 8 bits restantes 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 uno a la vez. Como Wegner describió en 1960, [14] el AND bit a bit de x con x − 1 difiere de x solo en poner a cero el bit distinto de cero menos significativo: restar 1 cambia la cadena de ceros más a la derecha a 1, 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 sólo 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/ramificación por "1" bit en x. int popcount64d ( uint64_t x ) { int recuento ; para ( cuenta = 0 ; x ; cuenta ++ ) x &= x - 1 ; recuento de retornos ; } 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 tabla de búsqueda grande 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 ] = { /* recuentos de bits de números enteros del 0 al 65535, inclusive */ }; //Este algoritmo utiliza 3 operaciones aritméticas y 2 lecturas de memoria. int popcount32e ( uint32_t x ) { devolver bits de palabras [ x & 0xFFFF ] + bits de palabras [ x >> 16 ]; } //Opcionalmente, la tabla wordbits[] podría completarse usando esta función int popcount32e_init ( void ) { uint32_t i ; uint16_tx ; _ recuento int ; para ( yo = 0 ; yo <= 0xFFFF ; yo ++ ) { x = yo ; for ( count = 0 ; x ; count ++ ) // tomado de popcount64d() arriba x &= x - 1 ; bits de palabras [ i ] = contar ; } } Muła et al. [15] han demostrado que una versión vectorizada de popcount64b puede ejecutarse más rápido que instrucciones dedicadas (por ejemplo, popcnt en procesadores x64).
En la codificación de corrección de errores , el peso mínimo de Hamming, comúnmente conocido como 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 = n y el código corregirá hasta d min /2 errores. [dieciséis]
Algunos compiladores de C proporcionan funciones intrínsecas que proporcionan funciones de recuento de bits. Por ejemplo, GCC (desde la versión 3.4 en abril de 2004) incluye una función incorporada __builtin_popcountque utilizará una instrucción de procesador si está disponible o una implementación de biblioteca eficiente en caso contrario. [17] LLVM-GCC ha incluido esta función desde la versión 1.5 en junio de 2005. [18]
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 configurados. En C++20<bit> , se agregó un nuevo encabezado que contiene funciones std::popcounty std::has_single_bit, tomando argumentos de tipos enteros sin signo.
En Java, la estructura de datos de matriz de bits ampliable BitSettiene un BitSet.cardinality()método que cuenta la cantidad de bits que se configuran. Además, existen Integer.bitCount(int)funciones Long.bitCount(long)para contar bits en enteros primitivos de 32 y 64 bits, respectivamente. Además, la BigIntegerclase entera de precisión arbitraria también tiene un BigInteger.bitCount()método que cuenta bits.
En Python , el inttipo tiene un bit_count()método 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 1 bits. (Para números enteros negativos, devuelve el número de bits 0 en notación en complemento a 2). En cualquier caso, el número entero puede ser BIGNUM.
A partir de GHC 7.4, el paquete base de HaskellpopCount tiene una función disponible en todos los tipos que son instancias de la Bitsclase (disponible en el Data.Bitsmódulo). [20]
La versión MySQL del lenguaje SQLBIT_COUNT() proporciona una función estándar. [21]
Fortran 2008 tiene la función elemental intrínseca estándar popcntque devuelve el número de bits distintos de cero dentro de un número entero (o matriz de enteros). [22]
Algunas calculadoras científicas de bolsillo programables cuentan con comandos especiales para calcular el número de bits configurados, por ejemplo, #Ben HP-16C [3] [23] y WP 43S , [24] [25] #BITS[26] [27] o BITSUM[28] [29 ] en emuladores HP-16C y nBITSen WP 34S . [30] [31]
FreePascal implementa popcnt desde la versión 3.0. [32]
CXi.POPCinstrucción, [12] [1] pero la mayoría de las implementaciones no la implementan, lo que requiere que el sistema operativo la emule. [33]SADDinstrucción desde 1999. SADD a,b,ccuenta todos los bits que son 1 en b y 0 en c y escribe el resultado en a.CIX).ONESinstrucciones para realizar un recuento de población de 32 bits. [34]POPCNTinstrucción como parte de las extensiones SSE4a en 2007.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.VCNTinstrucción como parte de las extensiones Advanced SIMD ( NEON ).CPOP introdujo la instrucción como parte de la extensión Bit Manipulation (B). [35]Sección 6.3: "En general, la cantidad de dedos que debemos seguir será la cantidad de unos en la representación binaria de la distancia desde el nodo hasta la consulta".