Peso de Hamming
# Peso de Hamming

Ejemplos :

| Cadena de caracteres | Peso de Hamming |
| - | - |
| 11101 | 4 |
| 11101000 | 4 |
| 00000000 | 0 |
| 678012340567 | 10 |

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, suma lateral, o suma de bits.

## Historia y uso

La función lleva el nombre de Richard Hamming, aunque él no originó el concepto. 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. Irving Stoy Reed también introdujo en 1954 un concepto equivalente en el caso binario.

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 $log_2$ 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.
* El peso de Hamming determina las longitudes de ruta entre nodos en las tablas del algoritmo Chord.
* 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.
* La operación de peso de Hamming se puede interpretar como una conversión del sistema de numeración unario al sistema binario.
* En el manejo de algunas estructuras de datos sucintas como los vectores de bits y los árboles de ondas.

## Cálculo eficiente

El 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.

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 | Binaria | Binaria | Binaria | Binaria | Binaria | Binaria | 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 | 0001 | 0000 | 0000 | 0010 | 0010 | 0001 | 0001 | 1, 0, 2, 1 | Todos los demás contados desde c |
| d2= (c >> 2) & 0011 0011 0011 0011 | 0001 | 0001 | 0010 | 0010 | 0001 | 0001 | 0001 | 0001 | 1, 2, 1, 1 | Los restantes contados desde c |
| e= d0 + d2 | 0010 | 0010 | 0010 | 0010 | 0011 | 0011 | 0010 | 0010 | 2, 2, 3, 2 | Recuento de unos en cada porción de 4 bits de a |
| f0= (e >> 0) & 00001111 00001111 | 00000010 | 00000010 | 00000010 | 00000010 | 00000010 | 00000010 | 00000010 | 00000010 | 2, 2 | Todos los demás contados desde e |
| f4= (e >> 4) & 00001111 00001111 | 00000010 | 00000010 | 00000010 | 00000010 | 00000011 | 00000011 | 00000011 | 00000011 | 2, 3 | El resto contados desde e |
| g= f0 + f4 | 00000100 | 00000100 | 00000100 | 00000100 | 00000101 | 00000101 | 00000101 | 00000101 | 4, 5 | Recuento de unos en cada segmento de 8 bits de a |
| h0= (g >> 0) & 0000000011111111 | 0000000000000101 | 0000000000000101 | 0000000000000101 | 0000000000000101 | 0000000000000101 | 0000000000000101 | 0000000000000101 | 0000000000000101 | 5 | Todos los demás contados desde g |
| h8= (g >> 8) & 0000000011111111 | 0000000000000100 | 0000000000000100 | 0000000000000100 | 0000000000000100 | 0000000000000100 | 0000000000000100 | 0000000000000100 | 0000000000000100 | 4 | El resto contados desde g |
| i= h0 + h8 | 0000000000001001 | 0000000000001001 | 0000000000001001 | 0000000000001001 | 0000000000001001 | 0000000000001001 | 0000000000001001 | 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í:

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, 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.

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.

Muła et al. 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

En código de corrección de errores, el peso de Hamming mínimo, 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ódigos de bloque el peso mínimo es también la distancia 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.

## Lenguajes de programación que disponen de conteo de unos

* 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_popcount que utilizará una instrucción de procesador si está disponible o una aplicación de biblioteca eficiente en caso contrario. LLVM-GCC ya incluía esta función desde la versión 1.5 en junio de 2005.
* En la Standard Template Library, la estructura de datos de matriz de bits bitset tiene un método count que cuenta el número de bits que se establecen. En C++20 se agregó un nuevo encabezado <bit> que contiene las funciones std::popcount y std::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 int tiene un método bit_count para contar el número de bits establecidos. Esta funcionalidad se introdujo en Python 3.10, lanzado en octubre de 2021.
* 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 popCount disponible en todos los tipos que son instancias de la clase Bits (disponible en el módulo Data.Bits).
* La versión MySQL del lenguaje SQL proporciona BIT_COUNT como una función estándar.
* 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).
* Algunas calculadoras de bolsillo científicas programables cuentan con comandos especiales para calcular el número de bits establecidos, como por ejemplo #B en la HP-16C y WP 43S, #BITS o BITSUM en emuladores HP-16C y nBITS en WP 34S.
* Free Pascal implementa la orden popcnt desde la versión 3.0.

## Compatibilidad con procesadores

* 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.
* 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.
* 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,, pero la mayoría de las sistemas implantados no disponen de ella, lo que requiere que el sistema operativo la emule.
* 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 SADD desde 1999. SADD a,b,c cuenta 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 ONES para realizar un conteo de población de 32 bits.
* La arquitectura Barcelona de AMD introdujo la manipulación avanzada de bits (ABM) ISA al incorporar la instrucción POPCNT como parte de las extensiones SSE4 en 2007.
* Los procesadores Intel Core introdujeron una instrucción POPCNT con 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 VCNT como parte de las extensiones Advanced SIMD (NEON).
* La arquitectura RISC-V introdujo la instrucción PCNT como parte de la extensión de manipulación de bits (B).
