Najít první sadu - Find first set
V počítači software a hardware, najít první sadu (ffs) nebo najít první je bitová operace to, vzhledem k nepodepsané strojové slovo,[pozn. 1] označuje index nebo pozici nejméně významného bitu nastaveného na jednu ve slově počítajícího z nejméně významné bitové pozice. Téměř ekvivalentní operace je počítat koncové nuly (ctz) nebo počet koncových nul (ntz), který počítá počet nulových bitů následujících po nejméně významném jednom bitu. Doplňková operace, která najde index nebo pozici nejvýznamnějšího nastaveného bitu, je základna protokolu 2, tzv. protože počítá binární logaritmus ⌊Log2(X)⌋.[1] Tohle je úzce souvisí na počítat úvodní nuly (clz) nebo počet úvodních nul (nlz), který počítá počet nula bitů před nejvýznamnějším jedním bitem.[pozn. 2]Existují dvě běžné varianty nálezu první sady, POSIX definice, která začíná indexování bitů na 1,[2] zde označené ffs a varianta, která začíná indexování bitů na nulu, což je ekvivalentní ctz a bude tedy nazývána tímto jménem.
Nejmodernější CPU architektury instrukční sady poskytnout jeden nebo více z nich jako operátory hardwaru; softwarová emulace je obvykle poskytována všem, kteří nejsou k dispozici, ať už jako vnitřní kompilátor nebo v systémových knihovnách.
Příklady
Vzhledem k následujícímu 32bitovému slovu:
- 0000 0000 0000 0000 1000 0000 0000 1000
Operace počítání koncových nul by vrátila 3, zatímco operace počítání počátečních nul vrátí 16. Počítání operací počátečních nul závisí na velikosti slova: pokud by bylo toto 32bitové slovo zkráceno na 16bitové slovo, počet počátečních nul by vrátil nulu . Operace hledání první sady vrátí hodnotu 4, což značí 4. pozici zprava. Základna protokolu 2 je 15.
Podobně vzhledem k následujícímu 32bitovému slovu je bitová negace výše uvedeného slova:
- 1111 1111 1111 1111 0111 1111 1111 0111
Operace spočítání koncových jednotek by vrátila 3, operace spočítání hlavních by vrátila 16 a nález první nulové operace ffz by vrátil 4.
Pokud je slovo nula (nejsou nastaveny žádné bity), počítání počátečních nul a počítání koncových nul vrátí počet bitů ve slově, zatímco ffs vrátí nulu. Jak implementace základny 2 protokolu, tak nulové implementace sady find first set obecně vrátí nedefinovaný výsledek pro nulové slovo.
Hardwarová podpora
Mnoho architektur zahrnuje instrukce k rychlému provedení vyhledání první sady a / nebo souvisejících operací uvedených níže. Nejběžnější operací je počet úvodních nul (clz), pravděpodobně proto, že všechny ostatní operace lze z hlediska toho efektivně implementovat (viz Vlastnosti a vztahy ).
Plošina | Mnemotechnická pomůcka | název | Šířky operandů | Popis | Při aplikaci do 0 |
---|---|---|---|---|---|
PAŽE (ARMv5T architektura a novější ) až na Cortex-M0 / M0 + / M1 / M23 | clz[3] | Počítejte přední nuly | 32 | clz | 32 |
PAŽE (ARMv8-A architektura ) | clz | Počítejte přední nuly | 32, 64 | clz | Šířka operandu |
AVR32 | clz[4] | Počítejte přední nuly | 32 | clz | 32 |
DEC Alpha | ctlz[5] | Počítejte přední nuly | 64 | clz | 64 |
cttz[5] | Počítat koncové nuly | 64 | ctz | 64 | |
Intel 80386 a později | bsf[6] | Bit Scan Forward | 16, 32, 64 | ctz | Nedefinováno; nastaví nulový příznak |
bsr[6] | Zpětné skenování bitů | 16, 32, 64 | Základna protokolu 2 | Nedefinováno; nastaví nulový příznak | |
x86 vedlejší BMI1 nebo ABM | lzcnt[7] | Počítejte přední nuly | 16, 32, 64 | clz | Šířka operandu; sady nesou vlajku |
x86 vedlejší BMI1 | tzcnt[8] | Počítat koncové nuly | 16, 32, 64 | ctz | Šířka operandu; sady nesou vlajku |
Itanium | clz[9] | Počítejte přední nuly | 64 | clz | 64 |
MIPS | clz[10][11] | Počítejte přední nuly ve Wordu | 32, 64 | clz | Šířka operandu |
clo[10][11] | Počítejte přední ve Wordu | 32, 64 | clo | Šířka operandu | |
Motorola 68020 a později | bfffo[12] | Najděte první v bitovém poli | Libovolný | Základna protokolu 2 | Posun pole + šířka pole |
PDP-10 | jffo | Skočte, pokud najdete první | 36 | ctz | 0; žádná operace |
NAPÁJENÍ /PowerPC /Napájení ISA | cntlz / cntlzw / cntlzd[13] | Počítejte přední nuly | 32, 64 | clz | Šířka operandu |
Power ISA 3.0 a novější | cnttzw / cnttzd[14] | Počítat koncové nuly | 32, 64 | ctz | Šířka operandu |
RISC-V (Rozšíření „B“) (koncept) | clz[15] | Počítejte přední nuly | 32, 64 | clz | Šířka operandu |
ctz[15] | Počítat koncové nuly | 32, 64 | ctz | Šířka operandu | |
SPARC Oracle Architecture 2011 a novější | lzcnt (synonymum: lzd)[16] | Přední nulový počet | 64 | clz | 64 |
VAX | ffs[17] | Najít první sadu | 0–32 | ctz | Šířka operandu; nastaví nulový příznak |
IBM z / Architecture | flogr[18] | Najděte jednu úplně vlevo | 64 | clz | 64 |
vclz[18] | Počet vektorů vedoucích nuly | 8, 16, 32, 64 | clz | Šířka operandu | |
vctz[18] | Vektorové počítání koncových nul | 8, 16, 32, 64 | ctz | Šířka operandu |
Na některých platformách Alpha jsou CTLZ a CTTZ emulovány v softwaru.
Podpora nástrojů a knihoven
Řada dodavatelů kompilátorů a knihoven dodává vnitřní funkce kompilátoru nebo funkce knihovny k provádění vyhledání první sady a / nebo souvisejících operací, které jsou často implementovány z hlediska výše uvedených hardwarových pokynů:
Nástroj / knihovna | název | Typ | Typ vstupu | Poznámky | Při aplikaci do 0 |
---|---|---|---|---|---|
POSIX.1 vyhovující libc 4,3BSD libc OS X 10.3 libc[2][19] | ffs | Funkce knihovny | int | Zahrnuje glibc. POSIX nedodává doplňkovou základnu protokolu 2 / clz. | 0 |
FreeBSD 5,3 libc OS X 10.4 libc[19] | ffsl fls flsl | Funkce knihovny | int, dlouho | fls ("najít poslední sadu") počítá (základ protokolu 2) + 1. | 0 |
FreeBSD 7,1 libc[20] | ffsll flsll | Funkce knihovny | dlouho dlouho | 0 | |
GCC 3.4.0[21][22] Zvonit 5.x[23][24] | __builtin_ffs [l, ll, imax] __builtin_clz [l, ll, imax] __builtin_ctz [l, ll, imax] | Integrované funkce | nepodepsaný int, bez znaménka, nepodepsaný dlouhý dlouhý, uintmax_t | Dokumentace GCC považuje výsledek za nedefinovaný clz a ctz na 0. | 0 (ffs) |
Vizuální studio 2005 | _BitScanForward [25]_BitScanReverse [26] | Vnitřní kompilátor | bez znaménka, nepodepsaný __int64 | Samostatná návratová hodnota označuje nulový vstup | Nedefinováno |
Vizuální studio 2008 | __lzcnt [27] | Vlastní překladač | bez znaménka krátký, nepodepsaný int, nepodepsaný __int64 | Spoléhá se na hardwarovou podporu instrukce lzcnt zavedené v BMI1 nebo ABM. | Šířka operandu |
Překladač Intel C ++ | _bit_scan_forward _bit_scan_reverse [28][29] | Vnitřní kompilátor | int | Nedefinováno | |
NVIDIA CUDA[30] | __clz | Funkce | 32bitová, 64bitová | Zkompiluje se méně pokynů na Řada GeForce 400 | 32 |
__ffs | 0 | ||||
LLVM | llvm.ctlz. * llvm.cttz. * [31] | Vnitřní | 8, 16, 32, 64, 256 | Montážní jazyk LLVM | Šířka operandu, pokud je druhý argument 0; jinak nedefinováno |
GHC 7,10 (základ 4,8), v Data.Bits [Citace je zapotřebí ] | countLeadingZeros countTrailingZeros | Funkce knihovny | FiniteBits b => b | Haskell programovací jazyk | Šířka operandu |
C ++ 20 standardní knihovna, v záhlaví <bit> [32][33] | bit_ceil bit_floor bit_width countl_zero countl_one countr_zero countr_one | Funkce knihovny | nepodepsaný znak, bez znaménka krátký, nepodepsaný int, bez znaménka, nepodepsáno dlouho dlouho |
Vlastnosti a vztahy
Pokud jsou bity označeny od 1 (což je konvence použitá v tomto článku), pak počítat koncové nuly a najít operace první sady souvisí s ctz (X) = ffs (X) − 1 (kromě případů, kdy je vstup nulový). Pokud jsou bity označeny počínaje od 0, pak spočítat koncové nuly a najít první sadu jsou přesně ekvivalentní operace. Dáno w bitů na slovo, log2 lze snadno vypočítat z clz a naopak log2(X) = w - 1 - clz (X).
Jak je ukázáno ve výše uvedeném příkladu, operace hledání první nuly, počítání úvodních a počítání koncových jednotek lze implementovat negováním vstupu a použitím funkce Najít první sadu, počítat úvodní nuly a počítat koncové nuly. Opak je také pravdou.
Na platformách s efektivním protokolem2 úkon[který? ] jako M68000, ctz lze vypočítat pomocí:
- ctz (X) = log2(X & −x)
kde & označuje bitové AND a −x označuje doplněk dvou z X. Výraz X & −x vymaže všechny kromě nejméně významných 1 bit, takže nejvýznamnější a nejméně významné 1 bit jsou stejné.
Na platformách s efektivním počtem vedoucích nulových operací, jako jsou ARM a PowerPC, ffs lze vypočítat pomocí:
- ffs (X) = w - clz (X & −x).
Naopak na strojích bez log2 nebo clz operátoři, clz lze vypočítat pomocí ctz, i když neefektivně:
- clz = w - ctz (2⌈Log2(X)⌉) (což závisí na ctz vracející se w pro nulový vstup)
Na platformách s efektivním Hammingova hmotnost (počet obyvatel) operace jako SPARC je POPC
[34][35] nebo Blackfin je JEN
,[36] tady je:
- ctz (X) = popcount ((X & −x) − 1),[37][38]
- ffs (X) = počet obyvatel (X ^ ~−X)[34]
- clz = 32 - počet obyvatel (2⌈Log2(X)⌉ − 1)
kde ^ označuje bitové výlučné OR nebo ~ označuje bitovou negaci.
Inverzní problém (daný i, vyrábět X takhle ctz (X) = i) lze vypočítat s posunem doleva (1 << i).
Najít první sadu a související operace lze rozšířit na libovolně velké bitová pole přímým způsobem tak, že začínáte na jednom konci a pokračujete, dokud slovo není nenulové (pro ffs, ctz, clz) nebo ne vše (pro ffz, clo, cto). Stromová datová struktura, která rekurzivně používá bitmapy ke sledování, která slova jsou nenulová, to může urychlit.
Emulace softwaru
Většina CPU datovaných od konce 80. let 20. století má bitové operátory pro ffs nebo ekvivalent, ale několik moderních, jako některé ze sérií ARM-Mx, nikoli. Místo hardwarových operátorů pro ffs, clz a ctz je software může emulovat pomocí posunů, celočíselných aritmetických a bitových operátorů. Existuje několik přístupů v závislosti na architektuře CPU a v menší míře na sémantice programovacího jazyka a kvalitě generování kódu kompilátoru. Přístupy lze volně popsat jako lineární vyhledávání, binární vyhledávání, vyhledávání + vyhledávání v tabulce, de Bruijnova násobení, metody převodu s plovoucí desetinnou čárkou / exponentového extraktu a metody bitových operátorů (bez větví) Existují kompromisy mezi dobou provedení a úložným prostorem, jakož i přenositelností a účinností.
Softwarové emulace jsou obvykle deterministické. Vrátí definovaný výsledek pro všechny vstupní hodnoty; zejména výsledek pro vstup všech nulových bitů je obvykle 0 pro ffs a bitová délka operandu pro ostatní operace.
Pokud má jeden hardwarový clz nebo ekvivalent, ctz lze efektivně vypočítat pomocí bitových operací, ale obrácení není pravdivé: clz není efektivní vypočítat v nepřítomnosti hardwarového operátora.
2n
Funkce 2⌈Log2(X)⌉ (zaokrouhlit nahoru na nejbližší sílu dvou) pomocí posunů a bitových OR[39] není efektivní počítat jako v tomto 32bitovém příkladu a ještě neefektivnější, pokud máme 64bitový nebo 128bitový operand:
funkce pow2 (x): -li x = 0 návrat neplatný // neplatný je implementace definována (není v [0,63]) x ← x - 1 pro každého y v {1, 2, 4, 8, 16}: x ← x | (x >> y) vrátit se x + 1
FFS
Protože ffs = ctz + 1 (POSIX) nebo ffs = ctz (další implementace), lze použít použitelné algoritmy pro ctz, s možným posledním krokem přidání 1 k výsledku a vrácení 0 místo délky operandu pro vstup všechny nulové bity.
CTZ
Kanonický algoritmus je nuly počítání smyček začínající na LSB, dokud nenarazí na 1-bit:
funkce ctz1 (x) -li x = 0 vrátit se w t ← 1 r ← 0 zatímco (x & t) = 0 t ← t << 1 r ← r + 1 vrátit se r
Tento algoritmus provádí O (n) čas a operace a je v praxi nepraktický kvůli velkému počtu podmíněných větví.
Vyhledávací tabulka může eliminovat většinu větví:
tabulka [0..2n-1] = ctz (i) pro i v 0..2n-1funkce ctz2 (x) -li x = 0 vrátit se w r ← 0 smyčka -li (x & (2n-1)) ≠ 0 vrátit se r + tabulka [x & (2n-1)] x ← x >> n r ← r + n
Parametr n je pevná (obvykle 8) a představuje a kompromis v časoprostoru. Smyčka může být také úplně rozvinutý. Ale jako lineární vyhledávání je tento přístup stále O (n) v počtu bitů v operandu.
A binární vyhledávání implementace vyžaduje logaritmický počet operací a poboček, jako v této 32bitové verzi:[40][41]Tomuto algoritmu může pomoci také tabulka, která nahradí spodní tři příkazy „if“ vyhledávací tabulkou 256 položek s použitím prvního nenulového bajtu, který se vyskytuje jako index.
funkce ctz3 (x) -li x = 0 vrátit se 32 n ← 0 -li (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16 -li (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8 -li (x & 0x0000000F) = 0: n ← n + 4, x ← x >> 4 -li (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2 -li (x & 0x00000001) = 0: n ← n + 1 vrátit se n
Pokud má hardware operátor clz, nejúčinnější přístup k výpočtu ctz je takto:
funkce ctz4 (x) x & = -x vrátit se w - (clz (x) + 1)
Algoritmus pro 32bitové ctz používá de Bruijn sekvence postavit a minimální dokonalá hashovací funkce který vylučuje všechny větve.[42][43]Tento algoritmus předpokládá, že výsledek násobení je zkrácen na 32 bitů.
pro i z 0 na 31: tabulka [(0x077CB531 * (1 << i)) >> 27] ← i // tabulka [0..31] inicializovánafunkce ctz5 (x) vrátit se tabulka [((x & -x) * 0x077CB531) >> 27]
Výraz (x & -x) opět izoluje nejméně významný 1 bit. Existuje tedy pouze 32 možných slov, která nepodepsané násobení a posun hash do správné polohy v tabulce. (Tento algoritmus nezpracovává nulový vstup.)
CLZ
Kanonický algoritmus zkoumá jeden bit po druhém počínaje od MSB, dokud není nalezen nenulový bit, jak je znázorněno v tomto příkladu. Provádí se v čase O (n), kde n je bitová délka operandu a není praktickým algoritmem pro obecné použití.
funkce clz1 (x) -li x = 0 vrátit se w t ← 1 << w - 1 r ← 0 zatímco (x & t) = 0 t ← t >> 1 r ← r + 1 vrátit se r
Vylepšení předchozího přístupu opakování zkoumá osm bitů najednou a poté používá 256 (28) vstupní vyhledávací tabulka pro první nenulový bajt. Tento přístup je však stále O (n) v době provádění.
funkce clz2 (x) -li x = 0 vrátit se w t ← 0xff << w - 8 r ← 0 zatímco (x & t) = 0 t ← t >> 8 r ← r + 8 vrátit se r + tabulka [x >> w-8]
Binární vyhledávání může zkrátit dobu provádění na O (log2n):
funkce clz3 (x) -li x = 0 vrátit se 32 n ← 0 -li (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16 -li (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8 -li (x & 0xF0000000) = 0: n ← n + 4, x ← x << 4 -li (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2 -li (x & 0x80000000) = 0: n ← n + 1 vrátit se n
Nejrychlejší přenosné přístupy k simulaci CLZ jsou kombinací binárního vyhledávání a vyhledávání v tabulce: 8bitové vyhledávání v tabulce (28= 256 1bajtových záznamů) může v binárním vyhledávání nahradit spodní 3 větve. 64bitové operandy vyžadují další větev. Lze použít vyhledávání větší šířky, ale maximální praktická velikost tabulky je omezena velikostí datové mezipaměti L1 na moderních procesorech, což je u mnoha 32 kB. Uložení větve je více než kompenzováno latencí Mezipaměť L1 slečna, minout.
Algoritmus podobný de Bruijnovu multiplikaci pro CTZ funguje pro CLZ, ale místo toho, aby izoloval nejvýznamnější bit, zaokrouhlí se na nejbližší celé číslo formy 2n−1 pomocí posunů a bitových OR:[44]
tabulka [0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15 , 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}funkce clz4 (x) pro každého y v {1, 2, 4, 8, 16}: x ← x | (x >> y) vrátit se tabulka [(x * 0x07C4ACDD) >> 27]
U procesorů s hlubokými kanály, jako jsou Prescott a novější procesory Intel, může být rychlejší nahradit větve bitovými operátory AND a OR (i když je vyžadováno mnohem více pokynů), aby se zabránilo vyprázdnění potrubí pro nesprávně předvídané větve (a tyto typy větví jsou neodmyslitelně nepředvídatelné):
funkce clz5 (x) r = (x> 0xFFFF) << 4; x >> = r; q = (x> 0xFF) << 3; x >> = q; r | = q; q = (x> 0xF) << 2; x >> = q; r | = q; q = (x> 0x3) << 1; x >> = q; r | = q; r | = (x >> 1); vrátit se r;
Na platformách, které poskytují hardwarový převod celých čísel na plovoucí desetinnou čárku, lze pole exponentu extrahovat a odečíst od konstanty, aby se vypočítal počet úvodních nul. Jsou nutné opravy, aby se zohlednily chyby zaokrouhlování.[40][45] Konverze s plovoucí desetinnou čárkou může mít značnou latenci. Tato metoda je vysoce nepřenosná a obvykle se nedoporučuje.
int X; int r;svaz { nepodepsaný int u[2]; dvojnásobek d; } t; t.u[LE] = 0x43300000; // LE je 1 pro malý endiant.u[!LE] = X;t.d -= 4503599627370496.0;r = (t.u[LE] >> 20) - 0x3FF; // log2r++; // CLZ
Aplikace
K efektivní implementaci lze použít operaci počátečních nul (clz) normalizace, který kóduje celé číslo jako m × 2E, kde m má svůj nejvýznamnější bit ve známé poloze (například nejvyšší pozici). To lze zase použít k implementaci Newton-Raphsonova divize, provést celé číslo do plovoucí bod konverze v softwaru a dalších aplikacích.[40][46]
Počet úvodních nul (clz) lze použít k výpočtu 32bitového predikátu "x = y" (nula, pokud je pravda, jedna, pokud je nepravda) prostřednictvím identity clz (x - y) >> 5, kde „>>“ je nepodepsaný pravý posun.[47] Může být použit k provádění složitějších bitových operací, jako je nalezení prvního řetězce n 1 bit.[48] Výraz clz (x - y) 1 << (16 - clz (x - 1) / 2) je efektivní počáteční odhad pro výpočet druhé odmocniny 32bitového celého čísla pomocí Newtonova metoda.[49] CLZ může efektivně implementovat nulové potlačení, rychlý komprese dat technika, která kóduje celé číslo jako počet úvodních nulových bajtů spolu s nenulovými bajty.[50] Může také efektivně generovat exponenciálně distribuováno celá čísla převzetím CLZ rovnoměrně náhodně celá čísla.[40]
Základnu protokolu 2 lze použít k předvídání, zda násobení přeteče, protože ⌈Log2(xy) ⌉ ≤ ⌈log2(x) ⌉ + ⌈log2(y) ⌉.[51]
Počet úvodních nul a počet koncových nul lze použít společně k implementaci Gosperův algoritmus detekce smyčky,[52] který může najít období funkce konečného rozsahu s využitím omezených zdrojů.[41]
The binární algoritmus GCD tráví mnoho cyklů odstraňováním koncových nul; toto může být nahrazeno nulou počtu konců (ctz) následovanou posunem. Podobná smyčka se objeví ve výpočtech sekvence krupobití.
A bitové pole lze použít k implementaci a prioritní fronta. V této souvislosti je užitečné najít první sadu (ffs) při efektivní implementaci operace „pop“ nebo „vytáhnout prvek nejvyšší priority“. The Linuxové jádro plánovač v reálném čase interně používá sched_find_first_bit ()
pro tento účel.[53]
Operace počítání koncových nul poskytuje jednoduché optimální řešení Hanojská věž problém: disky jsou očíslovány od nuly a za pohybu k, číslo disku ctz (k) se posune o minimální možnou vzdálenost doprava (podle potřeby krouží dozadu doleva). Může také generovat a Šedý kód převzetím libovolného slova a převrácením bit ctz (k) v kroku k.[41]
Viz také
- Sady instrukcí pro manipulaci s bitem (BMI) pro procesory Intel a AMD x86
- Koncová nula
- Vedoucí nula
- Koncová číslice
- Vedoucí číslice
Poznámky
- ^ Použití bitových operací na jiném než nepodepsaném strojovém slovu může přinést nedefinované výsledky.
- ^ Tyto čtyři operace mají také (mnohem méně běžné) negované verze:
- najít první nulu (ffz), který identifikuje index nejméně významného nulového bitu;
- počítat koncové, který počítá počet jednoho bitu po nejméně významném nulovém bitu.
- počítat vedoucí, který počítá počet 1 bitů před nejvýznamnějším nulovým bitem;
- najít index nejvýznamnějšího nulového bitu, což je obrácená verze souboru binární logaritmus.
Reference
- ^ Anderson. Najděte základnu protokolu 2 celého čísla s MSB N nastaveným v operacích O (N) (zřejmý způsob).
- ^ A b „FFS (3)“. Příručka programátora systému Linux. Archivy jádra Linuxu. Citováno 2012-01-02.
- ^ „Referenční příručka ARM> Obecné pokyny ke zpracování dat ARM> CLZ“. Průvodce sestavovatelem ARM Developer Suite. PAŽE. Citováno 2012-01-03.
- ^ "Dokument architektury AVR32" (PDF) (CORP072610 ed.). Atmel Corporation. 2011. 32000D – 04/201. Archivovány od originál (PDF) dne 2017-10-25. Citováno 2016-10-22.
- ^ A b Referenční příručka architektury Alpha (PDF). Compaq. 2002. str. 4-32, 4-34.
- ^ A b Příručka pro vývojáře softwaru Intel 64 a IA-32 Architectures. Svazek 2A. Intel. str. 3-92–3-97. Objednací číslo 325383.
- ^ AMD64 Architecture Programmer's Manual Volume 3: General Purpose and System Instructions (PDF). 3. Pokročilá mikro zařízení (AMD). 2011. s. 204–205. Publikace č. 24594.
- ^ „AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions“ (PDF). Technologie AMD64 (verze 3.28 ed.). Pokročilá mikro zařízení (AMD). Září 2019 [2013]. Publikace č. 24594. Archivováno (PDF) od původního dne 2019-09-30. Citováno 2014-01-02.
- ^ Příručka pro vývojáře softwaru Intel Itanium Architecture. Svazek 3: Sada instrukcí Intel Itanium. 3. Intel. 2010. str. 3:38. Archivováno od původního dne 26.06.2019.
- ^ A b Architektura MIPS pro programátory. Svazek II-A: Sada instrukcí MIPS32 (Revize 3.02 ed.). MIPS Technologies. 2011. s. 101–102.
- ^ A b Architektura MIPS pro programátory. Svazek II-A: Sada instrukcí MIPS64 (Revize 3.02 ed.). MIPS Technologies. 2011. s. 105, 107, 122, 123.
- ^ Referenční příručka programátoru rodiny M68000 (zahrnuje pokyny CPU32) (PDF) (revize 1 ed.). Motorola. 1992. str. 4-43–4-45. M68000PRM / AD. Archivovány od originál (PDF) dne 8. 12. 2019.
- ^ Frey, Brad. „Kapitola 3.3.11 Logické pokyny pro pevné body“. Kniha architektury PowerPC (Verze 2.02 ed.). IBM. str. 70.
- ^ „Kapitola 3.3.13 Logické pokyny s pevným bodem - Kapitola 3.3.13.1 64bitové logické pokyny s pevným bodem“. Power ISA verze 3.0B. IBM. 95, 98.
- ^ A b Vlk, Clifford (2019-03-22). "RISC-V" B "rozšíření bitové manipulace pro RISC-V" (PDF). Github (Koncept) (v0.37 ed.). Citováno 2020-01-09.
- ^ Oracle SPARC Architecture 2011. Věštec. 2011.
- ^ Referenční příručka architektury VAX (PDF). Digital Equipment Corporation (DEC). 1987. s. 70–71. Archivováno (PDF) z původního dne 2019-09-29. Citováno 2020-01-09.
- ^ A b C „Kapitola 22. Pokyny pro vektorové celé číslo“. Principy fungování IBM z / Architecture (PDF) (Jedenácté vydání.). IBM. Březen 2015. str. 7-219–22-10. SA22-7832-10. Citováno 2020-01-10.
- ^ A b „FFS (3)“. Knihovna vývojářů pro Mac OS X.. Apple, Inc. 1994-04-19. Citováno 2012-01-04.
- ^ „FFS (3)“. Manuál funkcí knihovny FreeBSD. Projekt FreeBSD. Citováno 2012-01-04.
- ^ „Other built-in functions provided by GCC“. Používání GNU Compiler Collection (GCC). Free Software Foundation, Inc. Citováno 2015-11-14.
- ^ „ChangeLog GCC 3.4.0“. GCC 3.4.0. Free Software Foundation, Inc. Citováno 2015-11-14.
- ^ „Clang Language Extensions - kapitola Builtin Functions“. Clang Team. Citováno 2017-04-09.
Clang podporuje řadu vestavěných funkcí knihovny se stejnou syntaxí jako GCC
- ^ "Zdrojový kód Clangu". Tým LLVM, University of Illinois v Urbana-Champaign. Citováno 2017-04-09.
- ^ „_BitScanForward, _BitScanForward64“. Visual Studio 2008: Visual C ++: Základní vlastnosti kompilátoru. Microsoft. Citováno 2018-05-21.
- ^ „_BitScanReverse, _BitScanReverse64“. Visual Studio 2008: Visual C ++: Základní vlastnosti kompilátoru. Microsoft. Citováno 2018-05-21.
- ^ „__lzcnt16, __lzcnt, __lzcnt64“. Visual Studio 2008: Visual C ++: Základní vlastnosti kompilátoru. Microsoft. Citováno 2012-01-03.
- ^ „Průvodce Intel Intrinsics“. Intel. Citováno 2020-04-03.
- ^ Intel C ++ Compiler for Linux Intrinsics Reference. Intel. 2006. s. 21.
- ^ Průvodce programováním NVIDIA CUDA (PDF) (Verze 3.0 ed.). NVIDIA. 2010. str. 92.
- ^ "'llvm.ctlz. * 'Vnitřní,' llvm.cttz. * 'Vnitřní ". Referenční příručka jazyka LLVM. Infrastruktura kompilátoru LLVM. Citováno 2016-02-23.
- ^ Smith, Richard (01.04.2020). Pracovní koncept N4861, standard pro programovací jazyk C ++ (PDF). ISO / IEC. str. 1150–1153. Citováno 2020-05-25.
- ^ "Standardní záhlaví knihovny
" . cppreference.com. Citováno 2020-05-25. - ^ A b SPARC International, Inc. (1992). "A.41: Počet obyvatel. Poznámka k programování" (PDF). Manuál architektury SPARC: verze 8 (Verze 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. str.231. ISBN 978-0-13-825001-0.
- ^ Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2. vyd.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
- ^ 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.
- ^ Dietz, Henry Gordon. „Agregované magické algoritmy“. University of Kentucky. Archivováno od původního dne 2019-10-31.
- ^ Isenberg, Gerd (03.11.2019) [2012]. „BitScanProtected“. Chess Programming Wiki (CPW). Archivováno od původního dne 2020-01-09. Citováno 2020-01-09.
- ^ Anderson. Zaokrouhlete nahoru na další nejvyšší sílu 2.
- ^ A b C d Warren. Kapitola 5-3: Počítání prvních 0.
- ^ A b C Warren. Kapitola 5-4: Počítání koncových 0.
- ^ Leiserson, Charles E.; Prokop, Harald; Randall, Keith H. (07.07.1998). „Použití de Bruijnových sekvencí k indexování čísla 1 v počítačovém slově“ (PDF). MIT Laboratory for Computer Science, Cambridge, MA, USA. Archivováno (PDF) od původního dne 2020-01-09. Citováno 2020-01-09.
- ^ Busch, Philip (01.03.2009) [2009-02-21]. „Computing Trailing Zeros HOWTO“ (PDF). Archivováno (PDF) od originálu 2016-08-01. Citováno 2020-01-09.
- ^ Anderson. Vyhledejte základnu protokolu 2 N-bitového celého čísla v operacích O (lg (N)) pomocí funkce násobení a vyhledávání.
- ^ Anderson. Najděte celočíselnou základnu protokolu 2 celého čísla s 64bitovým plovoucím IEEE.
- ^ Sloss, Andrew N .; Symes, Dominic; Wright, Chris (2004). Příručka vývojáře systému ARM pro návrh a optimalizaci systémového softwaru (1. vyd.). San Francisco, CA, USA: Morgan Kaufmann. 212–213. ISBN 978-1-55860-874-0.
- ^ Warren. Kapitola 2-11: Predikáty srovnání.
- ^ Warren. Kapitola 6-2: Najděte první řetězec 1 bitů dané délky.
- ^ Warren. Kapitola 11-1: Integer Square Root.
- ^ Schlegel, Benjamin; Gemulla, Rainer; Lehner, Wolfgang (Červen 2010). Rychlá komprese celého čísla pomocí pokynů SIMD. Sborník ze šestého mezinárodního semináře o správě dat na novém hardwaru (DaMoN 2010). str. 34–40. CiteSeerX 10.1.1.230.6379. doi:10.1145/1869389.1869394. ISBN 978-1-45030189-3.
- ^ Warren. Kapitola 2-12: Detekce přetečení.
- ^ Gosper, Bille (Duben 1995) [1972-02-29]. Baker, Jr., Henry Givens (vyd.). "Detektor smyčky". HAKMEM (přepsaný a převedený ed.). Cambridge, Massachusetts, USA: Laboratoř umělé inteligence, Massachusetts Institute of Technology (MIT). AI Memo 239, položka 132. Archivováno od originálu dne 10. 10. 2019. Citováno 2020-01-09.
- ^ Aas, Josh (2005-02-17). Pochopení plánovače CPU Linux 2.6.8.1 (PDF). Silicon Graphics, Inc. (SGI). str. 19. Archivováno (PDF) z původního dne 2017-05-19. Citováno 2020-01-09.
Další čtení
- Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2. vyd.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
- Anderson, Sean Eron (2005) [1997]. „Bit Twiddling Hacks“. Stanfordská Univerzita. Archivováno od původního dne 2020-01-08. Citováno 2012-01-03. (Pozn. Uvádí několik účinných implementací jazyka C pro veřejnou doménu počítat koncové nuly a základna protokolu 2.)
externí odkazy
- Průvodce Intel Intrinsics
- Chess Programming Wiki: BitScan: Podrobné vysvětlení řady implementačních metod pro ffs (nazývané LS1B) a log base 2 (nazývané MS1B).