Pes de Hamming

Archiu:Hamming weight for binary numbers.png

Un gràfic del conteo de població (pes de Hamming d'número binario) per als números (decimals) de 0 a 256.

Eixemples

Cadena de caràcters	Pes de Hamming
11101	4
11101000	4
00000000	0
678012340567	10

El pes de Hamming d'una cadena de caràcters és el número de símbols que són diferents del símbol zero del alfabet utilisat. Per lo tant, és equivalent a la distància de Hamming de la cadena de zeros de la mateixa llongitut. Per al cas més típic, una cadena de bits, est és el número d'uns en la cadena, o la sumixca de dígits de la representació binaria d'un número donat i la norma ℓ₁ d'un vector de bits. En el cas binario, també es denomina reconte de població, suma lateral, o suma de bits.

Història i us

La funció du el nom de Richard Hamming, encara que ell no va originar el concepte. El pes de Hamming dels número binario ya va ser utilisat en 1899 per James W. L. Glaisher per a donar una fòrmula per al número de coeficients binomiales impar en una sola fila del triàngul de Pascal. Irving Stoy Reed també va introduir en 1954 un concepte equivalent en el cas binario.

El pes de Hamming s'usa en vàries disciplines, incloses la teoria de l'informació, la teoria de còdics i la criptografia. Eixemples d'aplicacions del pes de Hamming inclouen:

• l'exponenciación binaria modular; el número de multiplicacions modular necessàries per a un exponent i és log₂ i + pes(i). Esta és la raó per la que el valor de la clau pública i que s'utilisa en RSA normalment s'elegix com un número de baix pes de Hamming.
• El pes de Hamming determina les llongituts de ruta entre nodos en les taules de l'algoritme Chord.
• Les tècniques de reconeiximent de iris en les bases de senyes biométricas s'implementen normalment calculant la distància de Hamming de cada registre almagasenat.
• En els programes d'escacs per computadora que utilisen una representació bitboard, el pes de Hamming d'un tauler de bits dona el número de peces d'un tipo determinat que queden en el joc, o el número de caselles del tauler controlat per les peces d'un jugador i, per lo tant, és un terme contribuent important al valor d'una posició.
• El pes de Hamming es pot usar para trobar el primer conjunt de manera eficient usant l'identitat ffs(x) = pop(x ^ (x - 1)). Açò és útil en plataformes com Sun SPARC que tenen instruccions de pes de Hamming d'hardware pero cap instrucció de primer conjunt de busca d'hardware.
• L'operació de pes de Hamming es pot interpretar com una conversió del sistema de numeració unario al sistema binario.
• En el maneig d'algunes estructures de senyes sucintas com els vectores de bits i els arbres d'ones.

Càlcul eficient

El conteo de població d'un fluix de senyes a sovint es necessita en criptografia i atres aplicacions. La distància de Hamming de dos paraules A i B es pot calcular com el pes de Hamming d'exclusivament A o B.

El problema de cóm determinar-ho de manera eficient ha segut àmpliament estudiat. Una sola operació per al càlcul, o operacions paraleles sobre vectores de bits són disponible en alguns processadors. Per als processadors que carixen d'eixes funcions, les millors solucions conegudes es basen en agregar contes en un patró d'arbre. Per eixemple, per a contar el número d'1 bits en l'número binario de 16 bits a = 0110 1100 1011 1010, es poden realisar estes operacions:

Expressió	Binaria								Decimal	Comentari
a	01	10	11	00	10	11	10	10	style="text-align:left;" Plantilla:Cela	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 atre 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	Els bits restants de a
c= b0 + b1	01	01	10	00	01	10	01	01	1, 1, 2, 0, 1, 2, 1, 1	Reconte d'uns en cada porció de 2 bits de a
d0= (c >> 0) & 0011 0011 0011 0011	0001		0000		0010		0001		1, 0, 2, 1	Tots els demés contats des de c |-	d2= (c >> 2) & 0011 0011 0011 0011	0001		0010		0001		0001		1, 2, 1, 1	Els restants contats des de c |-	i= d0 + d2	0010		0010		0011		0010		2, 2, 3, 2	Reconte d'uns en cada porció de 4 bits de a
f0= (i >> 0) & 00001111 00001111	00000010				00000010				2, 2	Tots els demés contats des d'i
f4= (i >> 4) & 00001111 00001111	00000010				00000011				2, 3	El restant contats des d'i
g= f0 + f4	00000100				00000101				4, 5	Reconte d'uns en cada segment de 8 bits de a
h0= (g >> 0) & 0000000011111111	0000000000000101								5	Tots els demés contats des de g |-	h8= (g >> 8) & 0000000011111111	0000000000000100								4	El restant contats des de g |-	i= h0 + h8	0000000000001001								9	Reconte d'uns en una paraula completa de 16 bits

Ací, les operacions són com en llenguage de programació C, per lo que Plantilla:Code significa desplaçar X a la dreta en I bits, X & I significa el AND bit a bit de X i I, i + és una suma ordinària. Els millors algoritmes coneguts per a este problema es basen en el concepte ilustrat anteriorment i es proporcionen ací:

//Tipos de variables i constants usats ​​en les següents funcions
//uint64_t és un tipo de variable sancera de 64 bits sense signe (definida en la versió C99 del llenguage C)
const uint64_t m1= 0x5555555555555555; //binary: 0101...
const uint64_t m2= 0x3333333333333333; //binary: 00110011..
const uint64_t m4= 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8= 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16= 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32= 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01= 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//Açò és un eixemple simple, que es mostra a modo de comparació,

//i per a ajudar a comprendre millor les funcions.
//L'algoritme utilisa 24 operacions aritmètiques (shift, add, and).
int popcount64a(uint64_t x)
{
    x= (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x= (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x= (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x= (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x= (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x= (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}

//Este eixemple usa menys operacions aritmètiques que qualsevol atra aplicació
//coneguda en màquines en multiplicació llenta.
//L'algoritme utilisa 17 operacions aritmètiques.
int popcount64b(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x= (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x= (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}

//Este eixemple usa menys operacions aritmètiques que qualsevol atra aplicació
//coneguda en màquines en multiplicació ràpida.
//L'algoritme utilisa 12 operacions aritmètiques, una de les quals és una multiplicació.
int popcount64c(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x= (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x= (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

Les aplicacions anteriors tenen el millor comportament en el pijor dels casos de qualsevol algoritme conegut. No obstant, quan s'espera que un valor tinga pocs bits distints de zero, pot ser més eficient utilisar algoritmes que conten estos bits d'un en un. Com Wegner va descriure en 1960, l'operador a nivell de bits de x en x - 1 diferix de x solament en posar a zero el bit distint de zero menys significatiu: restar 1 canvia el bit més a la dreta de la cadena de 0s a 1s, i canvia l'1 més a la dreta a un 0. Si x originalment tenia n bits que eren 1, llavors despuix de solament n iteraciones d'esta operació, x es reduirà a zero. El següent eixemple es basa en este principi.

//Esta aplicació és millor quan la majoria dels bits en x són 0
//L'algoritme funciona igual per a tots els tamanys de senyes.
//Usa 3 operacions aritmètiques i 1 comparació/branca per "1" bit en x.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

Si es permet un major us de memòria, es pot calcular el pes de Hamming més ràpidament que en els métodos anteriors. En memòria illimitada, es podria simplement crear una gran taula de busca del pes de Hamming de cada sancer de 64 bits. Si es pot almagasenar una taula de busca de la funció de Hamming de cada sancer de 16 bits, es pot fer lo següent per a calcular el pes de Hamming de cada sancer de 32 bits.

static uint8_t wordbits[65536]= {/* bitcounts of integers 0 through 65535, inclusivament */ };
//Este algoritme utilisa 3 operacions aritmètiques i 2 llectures de memòria.
int popcount32i(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Opcionalmente, la taula wordbits[] podria reblir-se usant esta funció
int popcount32i_init(void)
{
    uint32_t i;
    uint16_t x;
    int count;
    for (i=0; i <= 0xFFFF; i++)
    {
        x= i;
        for (count=0; x; count++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i]= count;
    }
}

Muła et al. varen demostrar que una versió vectorizada de popcount64b pot eixecutar-se més ràpit que les instruccions dedicades (per eixemple, popcnt en els processadors x64).

Vore també

• Complement a dos
• Fan out