Waga Hamminga - Hamming weight
Ciężar Hamminga z łańcucha jest liczba symboli, które są różne od zera-symbol alfabetu używany. Jest to zatem równoważne odległości Hamminga od struny zerowej o tej samej długości. Dla najbardziej typowym przypadku, ciąg bitów , jest to numer 1 w łańcuchu, czyli suma cyfr z binarnej reprezentacji danej liczby i £ -l roboczego pi normą bity wektora. W tym przypadku binarnym nazywa się to również licznikiem populacji , popcount , sumą boczną lub sumowaniem bitów .
Strunowy | Waga Hamminga |
---|---|
111 0 1 | 4 |
111 0 1 000 | 4 |
00000000 | 0 |
678 0 1234 0 567 | 10 |
Wykres liczby populacji (waga Hamminga dla liczb binarnych) dla liczb (dziesiętnych) od 0 do 256. |
Historia i użytkowanie
Waga Hamminga została nazwana na cześć Richarda Hamminga, chociaż to nie on był pomysłodawcą tego pojęcia. Waga Hamminga liczb binarnych została już użyta w 1899 roku przez Jamesa WL Glaishera, aby dać wzór na liczbę nieparzystych współczynników dwumianowych w jednym rzędzie trójkąta Pascala . Irving S. Reed wprowadził koncepcję, równoważną wadze Hamminga w przypadku binarnym, w 1954 roku.
Hamminga wagę stosuje się w wielu dziedzinach, w tym teorii informacji , teorii kodowania i szyfrowania . Przykładowe zastosowania ciężarka Hamminga to:
- W potęgowaniu modularnym przez kwadrat , liczba mnożeń modularnych wymaganych dla wykładnika e wynosi log 2 e + waga( e ). Jest to powód, dla którego wartość klucza publicznego e używana w RSA jest zwykle wybierana jako liczba o niskiej wadze Hamminga.
- Waga Hamminga określa długości ścieżek między węzłami w rozproszonych tablicach mieszających Chord .
- Wyszukiwania IrisCode w biometrycznych bazach danych są zazwyczaj implementowane przez obliczenie odległości Hamminga do każdego zapisanego rekordu.
- W komputerowych programach szachowych wykorzystujących reprezentację bitboardową , waga Hamminga bitboardu podaje liczbę bierek danego typu pozostających w grze lub liczbę pól szachownicy kontrolowanych przez pionki jednego gracza, a zatem jest ważnym terminem przyczyniającym się do wartości pozycji.
- Waga Hamminga może być użyta do efektywnego obliczenia find pierwszego zestawu przy użyciu tożsamości ffs(x) = pop(x ^ (x - 1)). Jest to przydatne na platformach takich jak SPARC, które mają instrukcje sprzętowe dotyczące wagi Hamminga, ale nie mają instrukcji znajdowania pierwszego zestawu.
- Operację wagi Hamminga można interpretować jako konwersję z jednoargumentowego systemu liczbowego na liczby binarne .
- W realizacji niektórych zwięzłych struktur danych, takich jak wektory bitowe i drzewa falkowe .
Sprawne wdrożenie
Liczba populacji ciągu bitów jest często potrzebna w kryptografii i innych aplikacjach. Odległość Hamminga dwóch słów A i B, można obliczyć masę Hamminga A XOR B .
Problem, jak go skutecznie wdrożyć, był szeroko badany. Pojedyncza operacja do obliczeń lub równoległe operacje na wektorach bitowych są dostępne na niektórych procesorach . W przypadku procesorów pozbawionych tych cech najlepsze znane rozwiązania opierają się na dodawaniu zliczeń we wzorze drzewa. Na przykład, aby policzyć liczbę 1 bitów w 16-bitowej liczbie binarnej a = 0110 1100 1011 1010, można wykonać następujące operacje:
Wyrażenie | Dwójkowy | Dziesiętny | Komentarz | |||||||
---|---|---|---|---|---|---|---|---|---|---|
a
|
01 | 10 | 11 | 00 | 10 | 11 | 10 | 10 | 27834 | Oryginalny numer |
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 | Co drugi bit od |
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 | Pozostałe bity z |
c = b0 + b1
|
01 | 01 | 10 | 00 | 01 | 10 | 01 | 01 | 1, 1, 2, 0, 1, 2, 1, 1 | Liczba 1s w każdym 2-bitowym wycinku a |
d0 = (c >> 0) & 0011 0011 0011 0011
|
0001 | 0000 | 0010 | 0001 | 1, 0, 2, 1 | Wszystkie inne liczą się od c | ||||
d2 = (c >> 2) & 0011 0011 0011 0011
|
0001 | 0010 | 0001 | 0001 | 1, 2, 1, 1 | Pozostałe liczy od c | ||||
e = d0 + d2
|
0010 | 0010 | 0011 | 0010 | 2, 2, 3, 2 | Liczba 1s w każdym 4-bitowym wycinku a | ||||
f0 = (e >> 0) & 00001111 00001111
|
00000010 | 00000010 | 2, 2 | Wszystkie inne liczą się od e | ||||||
f4 = (e >> 4) & 00001111 00001111
|
00000010 | 00000011 | 2, 3 | Pozostałe liczy od e | ||||||
g = f0 + f4
|
00000100 | 00000101 | 4, 5 | Liczba 1s w każdym 8-bitowym wycinku a | ||||||
h0 = (g >> 0) & 0000000011111111
|
000000000000101 | 5 | Wszystkie inne liczą się od g | |||||||
h8 = (g >> 8) & 0000000011111111
|
000000000000100 | 4 | Pozostałe liczy z g | |||||||
i = h0 + h8
|
00000000000001001 | 9 | Liczba 1s w całym 16-bitowym słowie |
Tutaj operacje są takie jak w języku programowania C , więc X >> Y
oznacza przesunięcie X w prawo o bity Y, X & Y oznacza bitowe AND X i Y, a + jest zwykłym dodawaniem. Najlepsze algorytmy znane dla tego problemu opierają się na koncepcji zilustrowanej powyżej i są podane tutaj:
//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) + ...
}
Powyższe implementacje mają najlepsze zachowanie w najgorszym przypadku ze wszystkich znanych algorytmów. Jeśli jednak oczekuje się, że wartość będzie miała kilka niezerowych bitów, zamiast tego bardziej efektywne może być użycie algorytmów, które zliczają te bity pojedynczo. Jak opisał Wegner w 1960 r., bitowe AND dla x z x − 1 różni się od x tylko wyzerowaniem najmniej znaczącego bitu niezerowego: odjęcie 1 zmienia skrajny prawy ciąg zer na 1, a skrajny prawy 1 na 0. Jeśli x pierwotnie miał n bitów, które były 1, to po zaledwie n iteracjach tej operacji, x zostanie zredukowane do zera. Na tej zasadzie opiera się następująca implementacja.
//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;
}
Jeśli dozwolone jest większe wykorzystanie pamięci, możemy obliczyć wagę Hamminga szybciej niż powyższe metody. Mając nieograniczoną pamięć, moglibyśmy po prostu stworzyć dużą tabelę przeglądową wagi Hamminga każdej 64-bitowej liczby całkowitej. Jeśli możemy przechowywać tabelę przeglądową funkcji Hamminga dla każdej 16-bitowej liczby całkowitej, możemy wykonać następujące czynności, aby obliczyć wagę Hamminga dla każdej 32-bitowej liczby całkowitej.
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 i in. wykazali, że zwektoryzowana wersja popcount64b może działać szybciej niż dedykowane instrukcje (np. popcnt na procesorach x64).
Minimalna waga
W kodowaniu z korekcją błędów minimalna waga Hamminga, potocznie nazywana minimalną wagą w min kodu, jest wagą najmniejszego niezerowego słowa kodowego. Waga w słowa kodowego to liczba jedynek w słowie. Na przykład słowo 11001010 ma wagę 4.
W liniowym kodzie blokowym minimalna waga jest również minimalną odległością Hamminga ( d min ) i określa zdolność korekcji błędów kodu. Jeśli w min = n , to d min = n i kod poprawi do d min /2 błędy.
Wsparcie językowe
Niektóre kompilatory języka C zapewniają wewnętrzne funkcje, które zapewniają funkcje zliczania bitów. Na przykład, GCC (od wersji 3.4 w kwietniu 2004) zawiera wbudowaną funkcję __builtin_popcount
, która użyje instrukcji procesora, jeśli jest dostępna, lub wydajną implementację biblioteki w przeciwnym razie. LLVM-GCC zawiera tę funkcję od wersji 1.5 w czerwcu 2005.
W C++ STL struktura danych tablicy bitowej bitset
ma count()
metodę, która zlicza liczbę ustawionych bitów. W C++20 dodano nowy nagłówek <bit>
zawierający funkcje std::popcount
i std::has_single_bit
, przyjmujący argumenty typu unsigned integer.
W Javie struktura danych z rosnącą tablicą bitów BitSet
ma BitSet.cardinality()
metodę, która zlicza liczbę ustawionych bitów. Ponadto istnieją Integer.bitCount(int)
i Long.bitCount(long)
funkcje do zliczania bitów odpowiednio w 32-bitowych i 64-bitowych liczbach całkowitych. Ponadto BigInteger
klasa liczb całkowitych arbitralnej precyzji ma również BigInteger.bitCount()
metodę zliczającą bity.
W Pythonie , int
typ ma bit_count()
sposobu, aby policzyć liczbę bitów zestawu. Ta funkcja jest nowa w Pythonie 3.10, której premiera zaplanowana jest na 2021 rok.
W Common Lisp funkcja logcount
, mająca nieujemną liczbę całkowitą, zwraca liczbę 1 bitów. (Dla ujemnych liczb całkowitych zwraca liczbę bitów 0 w notacji uzupełnienia do dwójek). W obu przypadkach liczba całkowita może być BIGNUM.
Począwszy od GHC 7.4, pakiet podstawowy Haskell ma popCount
funkcję dostępną dla wszystkich typów, które są instancjami Bits
klasy (dostępne z Data.Bits
modułu).
Wersja MySQL języka SQL zapewnia BIT_COUNT()
jako standardową funkcję.
Fortran 2008 ma standardową, wewnętrzną, elementarną funkcję popcnt
zwracającą liczbę niezerowych bitów w liczbie całkowitej (lub tablicy liczb całkowitych).
Niektóre programowalne naukowe kalkulatory kieszonkowe posiadają specjalne komendy, aby obliczyć liczbę ustawionych bitów, na przykład #B
w systemie HP-16C i WP 43S , #BITS
lub BITSUM
na emulatory HP-16C, a nBITS
na WP 34S .
FreePascal implementuje popcnt od wersji 3.0.
Obsługa procesora
- Komputer IBM STRETCH w latach 60. obliczał liczbę bitów zestawu, a także liczbę zer wiodących jako produkt uboczny wszystkich operacji logicznych.
- Superkomputery Cray na początku zawierały instrukcję maszynową do liczenia populacji , która podobno była specjalnie wymagana przez Narodową Agencję Bezpieczeństwa rządu USA do zastosowań kryptoanalizy .
-
Maszyny z serii Control Data Corporation (CDC) 6000 i Cyber 70/170 zawierały instrukcję liczenia populacji; w COMPASS instrukcja ta została zakodowana jako
CXi
. - 64-bitowa architektura SPARC w wersji 9 definiuje
POPC
instrukcję, ale większość implementacji jej nie implementuje, wymagając emulacji przez system operacyjny. -
Model komputera MMIX Donalda Knutha , który ma zastąpić MIX w jego książce The Art of Computer Programming ma
SADD
instrukcję od 1999 roku.SADD a,b,c
liczy wszystkie bity, które są 1 w b i 0 w c i zapisuje wynik do a. -
Compaq „s Alpha 21264A , wydany w 1999 roku, był pierwszym z serii Alpha CPU projekt, który miał rozszerzenie count (
CIX
). -
Analog Devices ' BLACKFIN procesory są wyposażone w
ONES
instrukcje do wykonywania 32-bitowej liczby ludności. -
AMD „s Barcelona architektura wprowadzono zaawansowaną nieco manipulacja (ABM) ISA wprowadzającej
POPCNT
instrukcji jako część SSE4a rozszerzenia w 2007 r. -
Intel Core procesory wprowadził
POPCNT
dyspozycję z SSE4.2 Instruction Set rozszerzenia, najpierw dostępne w Nehalem -na Core i7 procesor, wydany w listopadzie 2008 roku. - Architektura ARM wprowadził
VCNT
dyspozycję jako część zaawansowane SIMD ( NEON ) rozszerzeń. - Architektura RISC-V wprowadziła
PCNT
instrukcję jako część rozszerzenia Bit Manipulation (B).
Zobacz też
Bibliografia
Dalsza lektura
- Schroeppel, Richard C .; Orman, Hilarie K. (1972-02-29). "kompilacja". HAKMEM . Przez Beelera, Michaela; Gosper, Ralph William ; Schroeppel, Richard C. (raport). Laboratorium Sztucznej Inteligencji , Massachusetts Institute of Technology , Cambridge, Massachusetts, USA. Notatka MIT AI 239.( Pozycja 169 : Kod zespołu liczenia populacji dla PDP/6-10.)
Linki zewnętrzne
- Agregaty Magiczne Algorytmy . Zoptymalizowana liczba populacji i inne algorytmy wyjaśnione za pomocą przykładowego kodu.
- Bit Twiddling Hacks Kilka algorytmów z ustawionym kodem do liczenia bitów.
- Niezbędne i wystarczające - autorstwa Damiena Wintoura - Posiada kod w C# dla różnych implementacji Hamming Weight.
- Najlepszy algorytm do liczenia liczby ustawionych bitów w 32-bitowej liczbie całkowitej? - Przepełnienie stosu