Peso de Hamming 📖 Wikipedia

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 ${\displaystyle \ell _{1}}$ (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).^[1][2][3]

O peso de Hamming recebeu o nome do matemático americano Richard Hamming, embora não tenha sido ele a criar a noção.^[5] 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.^[6] Irving S. Reed introduziu um conceito equivalente ao peso de Hamming no caso binário em 1954.^[7]

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 ${\displaystyle e}$ é ${\displaystyle \log _{2}e+{\text{weight}}(e)}$. Esta é a razão pela qual o valor da chave pública ${\displaystyle e}$ usado no algoritmo RSA é tipicamente escolhido como um número de baixo peso de Hamming.^[8]
• O peso de Hamming determina os comprimentos dos caminhos entre nós em tabelas de hash distribuídas Chord.^[9]
• 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.^[10]
• 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.^[11]
• O peso de Hamming pode ser usado para calcular eficientemente o find first set (encontrar o primeiro conjunto) usando a identidade ${\displaystyle {\text{ffs}}(x)={\text{pop}}(x\oplus (x-1))}$. 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.^[12][1]
• 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.^[13]

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 ${\displaystyle A}$ e ${\displaystyle B}$ pode ser calculada como o peso de Hamming de ${\displaystyle A\oplus B}$ (XOR lógico).^[1]

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:

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:^[1]

//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,^[14] o AND bit a bit de ${\displaystyle x}$ com ${\displaystyle x-1}$ difere de ${\displaystyle x}$ 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 ${\displaystyle x}$ originalmente tinha ${\displaystyle n}$ bits iguais a 1, após exatamente ${\displaystyle n}$ iterações desta operação, ${\displaystyle x}$ 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:^[15]

