Hammingova hmotnost - Hamming weight
![]() | tento článek potřebuje další citace pro ověření.Leden 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
![]() | Bylo navrženo, že Minimální hmotnost být sloučeny do tohoto článku. (Diskutujte) Navrhováno od července 2020. |
The Hammingova hmotnost a tětiva je počet symbolů, které se liší od nulového symbolu abeceda použitý. Je tedy ekvivalentní s Hammingova vzdálenost z nulového řetězce stejné délky. Pro nejtypičtější případ řetězec řetězce bity, toto je počet 1 v řetězci, nebo součet číslic z binární reprezentace daného čísla a ℓ₁ norma bitového vektoru. V tomto binárním případě se také nazývá počet obyvatel,[1] počet obyvatel, součet do strany,[2] nebo bitový součet.[3]
Tětiva | Hammingova hmotnost |
---|---|
11101 | 4 |
11101000 | 4 |
00000000 | 0 |
678012340567 | 10 |
![]() |
Graf pro počet obyvatel (Hammingova váha pro binární čísla) pro (desetinná) čísla od 0 do 256.[4][5][6] |
Historie a použití
Hammingova váha je pojmenována po Richard Hamming i když tu představu nevytvořil.[7] Hammingova váha binárních čísel byla použita již v roce 1899 James W. L. Glaisher dát vzorec pro počet lichých binomických koeficientů v jedné řadě Pascalův trojúhelník.[8] Irving S. Reed představil koncept, ekvivalentní Hammingově hmotnosti v binárním případě, v roce 1954.[9]
Hammingova váha se používá v několika disciplínách včetně teorie informace, teorie kódování, a kryptografie. Mezi příklady použití Hammingovy váhy patří:
- V modulárním provedení umocňování druhou mocninou, počet modulárních násobení požadovaných pro exponenta E je log2 E + hmotnost (E). To je důvod, proč hodnota veřejného klíče E použito v RSA je typicky zvolena jako řada s nízkou Hammingovou hmotností.
- Hammingova váha určuje délky cesty mezi uzly v Chord distribuované hash tabulky.[10]
- IrisCode vyhledávání v biometrických databázích se obvykle provádějí výpočtem Hammingova vzdálenost ke každému uloženému záznamu.
- v počítačové šachy programy využívající a bitboard Hammingova váha bitboardu udává počet dílků daného typu zbývajících ve hře nebo počet čtverců hracího plánu ovládaných dílky jednoho hráče, a je proto důležitým pojmem přispívajícím k hodnotě pozice.
- Hammingovu váhu lze použít k efektivnímu výpočtu najít první sadu pomocí identity ffs (x) = pop (x ^ (x-1)). To je užitečné na platformách, jako je SPARC které mají hardwarové instrukce Hammingovy váhy, ale žádný hardware nenajde první instrukci.[11][1]
- Operaci Hammingovy váhy lze interpretovat jako převod z unární číselná soustava na binární čísla.[12]
- Při provádění některých stručné datové struktury jako bitové vektory a wavelet stromy.
Efektivní implementace
Počet obyvatel a bitstring je často potřeba v kryptografii a dalších aplikacích. The Hammingova vzdálenost dvou slov A a B lze vypočítat jako Hammingovu hmotnost A xor B.[1]
Problém, jak jej efektivně implementovat, byl široce studován. Jedna operace pro výpočet nebo paralelní operace na bitových vektorech jsou k dispozici u některých procesorů. Pro procesory, které tyto funkce nemají, jsou nejlepší známá řešení založená na přidávání počtů ve stromovém vzoru. Například k spočítání počtu 1 bitů v 16bitovém binárním čísle a = 0110 1100 1011 1010 lze provést tyto operace:
Výraz | Binární | Desetinný | Komentář | |||||||
---|---|---|---|---|---|---|---|---|---|---|
A | 01 | 10 | 11 | 00 | 10 | 11 | 10 | 10 | 27834 | Původní číslo |
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 | Každý další bit z 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 | Zbývající bity z a |
c = b0 + b1 | 01 | 01 | 10 | 00 | 01 | 10 | 01 | 01 | 1, 1, 2, 0, 1, 2, 1, 1 | Počet 1 s v každém 2-bitovém řezu a |
d0 = (c >> 0) & 0011 0011 0011 0011 | 0001 | 0000 | 0010 | 0001 | 1, 0, 2, 1 | Každý další počet od c | ||||
d2 = (c >> 2) & 0011 0011 0011 0011 | 0001 | 0010 | 0001 | 0001 | 1, 2, 1, 1 | Zbývající počty od c | ||||
e = d0 + d2 | 0010 | 0010 | 0011 | 0010 | 2, 2, 3, 2 | Počet 1 s v každém 4bitovém řezu a | ||||
f0 = (e >> 0) & 00001111 00001111 | 00000010 | 00000010 | 2, 2 | Každý další počet od e | ||||||
f4 = (e >> 4) & 00001111 00001111 | 00000010 | 00000011 | 2, 3 | Zbývající počty od e | ||||||
g = f0 + f4 | 00000100 | 00000101 | 4, 5 | Počet 1 s v každém 8bitovém řezu a | ||||||
h0 = (g >> 0) & 0000000011111111 | 0000000000000101 | 5 | Každý další počet od g | |||||||
h8 = (g >> 8) & 0000000011111111 | 0000000000000100 | 4 | Zbývající počty od g | |||||||
i = h0 + h8 | 0000000000001001 | 9 | Počet 1 s v celém 16bitovém slově |
Tady jsou operace jako v Programovací jazyk C., tak X >> Y
znamená posunout X doprava o Y bity, X & Y znamená bitový AND X a Y, a + je obyčejný doplněk. Nejlepší algoritmy známé pro tento problém jsou založeny na konceptu ilustrovaném výše a jsou uvedeny zde:[1]
// typy a konstanty použité v níže uvedených funkcích// uint64_t je nepodepsaný 64bitový celočíselný typ proměnné (definovaný ve verzi C99 jazyka C)konst uint64_t m1 = 0x5555555555555555; // binární: 0101 ...konst uint64_t m2 = 0x3333333333333333; // binární: 00110011 ..konst uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // binární: 4 nuly, 4 jedničky ...konst uint64_t m8 = 0x00ff00ff00ff00ff; // binární: 8 nul, 8 jedniček ...konst uint64_t m16 = 0x0000ffff0000ffff; // binární: 16 nul, 16 jedniček ...konst uint64_t m32 = 0x00000000ffffffff; // binární: 32 nul, 32 jedničekkonst uint64_t h01 = 0x0101010101010101; // součet 256 k síle 0,1,2,3 ...// Toto je naivní implementace, ukázaná pro srovnání,// a pomoci pochopit lepší funkce.// Tento algoritmus používá 24 aritmetických operací (shift, add a).int popcount64a(uint64_t X){ X = (X & m1 ) + ((X >> 1) & m1 ); // do těchto 2 bitů vloží počet každých 2 bitů X = (X & m2 ) + ((X >> 2) & m2 ); // do těchto 4 bitů vložte počet každých 4 bitů X = (X & m4 ) + ((X >> 4) & m4 ); // vloží počet každých 8 bitů do těchto 8 bitů X = (X & m8 ) + ((X >> 8) & m8 ); // vloží počet každých 16 bitů do těchto 16 bitů X = (X & m16) + ((X >> 16) & m16); // vloží počet každých 32 bitů do těchto 32 bitů X = (X & m32) + ((X >> 32) & m32); // vloží počet každých 64 bitů do těchto 64 bitů vrátit se X;}// Toto používá méně aritmetických operací než jakékoli jiné známé // implementace na strojích s pomalým množením.// Tento algoritmus používá 17 aritmetických operací.int popcount64b(uint64_t X){ X -= (X >> 1) & m1; // do těchto 2 bitů vloží počet každých 2 bitů X = (X & m2) + ((X >> 2) & m2); // do těchto 4 bitů vložte počet každých 4 bitů X = (X + (X >> 4)) & m4; // vloží počet každých 8 bitů do těchto 8 bitů X += X >> 8; // vloží počet každých 16 bitů do svých nejnižších 8 bitů X += X >> 16; // vloží počet každých 32 bitů do svých nejnižších 8 bitů X += X >> 32; // vloží počet každých 64 bitů do svých nejnižších 8 bitů vrátit se X & 0x7f;}// Toto používá méně aritmetických operací než jakékoli jiné známé // implementace na strojích s rychlým množením.// Tento algoritmus používá 12 aritmetických operací, z nichž jedna je násobení.int popcount64c(uint64_t X){ X -= (X >> 1) & m1; // do těchto 2 bitů vloží počet každých 2 bitů X = (X & m2) + ((X >> 2) & m2); // do těchto 4 bitů vložte počet každých 4 bitů X = (X + (X >> 4)) & m4; // vloží počet každých 8 bitů do těchto 8 bitů vrátit se (X * h01) >> 56; // vrací levých 8 bitů x + (x << 8) + (x << 16) + (x << 24) + ... }
Výše uvedené implementace mají nejlepší chování v nejhorším případě ze všech známých algoritmů. Když se však očekává, že hodnota bude mít několik nenulových bitů, může být místo toho efektivnější použít algoritmy, které tyto bity počítají jeden po druhém. Jak popsal Wegner v roce 1960,[13] the bitové AND z X s X - 1 se liší od X pouze při vynulování nejméně významného nenulového bitu: odečtení 1 změní řetězec nejvíce vpravo 0 s na 1 s a změní pravý 1 na 0. X původně měl n bity, které byly 1, pak až poté n iterace této operace, X bude snížena na nulu. Na tomto principu je založena následující implementace.
// To je lepší, když většina bitů v x je 0// Toto je algoritmus funguje stejně pro všechny velikosti dat.// Tento algoritmus používá 3 aritmetické operace a 1 srovnání / větev na „1“ bit v x.int popcount64d(uint64_t X){ int počet; pro (počet=0; X; počet++) X &= X - 1; vrátit se počet;}
Pokud je povoleno větší využití paměti, můžeme vypočítat Hammingovu váhu rychleji než výše uvedené metody. S neomezenou pamětí bychom mohli jednoduše vytvořit velkou vyhledávací tabulku Hammingovy hmotnosti každého 64bitového celého čísla. Pokud můžeme uložit vyhledávací tabulku Hammingovy funkce každého 16bitového celého čísla, můžeme provést následující výpočet Hammingovy váhy každého 32bitového celého čísla.
statický uint8_t wordbits[65536] = { / * bitové účty celých čísel 0 až 65535, včetně * / };// Tento algoritmus používá 3 aritmetické operace a 2 čtení paměti.int popcount32e(uint32_t X){ vrátit se wordbits[X & 0xFFFF] + wordbits[X >> 16];}
// Volitelně lze pomocí této funkce vyplnit tabulku wordbits []int popcount32e_init(prázdnota){ uint32_t i; uint16_t X; int počet; pro (i=0; i <= 0xFFFF; i++) { X = i; pro (počet=0; X; počet++) // vypůjčené od popcount64d () výše X &= X - 1; wordbits[i] = počet; }}
Muła a kol.[14] ukázaly, že vektorizovaná verze popcount64b může běžet rychleji než vyhrazené pokyny (např. popcnt na procesorech x64).
Jazyková podpora
Některé kompilátory jazyka C poskytují vnitřní funkce, které poskytují zařízení pro počítání bitů. Například, GCC (od verze 3.4 v dubnu 2004) obsahuje integrovanou funkci __builtin_popcount
který použije instrukci procesoru, pokud je k dispozici, nebo efektivní implementaci knihovny jinak.[15] LLVM-GCC zahrnoval tuto funkci od verze 1.5 v červnu 2005.[16]
v C ++ STL, datová struktura bitového pole bitová sada
má počet()
metoda, která počítá počet bitů, které jsou nastaveny. v C ++ 20, nová hlavička <bit>
byla přidána obsahující funkce std :: popcount
a std :: has_single_bit
, přičemž argumenty nepodepsaných celočíselných typů.
V Javě je rozšiřitelná datová struktura bitového pole BitSet
má BitSet.cardinality ()
metoda, která počítá počet bitů, které jsou nastaveny. Kromě toho existují Integer.bitCount (int)
a Long.bitCount (dlouhý)
funkce pro počítání bitů v primitivních 32bitových a 64bitových celých číslech. Také BigInteger
třída integer libovolné přesnosti má také a BigInteger.bitCount ()
metoda, která počítá bity.
v Krajta, int
typ má bit_count ()
metoda spočítat počet nastavených bitů. Tato funkce je nová v Pythonu 3.10, jehož vydání je naplánováno na rok 2021.[17]
v Společný Lisp, funkce logcount, zadaná nezáporné celé číslo, vrátí počet 1 bitů. (U záporných celých čísel vrací počet 0 bitů v zápisu doplňku 2.) V obou případech může být celé číslo BIGNUM.
Začíná v GHC 7,4, Haskell základní balíček má popCount
funkce dostupná u všech typů, které jsou instancemi Bity
třída (k dispozici od Data.Bits
modul).[18]
MySQL verze SQL jazyk poskytuje BIT_COUNT ()
jako standardní funkce.[19]
Fortran 2008 má standardní, vnitřní, elementární funkci popcnt
vrácení počtu nenulových bitů v rámci celého čísla (nebo celočíselného pole).[20]
Některé programovatelné vědecké kapesní kalkulačky obsahují speciální příkazy pro výpočet počtu nastavených bitů, např. #B
na HP-16C[3][21] a WP 43S,[22][23] #BITS
[24][25] nebo BITSUM
[26][27] na emulátorech HP-16C a nBITS
na WP 34S.[28][29]
FreePascal implementuje popcnt od verze 3.0.[30]
Podpora procesorů
- The IBM STRETCH počítač v 60. letech vypočítal počet nastavených bitů a také počet úvodních nul jako vedlejší produkt všech logických operací.[1]
- Cray superpočítače na začátku uváděly počet obyvatel strojová instrukce, říká se, že o to byla výslovně požádána vláda USA Národní bezpečnostní agentura pro dešifrování aplikace.[1]
- Některý z Control Data Corporation (CDC) Cyber 70/170 sériové stroje obsahovaly instrukci o počtu obyvatel; v KOMPAS, tato instrukce byla kódována jako
CXi
. - 64-bit SPARC architektura verze 9 definuje a
POPC
návod,[11][1] ale většina implementací to neimplementuje, což vyžaduje emulaci operačního systému.[31] - Donald Knuth modelový počítač MMIX který nahradí SMĚS ve své knize Umění počítačového programování má
SADD
instrukce od roku 1999.SADD a, b, c
spočítá všechny bity, které jsou 1 v ba 0 v c, a zapíše výsledek do a. - Compaq je Alfa 21264A, vydaný v roce 1999, byl prvním designem CPU řady Alpha, který měl rozšíření počtu (
CIX
). - Analogová zařízení ' Blackfin procesory mají
JEN
instrukce k provedení počtu 32bitových populací.[32] - AMD je Barcelona architektura představila pokročilou bitovou manipulaci (ABM) JE zavedení
POPCNT
instrukce jako součást SSE4a rozšíření v roce 2007. - Intel Core procesory představily a
POPCNT
instrukce s SSE4.2 instrukční sada rozšíření, první dostupné v a Nehalem -na základě Jádro i7 procesor, vydané v listopadu 2008. - The ARM architektura představil
VCNT
instrukce jako součást Pokročilé SIMD (NEON ) rozšíření. - The RISC-V architektura představila
PCNT
instrukce jako součást rozšíření Bit Manipulation (B).[33]
Viz také
Reference
- ^ A b C d E F G Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2. vyd.). Addison Wesley - Pearson Education, Inc. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
- ^ Knuth, Donald Ervin (2009). "Bitové triky a techniky; Binární rozhodovací diagramy". Umění počítačového programování. Svazek 4, Fascicle 1. Addison – Wesley Professional. ISBN 0-321-58050-8. (Pozn. Návrh Fascicle 1b k dispozici ke stažení.)
- ^ A b Příručka majitele počítačového vědce Hewlett-Packard HP-16C (PDF). Společnost Hewlett-Packard Company. Duben 1982. 00016-90001. Archivováno (PDF) od původního dne 2017-03-28. Citováno 2017-03-28.
- ^ [1], napsáno ve Fōrmulæ. Fōrmulæ wiki. Citováno 2019-09-30.
- ^ Řešení úkolu Počet obyvatel. Citováno 2019-09-30.
- ^ Rosettský kód. Citováno 2019-09-30.
- ^ Thompson, Thomas M. (1983). Od kódů pro opravu chyb přes balení koulí až po jednoduché skupiny. Matematické monografie Carus č. 21. Matematická asociace Ameriky. str. 33.
- ^ Glaisher, James Whitbread Lee (1899). „O zbytku koeficientu binomické věty vzhledem k primárnímu modulu“. Čtvrtletní deník čisté a aplikované matematiky. 30: 150–156. (Pozn. Viz zejména poslední odstavec str. 156.)
- ^ Reed, Irving Stoy (1954). "Třída kódů opravujících více chyb a schéma dekódování". Profesionální skupina IRE pro teorii informací. Institute of Radio Engineers (HNĚV). PGIT-4: 38–49.
- ^ Stoica, I .; Morris, R .; Liben-Nowell, D .; Karger, D. R .; Kaashoek, M. F .; Dabek, F .; Balakrishnan, H. (únor 2003). „Chord: škálovatelný protokol vyhledávání peer-to-peer pro internetové aplikace“. Transakce IEEE / ACM v síti. 11 (1): 17–32.
Sekce 6.3: „Obecně platí, že počet prstů, které musíme sledovat, bude počet těch v binární reprezentaci vzdálenosti od uzlu k dotazu.“
- ^ A b SPARC International, Inc. (1992). "A.41: Počet obyvatel. Poznámka k programování". Manuál architektury SPARC: verze 8 (Verze 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. str.231. ISBN 0-13-825001-4.
- ^ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (eds.). "Zaznamenat propojení podle bitového vzoru". Informatika a statistika - desáté výroční sympozium o rozhraní. Zvláštní publikace NBS. Americké ministerstvo obchodu / Národní úřad pro standardy. 503: 146–156.
- ^ Wegner, Peter (Květen 1960). "Technika počítání jedniček v binárním počítači". Komunikace ACM. 3 (5): 322. doi:10.1145/367236.367286.
- ^ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (leden 2018). Msgstr "Rychlejší počet obyvatel pomocí pokynů AVX2". Počítačový deník. 61 (1). arXiv:1611.07612. doi:10.1093 / comjnl / bxx046.
- ^ „Poznámky k verzi GCC 3.4“. Projekt GNU.
- ^ „Poznámky k verzi LLVM 1.5“. Projekt LLVM.
- ^ „Co je nového v Pythonu 3.10“. python.org.
- ^ „Poznámky k verzi GHC 7.4.1“. Dokumentace GHC.
- ^ „Kapitola 12.11. Bitové funkce - referenční příručka MySQL 5.0“.
- ^ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Vysvětlil moderní Fortran. Oxford University Press. str. 380. ISBN 0-19-960142-9.
- ^ Schwartz, Jake; Grevelle, Rick (2003-10-20) [1993]. Knihovna emulátorů HP16C pro HP48S / SX. 1,20 (1. vyd.). Citováno 2015-08-15. (Pozn. Tato knihovna funguje také na HP 48G /GX /G +. Kromě sady funkcí HP-16C tento balíček podporuje také výpočty pro binární, osmičkové a šestnáctkové soustavy čísla s plovoucí desetinnou čárkou v věděcký zápis kromě obvyklých desetinných čísel s plovoucí desetinnou čárkou.)
- ^ Bonin, Walter (2019) [2015]. Uživatelská příručka WP 43S (PDF). 0,12 (vydání ed.). str. 135. ISBN 978-1-72950098-9. ISBN 1-72950098-6. Citováno 2019-08-05. [2] [3] (314 stránek)
- ^ Bonin, Walter (2019) [2015]. Referenční příručka WP 43S (PDF). 0,12 (vydání ed.). str. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. ISBN 1-72950106-0. Citováno 2019-08-05. [4] [5] (271 stránek)
- ^ Martin, Ángel M .; McClure, Greg J. (05.09.2015). „Emulační modul HP16C pro HP-41CX - Uživatelská příručka a QRG“ (PDF). Archivováno (PDF) z původního dne 2017-04-27. Citováno 2017-04-27. (Pozn. Kromě HP-16C funkce nastavit tuto vlastní knihovnu pro HP-41CX rozšiřuje funkčnost kalkulačky o dalších 50 funkcí.)
- ^ Martin, Ángel M. (07.09.2015). „HP-41: New HP-16C Emulator available“. Archivováno z původního dne 2017-04-27. Citováno 2017-04-27.
- ^ Thörngren, Håkan (10.01.2017). "Dokumentace Beruška" (vydání 0A ed.). Citováno 2017-01-29. [6]
- ^ „Nový modul HP-41 k dispozici: Beruška“. 2017-01-10. Archivováno z původního dne 2017-01-29. Citováno 2017-01-29.
- ^ Dale, Paul; Bonin, Walter (2012) [2008]. „Manuál uživatele WP 34S“ (PDF) (3.1 ed.). Citováno 2017-04-27.
- ^ Bonin, Walter (2015) [2008]. Uživatelská příručka WP 34S (3,3 ed.). ISBN 978-1-5078-9107-0.
- ^ "Popcnt dokumentace zdarma Pascal". Citováno 2019-12-07.
- ^ „JDK-6378821: bitCount () by měl používat POPC na procesorech SPARC a AMD + 10h“. Databáze chyb Java. 2006-01-30.
- ^ Odkaz na instrukční sadu černých ryb (Předběžné vydání.). Analogová zařízení. 2001. s. 8–24. Číslo dílu 82-000410-14.
- ^ Vlk, Clifford (2019-03-22). "RISC-V" B "rozšíření bitové manipulace pro RISC-V, koncept v0.37" (PDF). Github.
Další čtení
- Schroeppel, Richard C.; Orman, Hilarie K. (1972-02-29). "sestavení". HAKMEM. Beeler, Michael; Gosper, Ralph William; Schroeppel, Richard C. (zpráva). Laboratoř umělé inteligence, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. Memo AI MIT 239. (Položka 169: Kód sestavy počtu obyvatel pro PDP / 6-10.)
externí odkazy
- Agregované magické algoritmy. Optimalizovaný počet obyvatel a další algoritmy vysvětlené ukázkovým kódem.
- Bit Twiddling Hacks Je nastaveno několik algoritmů s kódem pro počítání bitů.
- Nezbytné a dostatečné - Damien Wintour - Má kód v C # pro různé implementace Hamming Weight.
- Nejlepší algoritmus pro počítání počtu nastavených bitů v 32bitovém celém čísle? - Přetečení zásobníku