Hamming vekt - Hamming weight

Den Hamming-vekten av en streng er det antall symboler som er forskjellig fra null-symbol av alfabetet anvendes. Det tilsvarer dermed Hamming-avstanden fra nullstrengen av samme lengde. For det mest typiske tilfellet, en streng med biter , er dette tallet 1 i strengen, eller tallsummen for den binære representasjonen av et gitt tall og ℓ ₁ normen for en bitvektor. I dette binære tilfellet kalles det også befolkningstallet , popcount , summen sidelengs eller bit summering .

Historie og bruk

Hamming -vekten er oppkalt etter Richard Hamming, selv om han ikke stammer fra tanken. Hammingvekten til binære tall ble allerede brukt i 1899 av James WL Glaisher for å gi en formel for antall oddetall binomiske koeffisienter i en enkelt rad i Pascals trekant . Irving S. Reed introduserte et konsept, tilsvarende Hamming -vekt i binærhuset, i 1954.

Hammingvekt brukes i flere disipliner, inkludert informasjonsteori , kodeteori og kryptografi . Eksempler på anvendelser av Hamming -vekten inkluderer:

• I modulær eksponentiering ved kvadrering er antallet modulære multiplikasjoner som kreves for en eksponent e log ₂ e + vekt ( e ). Dette er grunnen til at den offentlige nøkkelverdien e som brukes i RSA vanligvis er valgt til å være et antall lav Hamming -vekt.
• Hamming -vekten bestemmer banelengder mellom noder i akkordfordelte hashtabeller .
• IrisCode -oppslag i biometriske databaser implementeres vanligvis ved å beregne Hamming -avstanden til hver lagrede post.
• I datamaskinen sjakk programmer ved hjelp av en bitboard representasjon, Hamming vekten av en bitboard gir antallet av biter av en gitt type igjen i spillet, eller antallet av kvadrater av brettet styres av en spillers stykker, og er derfor en viktig medvirkende sikt til verdien av en posisjon.
• Hammingvekt kan brukes til effektivt å beregne finn første sett ved hjelp av identiteten ffs (x) = pop (x ^ (x - 1)). Dette er nyttig på plattformer som SPARC som har Hamming -vektinstruksjoner for maskinvare, men ingen instruksjoner for første maskinvare finner.
• Hamming -vektoperasjonen kan tolkes som en konvertering fra det unære tallsystemet til binære tall .
• Ved implementering av noen kortfattede datastrukturer som bitvektorer og wavelet -trær .

Effektiv implementering

Befolkningstallet til en bitstreng er ofte nødvendig i kryptografi og andre applikasjoner. Den Hamming-avstand mellom to ord A og B kan beregnes som Hamming-vekten av A xor B .

Problemet med hvordan man implementerer det effektivt har blitt studert mye. En enkelt operasjon for beregningen eller parallelle operasjoner på bitvektorer er tilgjengelig på noen prosessorer . For prosessorer som mangler disse funksjonene, er de beste kjente løsningene basert på å legge til tellinger i et tremønster. For eksempel, for å telle antallet 1 bits i det 16-biters binære tallet a = 0110 1100 1011 1010, kan disse operasjonene utføres:

Her er operasjonene som i programmeringsspråk C , så X >> Ybetyr å skifte X til høyre med Y -biter, X og Y betyr bitvis AND for X og Y, og + er vanlig tillegg. De beste algoritmene som er kjent for dette problemet er basert på konseptet illustrert ovenfor og er gitt her:

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
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...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (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;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
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;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
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) + ... 
}

Ovennevnte implementeringer har den beste verste oppførselen til noen kjent algoritme. Imidlertid, når en verdi forventes å ha få bits uten null, kan det i stedet være mer effektivt å bruke algoritmer som teller disse bitene en om gangen. Som Wegner beskrev i 1960, er bitvis OG av x med x  - 1 forskjellig fra x bare ved å nullstille den minst signifikante nullbiten: subtrahering 1 endrer den høyeste strengen på 0s til 1s, og endrer den høyre til en 0. Hvis x opprinnelig hadde n biter som var 1, så etter bare n iterasjoner av denne operasjonen, vil x bli redusert til null. Følgende implementering er basert på dette prinsippet.

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

Hvis større minnebruk er tillatt, kan vi beregne Hamming -vekten raskere enn metodene ovenfor. Med ubegrenset minne kan vi ganske enkelt lage et stort oppslagstabell med Hamming -vekten for hvert 64 -bits heltall. Hvis vi kan lagre en oppslagstabell for hammingfunksjonen til hvert 16 -bits heltall, kan vi gjøre følgende for å beregne Hamming -vekten for hvert 32 -bits heltall.

static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
//This algorithm uses 3 arithmetic operations and 2 memory reads.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Optionally, the wordbits[] table could be filled using this function
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++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i] = count;
    }
}

Muła et al. har vist at en vektorisert versjon av popcount64b kan kjøre raskere enn dedikerte instruksjoner (f.eks. popcnt på x64 -prosessorer).

Minste vekt

Ved feilkorrigerende koding er minimum Hamming-vekt, vanligvis referert til som minimumsvekten w _min av en kode, vekten av det laveste vekt-ikke-null kodeordet. Vekten w av et kodeord er tallet 1s i ordet. For eksempel har ordet 11001010 en vekt på 4.