/* 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.^[16] 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^[17] é um dos mais rápidos que também necessita apenas de operações de números inteiros.^[18]

Na codificação de correção de erros, o peso de Hamming mínimo, habitualmente referido como o peso mínimo ${\displaystyle w_{\min }}$ de um código, é o peso da palavra de código não nula de menor peso. O peso ${\displaystyle w}$ 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 (${\displaystyle d_{\min }}$) e define a capacidade de correção de erros do código. Se ${\displaystyle w_{\min }=n}$, então ${\displaystyle d_{\min }=n}$ e o código corrigirá até ${\displaystyle d_{\min }/2}$ erros.^[19]

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.^[20] O LLVM-GCC também inclui esta função desde a versão 1.5 em junho de 2005.^[21]

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 [[[:Predefinição:Javadoc:SE/Home URL]]docs/api/java/util/BitSet.html BitSet] tem um método [[[:Predefinição:Javadoc:SE/Home URL]]docs/api/java/util/BitSet.html#cardinality() BitSet.cardinality()] que conta o número de bits definidos. Adicionalmente, existem as funções [[[:Predefinição:Javadoc:SE/Home URL]]docs/api/java/lang/Integer.html#bitCount(int) Integer.bitCount(int)] e [[[:Predefinição:Javadoc:SE/Home URL]]docs/api/java/lang/Long.html#bitCount(long) Long.bitCount(long)] para contar bits em números inteiros primitivos de 32 e 64 bits, respetivamente. A classe de inteiros de precisão arbitrária [[[:Predefinição:Javadoc:SE/Home URL]]docs/api/java/math/BigInteger.html BigInteger] também tem um método [[[:Predefinição:Javadoc:SE/Home URL]]docs/api/java/math/BigInteger.html#bitCount() BigInteger.bitCount()] que efetua a contagem de bits.

Em Python, o tipo int tem o método bit_count() para contar o número de bits em um. Esta funcionalidade foi introduzida no Python 3.10, lançado em outubro de 2021.^[22]

Em Common Lisp, a função logcount, dado um número inteiro não negativo, devolve o número de bits 1. (Para inteiros negativos devolve o número de bits 0 na notação de complemento para dois.) Em qualquer dos casos, o número inteiro pode ser um número grande de precisão arbitrária (bignum).

A partir da versão 7.4 do GHC, o pacote base do Haskell tem uma função popCount disponível em todos os tipos que são instâncias da classe Bits (disponível a partir do módulo Data.Bits).^[23]

A versão MySQL da linguagem SQL dispõe de BIT_COUNT() como uma função padrão.^[24]

O Fortran 2008 possui a função elementar, intrínseca e padrão popcnt que devolve o número de bits não nulos num número inteiro (ou matriz de inteiros).^[25]

Algumas calculadoras científicas de bolso programáveis oferecem comandos especiais para calcular o número de bits definidos, como, por exemplo, #B na HP-16C.^[3]

O Free Pascal implementa o popcnt desde a versão 3.0.^[26]

[Image of Processor Arithmetic Logic Unit]

• O computador IBM STRETCH da década de 1960 calculava o número de bits em um bem como a contagem de zeros à esquerda como subproduto de todas as operações lógicas.^[1]
• Os supercomputadores Cray possuíam desde cedo uma instrução de máquina para contagem da população, havendo rumores de que terá sido especificamente solicitada pelo governo dos EUA através da Agência de Segurança Nacional (NSA) para aplicações de criptanálise.^[1]
• As máquinas da série CDC 6000 e Cyber 70/170 da Control Data Corporation (CDC) incluíam uma instrução de contagem da população; no COMPASS, esta instrução era codificada como CXi.
• A arquitetura SPARC de 64 bits versão 9 define uma instrução POPC,^[12][1] mas a maioria das implementações não a operacionaliza de forma nativa, necessitando que seja emulada pelo sistema operativo.^[27]
• O modelo de computador MMIX do investigador Donald Knuth, concebido para substituir o MIX no seu livro The Art of Computer Programming, dispõe de uma instrução SADD desde 1999. A operação SADD a,b,c conta todos os bits que são 1 em ${\displaystyle b}$ e 0 em ${\displaystyle c}$ e escreve o resultado em ${\displaystyle a}$.
• O processador Alpha 21264A da Compaq, lançado em 1999, foi o primeiro modelo de CPU da série Alpha a incorporar a extensão de contagem (CIX).
• Os processadores Blackfin da Analog Devices contam com a instrução ONES para executar uma contagem de população de 32 bits.^[28]
• A arquitetura Barcelona da AMD introduziu a manipulação avançada de bits (ABM) baseada na ISA, estreando a instrução POPCNT como parte das extensões SSE4a em 2007.
• Os processadores Intel Core introduziram uma instrução POPCNT com a extensão do conjunto de instruções SSE4.2, disponibilizada pela primeira vez num processador Core i7 baseado na microarquitetura Nehalem, lançada em novembro de 2008.
• A Arquitetura ARM introduziu a instrução VCNT como parte das extensões Advanced SIMD (NEON).
• A arquitetura RISC-V introduziu a instrução CPOP enquanto parte da extensão de Manipulação de Bits (B).^[29]

• Complemento para dois
• Fan-out

• Beeler, Michael; Gosper, Ralph William; Schroeppel, Richard C. (29 de fevereiro de 1972). HAKMEM. compilation (report). Laboratório de Inteligência Artificial, Instituto de Tecnologia de Massachusetts, Cambridge, Massachusetts, EUA. MIT AI Memo 239  |contributor= ignorado (ajuda) (Item 169: Código assembly de contagem da população para o PDP/6-10.)

• Aggregate Magic Algorithms. Contagem de população otimizada e outros algoritmos explicados com código de exemplo.
• Bit Twiddling Hacks Vários algoritmos com código para contagem de bits definidos.
• Necessary and Sufficient Arquivado em 2017-09-23 no Wayback Machine - por Damien Wintour - Contém código C# para várias implementações do Peso de Hamming.
• Best algorithm to count the number of set bits in a 32-bit integer? - Stackoverflow