O peso de Hamming de uma cadeia de caracteres (string) é o número de símbolos que são diferentes do símbolo zero do alfabeto utilizado. É, portanto, equivalente à distância de Hamming em relação à cadeia composta apenas por zeros com o mesmo comprimento. Para o caso mais típico, um dado conjunto de bits, este é o número de bits definidos como 1, ou a soma dos dígitos da representação binária de um dado número e a norma (geometria do táxi) de um vetor de bits. Neste caso binário, também é designado por contagem de população (population count), popcount, soma lateral (sideways sum), ou soma de bits (bit summation). +ExemplosCadeia de caracteresPeso de Hamming11101411101000400000000067801234056710 direita|miniaturadaimagem|Um gráfico do peso de Hamming para os números de 0 a 256
História e uso O peso de Hamming recebeu o nome do matemático americano Richard Hamming, embora não tenha sido ele a criar a noção. O peso de Hamming de números binários já era usado em 1899 por James W. L. Glaisher para fornecer uma fórmula para o número de coeficientes binomiais ímpares numa única linha do triângulo de Pascal. Irving S. Reed introduziu um conceito equivalente ao peso de Hamming no caso binário em 1954.
O peso de Hamming é usado em diversas disciplinas, incluindo teoria da informação, teoria de códigos e criptografia. Exemplos de aplicações do peso de Hamming incluem:
Na exponenciação modular por quadratura, o número de multiplicações modulares necessárias para um expoente é . Esta é a razão pela qual o valor da chave pública usado no algoritmo RSA é tipicamente escolhido como um número de baixo peso de Hamming. O peso de Hamming determina os comprimentos dos caminhos entre nós em tabelas de hash distribuídas Chord. As procuras de IrisCode em bases de dados biométricas são tipicamente implementadas através do cálculo da distância de Hamming em relação a cada registo armazenado. Em programas de xadrez computacional que usam uma representação por bitboard, o peso de Hamming de um bitboard fornece o número de peças de um dado tipo que restam no jogo, ou o número de casas do tabuleiro controladas pelas peças de um jogador, sendo, por isso, um termo importante que contribui para a avaliação de uma posição. Atualizado e reimpresso em Scalable Search in Computer Chess (Vieweg+Teubner Verlag, 2000), pp. 185–198, O peso de Hamming pode ser usado para calcular eficientemente o find first set (encontrar o primeiro conjunto) usando a identidade . Isto é útil em plataformas como SPARC, que possuem instruções em hardware para o peso de Hamming, mas não instruções de hardware para find first set. A operação do peso de Hamming pode ser interpretada como uma conversão do sistema de numeração unário para números binários.
Implementação eficiente A contagem da população de uma cadeia de bits é frequentemente necessária na criptografia e noutras aplicações. A distância de Hamming de duas palavras e pode ser calculada como o peso de Hamming de (XOR lógico).
O problema de como implementá-lo de forma eficiente tem sido amplamente estudado. Uma única operação para o cálculo, ou operações paralelas em vetores de bits, estão disponíveis em alguns processadores. Para processadores desprovidos dessas características, as melhores soluções conhecidas são baseadas na soma das contagens usando um padrão em árvore. Por exemplo, para contar o número de bits 1 no número binário de 16 bits a = 0110 1100 1011 1010, estas operações podem ser efetuadas: ExpressãoBinárioDecimalComentárioa01101100101110 style="text-align:left;" O número originalb0 = (a >> 0) & 01 01 01 01 01 01 01 0101000100000100001, 0, 1, 0, 0, 1, 0, 0Bits alternados a partir de ab1 = (a >> 1) & 01 01 01 01 01 01 01 0100010100010101010, 1, 1, 0, 1, 1, 1, 1Os restantes bits a partir de ac = b0 + b101011000011001011, 1, 2, 0, 1, 2, 1, 1Contagem de 1s em cada fatia de 2 bits de ad0 = (c >> 0) & 0011 0011 0011 001100010000001000011, 0, 2, 1Contagens alternadas a partir de cd2 = (c >> 2) & 0011 0011 0011 001100010010000100011, 2, 1, 1As restantes contagens a partir de ce = d0 + d200100010001100102, 2, 3, 2Contagem de 1s em cada fatia de 4 bits de af0 = (e >> 0) & 00001111 0000111100000010000000102, 2Contagens alternadas a partir de ef4 = (e >> 4) & 00001111 0000111100000010000000112, 3As restantes contagens a partir de eg = f0 + f400000100000001014, 5Contagem de 1s em cada fatia de 8 bits de ah0 = (g >> 0) & 000000001111111100000000000001015Contagens alternadas a partir de gh8 = (g >> 8) & 000000001111111100000000000001004As restantes contagens a partir de gi = h0 + h800000000000010019Contagem de 1s em toda a palavra de 16 bits Aqui, as operações ocorrem como na linguagem de programação C, portanto X >> Y significa deslocar X para a direita em Y bits, X & Y significa o AND bit a bit (bit-a-bit) de X e Y, e o + é a adição comum. Os melhores algoritmos conhecidos para este problema baseiam-se no conceito ilustrado acima e são apresentados a seguir://Tipos e constantes utilizados nas funções abaixo //uint64_t é um tipo de variável inteira sem sinal de 64 bits (definida na versão C99 da linguagem C) const uint64_t m1 = 0x5555555555555555; //binário: 0101... const uint64_t m2 = 0x3333333333333333; //binário: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //binário: 4 zeros, 4 uns ... const uint64_t m8 = 0x00ff00ff00ff00ff; //binário: 8 zeros, 8 uns ... const uint64_t m16 = 0x0000ffff0000ffff; //binário: 16 zeros, 16 uns ... const uint64_t m32 = 0x00000000ffffffff; //binário: 32 zeros, 32 uns const uint64_t h01 = 0x0101010101010101; //a soma de 256 à potência de 0,1,2,3...
//Esta é uma implementação ingénua, apresentada para comparação, //e para ajudar a compreender as funções mais elaboradas. //Este algoritmo utiliza 24 operações aritméticas (deslocamento, soma, e lógico AND). int popcount64a(uint64_t x) { x = (x & m1 ) + ((x >> 1) & m1 ); //coloca a contagem de cada 2 bits nesses 2 bits x = (x & m2 ) + ((x >> 2) & m2 ); //coloca a contagem de cada 4 bits nesses 4 bits x = (x & m4 ) + ((x >> 4) & m4 ); //coloca a contagem de cada 8 bits nesses 8 bits x = (x & m8 ) + ((x >> 8) & m8 ); //coloca a contagem de cada 16 bits nesses 16 bits x = (x & m16) + ((x >> 16) & m16); //coloca a contagem de cada 32 bits nesses 32 bits x = (x & m32) + ((x >> 32) & m32); //coloca a contagem de cada 64 bits nesses 64 bits return x; }
//Utiliza menos operações aritméticas do que qualquer outra implementação //conhecida em máquinas com multiplicação lenta. //Este algoritmo utiliza 17 operações aritméticas. int popcount64b(uint64_t x) { x -= (x >> 1) & m1; //coloca a contagem de cada 2 bits nesses 2 bits x = (x & m2) + ((x >> 2) & m2); //coloca a contagem de cada 4 bits nesses 4 bits x = (x + (x >> 4)) & m4; //coloca a contagem de cada 8 bits nesses 8 bits x += x >> 8; //coloca a contagem de cada 16 bits nos seus 8 bits mais baixos x += x >> 16; //coloca a contagem de cada 32 bits nos seus 8 bits mais baixos x += x >> 32; //coloca a contagem de cada 64 bits nos seus 8 bits mais baixos return x & 0x7f; }
//Utiliza menos operações aritméticas do que qualquer outra implementação //conhecida em máquinas com multiplicação rápida. //Este algoritmo utiliza 12 operações aritméticas, sendo uma delas a multiplicação. int popcount64c(uint64_t x) { x -= (x >> 1) & m1; //coloca a contagem de cada 2 bits nesses 2 bits x = (x & m2) + ((x >> 2) & m2); //coloca a contagem de cada 4 bits nesses 4 bits x = (x + (x >> 4)) & m4; //coloca a contagem de cada 8 bits nesses 8 bits return (x * h01) >> 56; //devolve os 8 bits esquerdos de x + (x<<8) + (x<<16) + (x<<24) + ... }As implementações referidas acima apresentam o melhor comportamento no pior caso em comparação a qualquer algoritmo conhecido. No entanto, quando se espera que um valor tenha poucos bits não nulos, pode ser mais eficiente usar algoritmos que contem estes bits um de cada vez. Como Wegner descreveu em 1960, o AND bit a bit de com difere de apenas por zerar o bit não nulo menos significativo: subtrair 1 altera a cadeia de 0s mais à direita para 1s e altera o 1 mais à direita para um 0. Se originalmente tinha bits iguais a 1, após exatamente iterações desta operação, será reduzido a zero. A seguinte implementação baseia-se neste princípio.//Isto é melhor quando a maioria dos bits em x é 0 //Este algoritmo funciona da mesma forma para todos os tamanhos de dados. //Utiliza 3 operações aritméticas e 1 comparação/ramificação por cada bit "1" em x. int popcount64d(uint64_t x) { int count; for (count=0; x; count++) x &= x - 1; return count; }De interesse aqui é a ligação íntima entre Popcount, FFS e CLZ (contagem de zeros à esquerda).
Se for permitido um maior uso de memória, é possível calcular o peso de Hamming mais rapidamente do que com os métodos acima. Com memória ilimitada, poder-se-ia criar simplesmente uma enorme tabela de pesquisa (lookup table) do peso de Hamming de todos os inteiros de 64 bits. Se conseguirmos armazenar uma tabela de pesquisa da função de Hamming de cada inteiro de 16 bits, podemos fazer o seguinte para computar o peso de Hamming de todos os inteiros de 32 bits.static uint8_t wordbits[65536] = { /* contagem de bits de inteiros de 0 a 65535, inclusive */ }; //Este algoritmo usa 3 operações aritméticas e 2 leituras de memória. int popcount32e(uint32_t x) { return wordbits[x & 0xFFFF] + wordbits[x >> 16]; }//Opcionalmente, a tabela wordbits[] pode ser preenchida através desta função 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++) // retirado do popcount64d() acima x &= x - 1; wordbits[i] = count;
}Um algoritmo recursivo é descrito em Donovan & Kernighan:/* O peso de i pode diferir do peso de i / 2 apenas no 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. mostraram que uma versão vetorizada de `popcount64b` pode ser executada mais rapidamente do que instruções dedicadas (por exemplo, `popcnt` em processadores x64).
O algoritmo de Harley–Seal é um dos mais rápidos que também necessita apenas de operações de números inteiros.
Peso mínimo Na codificação de correção de erros, o peso de Hamming mínimo, habitualmente referido como o peso mínimo de um código, é o peso da palavra de código não nula de menor peso. O peso de uma palavra de código é o número de 1s na palavra. Por exemplo, a palavra 11001010 tem um peso de 4.
Num código de bloco linear, o peso mínimo é também a distância de Hamming mínima () e define a capacidade de correção de erros do código. Se , então e o código corrigirá até erros.Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
Suporte em linguagens Alguns compiladores C fornecem funções intrínsecas que disponibilizam facilidades de contagem de bits. Por exemplo, o GCC (desde a versão 3.4 em abril de 2004) inclui uma função nativa __builtin_popcount que usará uma instrução do processador, caso esteja disponível, ou uma implementação de biblioteca eficiente na sua ausência. O LLVM-GCC também inclui esta função desde a versão 1.5 em junho de 2005.
Na Biblioteca Padrão do C++, a estrutura de dados de matriz de bits bitset tem um método count() que conta o número de bits que estão definidos como um. Em C++20, foi adicionado um novo cabeçalho <bit>, que contém as funções std::popcount e std::has_single_bit, e que aceitam argumentos de tipos inteiros sem sinal.
Em Java, a estrutura de matriz de bits escalável tem um método que conta o número de bits definidos. Adicionalmente, existem as funções e para contar bits em números inteiros primitivos de 32 e 64 bits, respetivamente. A classe de inteiros de precisão arbitrária também tem um método que efetua a contagem de bits.