I en lineær blokkode er minimumsvekten også minimum Hamming -avstand ( d _min ) og definerer feilkorrigeringsevnen til koden. Hvis w _min  =  n , så d _min  =  n og koden vil korrigere opptil d _min /2 feil.

Språkstøtte

Noen C -kompilatorer har innebygde funksjoner som gir mulighet for bittelling. For eksempel inkluderer GCC (siden versjon 3.4 i april 2004) en innebygd funksjon __builtin_popcountsom vil bruke en prosessorinstruksjon hvis tilgjengelig eller en effektiv bibliotekimplementering på annen måte. LLVM-GCC har inkludert denne funksjonen siden versjon 1.5 i juni 2005.

I C ++ STL har bit-array datastrukturen bitseten count()metode som teller antall biter som er satt. I C ++ 20 ble en ny overskrift <bit>lagt til, som inneholder funksjoner std::popcountog std::has_single_bittar argumenter av usignerte heltallstyper.

I Java har den voksbare bit-array datastrukturen BitSeten BitSet.cardinality()metode som teller antall biter som er satt. I tillegg er det Integer.bitCount(int)og Long.bitCount(long)funksjoner for å telle biter i henholdsvis primitive 32-bits og 64-bits heltall. Heltallklassen BigIntegervilkårlig presisjon har også en BigInteger.bitCount()metode som teller biter.

I Python har inttypen en bit_count()metode for å telle antall biter som er angitt. Denne funksjonaliteten er ny i Python 3.10, planlagt for utgivelse i 2021.

I Common Lisplogcount returnerer funksjonen , gitt et ikke-negativt heltall, antallet 1 biter. (For negative heltall returnerer det antallet 0 bits i 2s komplementnotasjon.) I begge tilfeller kan heltallet være et BIGNUM.

Fra og med GHC 7.4 har Haskell -basepakken en popCountfunksjon tilgjengelig på alle typer som er forekomster av Bitsklassen (tilgjengelig fra Data.Bitsmodulen).

MySQL -versjon av SQL -språk gir BIT_COUNT()som en standardfunksjon.

Fortran 2008 har standard, iboende, elementær funksjon som popcntreturnerer antall ikke -null biter i et heltall (eller heltall array).

Noen programmerbare vitenskapelige lommekalkulatorer har spesielle kommandoer for å beregne antall settbiter , f.eks. #BPå HP-16C og WP 43S , #BITSeller BITSUMpå HP-16C-emulatorer, og nBITSpå WP 34S .

Free Pascal redskaper popcnt siden versjon 3.0.

Prosessorstøtte

• Den IBM STRETCH datamaskin i 1960 beregnet antall sett-biter, så vel som antallet av ledende nuller som et bi-produkt av alle logiske operasjoner.
• Cray -superdatamaskiner inneholdt tidlig en maskininstruksjon for befolkningstall , som ryktes å ha blitt spesielt forespurt av den amerikanske regjeringen National Security Agency for kryptanalyse -applikasjoner.
• Control Data Corporation 's (CDC) 6000 og Cyber 70/170 serie maskiner omfattet en befolkning teller instruksjon; i COMPASS , ble denne instruksjonen kodet som CXi.
• 64-biters SPARC versjon 9-arkitektur definerer en POPCinstruksjon, men de fleste implementeringer implementerer den ikke, og krever at den emuleres av operativsystemet.
• Donald Knuths modelldatamaskin MMIX som skal erstatte MIX i sin bok The Art of Computer Programming har en SADDinstruksjon siden 1999. SADD a,b,cteller alle biter som er 1 i b og 0 i c og skriver resultatet til a.
• Compaq 's Alpha 21264A , utgitt i 1999, var den første Alpha -serien CPU -designen som hadde telleforlengelsen ( CIX).
• Analog Devices ' Blackfin- prosessorer har ONESinstruksjoner om å utføre et 32-biters populasjonstall.
• AMD 's Barcelona arkitektur innført avanserte bit manipulasjon (ABM) ISA innføre POPCNTundervisning som en del av SSE4a utvidelsene i 2007.
• Intel Core -prosessorer introduserte en POPCNTinstruksjon med forlengelsen SSE4.2 -instruksjonssett , først tilgjengelig i en Nehalem -basert Core i7 -prosessor, utgitt i november 2008.
• Den armen arkitektur innføres den VCNTinstruksjon som en del av Advanced SIMD ( NEON ) utvidelser.
• Den RISC-V -arkitektur innført den PCNTinstruksjon som en del av Bit Manipulation (B) forlengelse.

Se også

• To komplement
• Hyppigste k-tegn
• Vifte ut

Referanser

Videre lesning

• Schroeppel, Richard C .; Orman, Hilarie K. (1972-02-29). "samling". HAKMEM . Av Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (rapport). Artificial Intelligence Laboratory , Massachusetts Institute of Technology , Cambridge, Massachusetts, USA. MIT AI Memo 239.( Artikkel 169 : Befolkningstallskode for PDP/6-10.)

Eksterne linker

• Aggregerte magiske algoritmer . Optimalisert populasjonstall og andre algoritmer forklart med prøvekode.
• Bit Twiddling Hacks Flere algoritmer med kode for å telle bits sett.
• Nødvendig og tilstrekkelig - av Damien Wintour - Har kode i C# for forskjellige Hamming Weight -implementeringer.
• Beste algoritme for å telle antall settbiter i et 32-bits heltall? - Stackoverflow