El peso de Hamming de una cadena 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 cadena compuesta por todos los ceros de la misma longitud. Para el caso más típico, una cadena de bits , este es el número de 1 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 denomina recuento de población , [1] recuento de población , suma lateral , [2] o suma de bits . [3]
El peso de Hamming debe su nombre al matemático estadounidense Richard Hamming , aunque no fue él quien originó la noción. [5] 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 . [6] Irving S. Reed introdujo un concepto, equivalente al peso de Hamming en el caso binario, en 1954. [7]
La ponderación de Hamming se utiliza en varias disciplinas, entre ellas, la teoría de la información , la teoría de la codificación y la criptografía . Entre los ejemplos de aplicaciones de la ponderación de Hamming se 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 xor B. [1]
El problema de cómo implementarlo de manera eficiente ha sido ampliamente estudiado. En algunos procesadores se dispone de una única operación para el cálculo, o de operaciones paralelas sobre vectores de bits. Para los procesadores que carecen de esas características, las mejores soluciones conocidas se basan en sumar 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 estas operaciones:
Aquí, las operaciones son como en el lenguaje de programación C , es X >> Ydecir, desplazar X a la derecha en Y bits, X e Y significa el 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 dan aquí: [1]
//tipos y constantes utilizados en las funciones siguientes //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 ; //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, que se muestra para comparar, //y para ayudar a comprender las mejores funciones. //Este algoritmo usa 24 operaciones aritméticas (desplazar, sumar y). int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); //poner el conteo de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //poner el conteo de cada 4 bits en esos 4 bits x = ( x & m4 ) + (( x >> 4 ) & m4 ); //poner el conteo de cada 8 bits en esos 8 bits x = ( x & m8 ) + (( x >> 8 ) & m8 ); //poner el conteo 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 conteo de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //poner el conteo de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; //poner el conteo de cada 8 bits en esos 8 bits x += x >> 8 ; //poner el conteo de cada 16 bits en sus 8 bits más bajos x += x >> 16 ; //poner el conteo de cada 32 bits en sus 8 bits más bajos x += x >> 32 ; //poner el conteo 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 ; //pone el conteo de cada 2 bits en esos 2 bits x = ( x & m2 ) + (( x >> 2 ) & m2 ); //pone el conteo de cada 4 bits en esos 4 bits x = ( x + ( x >> 4 )) & m4 ; //pone el conteo 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 describió Wegner en 1960, [12] el AND bit a bit de x con x − 1 difiere de x solo en que pone a cero el bit menos significativo distinto de cero: restar 1 cambia la cadena de 0 más a la derecha a 1, y cambia el 1 más a la derecha a 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 de la misma manera para todos los tamaños de datos. //Este algoritmo utiliza 3 operaciones aritméticas y 1 comparación/rama por cada bit "1" 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 la memoria, podemos calcular el peso de Hamming más rápido que con los métodos anteriores. Con una memoria ilimitada, podríamos simplemente crear una gran tabla de búsqueda del peso de Hamming de cada entero de 64 bits. Si podemos almacenar una tabla de búsqueda de la función de Hamming de cada entero de 16 bits, podemos hacer lo siguiente para calcular el peso de Hamming de cada entero de 32 bits.
static uint8_t wordbits [ 65536 ] = { /* recuento de bits de los 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 ) { return wordbits [ x & 0xFFFF ] + wordbits [ x >> 16 ]; } //Opcionalmente, la tabla wordbits[] se puede llenar 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 ; } } Muła et al. [13] 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).
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 con el peso más bajo. El peso w de una palabra de código es la cantidad de 1 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. [14]
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_popcountque utilizará una instrucción de procesador si está disponible o una implementación de biblioteca eficiente en caso contrario. [15] LLVM-GCC ha incluido esta función desde la versión 1.5 en junio de 2005. [16]
En la biblioteca estándar de C++ , la estructura de datos de matriz de bits bitsettiene un count()método que cuenta la cantidad de bits que se establecen. En C++20<bit> , se agregó un nuevo encabezado que contiene funciones std::popcounty std::has_single_bitque toman 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 establecen. Además, existen funciones Integer.bitCount(int)y Long.bitCount(long)para contar bits en números enteros primitivos de 32 y 64 bits, respectivamente. Asimismo, la BigIntegerclase de números enteros 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 la cantidad de bits establecidos. Esta funcionalidad se introdujo en Python 3.10, publicado en octubre de 2021. [17]
En Common Lisp , la función logcount, dado un entero no negativo, devuelve la cantidad de bits 1. (Para enteros negativos, devuelve la cantidad de bits 0 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 HaskellpopCount tiene una función disponible en todos los tipos que son instancias de la Bitsclase (disponible desde el Data.Bitsmódulo). [18]
La versión MySQL del lenguaje SQLBIT_COUNT() se proporciona como función estándar. [19]
Fortran 2008 tiene la función elemental intrínseca estándar popcntque devuelve la cantidad de bits distintos de cero dentro de un entero (o matriz de enteros). [20]
Algunas calculadoras científicas de bolsillo programables cuentan con comandos especiales para calcular el número de bits establecidos, por ejemplo, #Ben la HP-16C [3] [21] y la WP 43S , [22] [23] #BITS[24] [25] o BITSUM[26] [27] en los emuladores HP-16C, y nBITSen la WP 34S . [28] [29]
FreePascal implementa popcnt desde la versión 3.0. [30]
CXi.POPCinstrucción, [10] [1] pero la mayoría de las implementaciones no la implementan, requiriendo que sea emulada por el sistema operativo. [31]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).ONESinstrucción para realizar un recuento de población de 32 bits. [32]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 SIMD Avanzado ( NEON ).CPOP introdujo la instrucción como parte de la extensión de manipulación de bits (B). [33]Sección 6.3: "En general, la cantidad de dedos que necesitamos seguir será la cantidad de unos en la representación binaria de la distancia desde el nodo hasta la consulta".