Zoek eerste set - Find first set

In computer software en hardware, vindt eerste set ( FFS ) of voorbeeld eerste is een bit operatiecode die, gegeven een unsigned machinewoord , duidt de index of de positie van het minst significante bit op één in het woord gerekend vanaf het minst significante bit positie. Een bijna equivalente bewerking is het tellen van volgnullen ( ctz ) of het aantal volgnullen ( ntz ), dat het aantal nulbits telt dat volgt op het minst significante één bit. De complementaire bewerking die de index of positie van de meest significante set bit vindt, is log grondtal 2 , zo genoemd omdat het de binaire logaritme ⌊log ₂ (x) ⌋ berekent . Dit hangt nauw samen met het tellen van voorloopnullen ( clz ) of het aantal voorloopnullen ( nlz ), waarbij het aantal nulbits wordt geteld voorafgaand aan de meest significante bit. Er zijn twee veelvoorkomende varianten van find first set, de POSIX- definitie die begint met het indexeren van bits bij 1, hierin aangeduid als ffs, en de variant die begint met indexeren van bits bij nul, wat gelijk is aan ctz en dus met die naam zal worden genoemd.

De meeste moderne CPU- instructiesetarchitecturen bieden een of meer van deze als hardware-operators; software-emulatie wordt meestal geleverd voor degenen die niet beschikbaar zijn, hetzij als compiler-intrinsiek of in systeembibliotheken.

Voorbeelden

Gegeven het volgende 32-bits woord:

0000 0000 0000 0000 1000 0000 0000 1000

De bewerking met voorloopnullen tellen zou 3 opleveren, terwijl de bewerking met voorloopnullen tellen 16 retourneert. De bewerking met voorloopnullen tellen is afhankelijk van de woordgrootte: als dit 32-bits woord werd afgekapt tot een 16-bits woord, zou het tellen van voorloopnullen nul opleveren . De zoekbewerking voor de eerste set zou 4 opleveren, wat de 4e positie van rechts aangeeft. De logbase 2 is 15.

Evenzo, gegeven het volgende 32-bits woord, de bitsgewijze ontkenning van het bovenstaande woord:

1111 1111 1111 1111 0111 1111 1111 0111

De bewerking voor het tellen van de één zou 3 retourneren, de bewerking voor het tellen van de eerste zou 16 retourneren en de bewerking eerste nul vinden ffz zou 4 retourneren.

Als het woord nul is (geen bits ingesteld), retourneert het tellen van voorloopnullen en het tellen van volgnullen beide het aantal bits in het woord, terwijl ffs nul retourneert. Zowel logbase 2 als op nul gebaseerde implementaties van find first set retourneren over het algemeen een ongedefinieerd resultaat voor het nulwoord.

Hardware-ondersteuning

Veel architecturen bevatten instructies om snel de eerste set en/of gerelateerde bewerkingen uit te voeren, zoals hieronder vermeld. De meest voorkomende bewerking is het tellen van voorloopnullen (clz), waarschijnlijk omdat alle andere bewerkingen in termen daarvan efficiënt kunnen worden geïmplementeerd (zie Eigenschappen en relaties ).

Op sommige Alpha-platforms worden CTLZ en CTTZ in software geëmuleerd.

Ondersteuning voor hulpprogramma's en bibliotheken

Een aantal compiler- en bibliotheekleveranciers leveren compiler-intrinsiek of bibliotheekfuncties om de eerste set en/of gerelateerde bewerkingen uit te voeren, die vaak worden geïmplementeerd in termen van de bovenstaande hardware-instructies:

Eigenschappen en relaties

Als bits zijn gelabeld beginnend bij 1 (wat de conventie is die in dit artikel wordt gebruikt), dan tellen volgnullen en zoekbewerkingen voor de eerste set zijn gerelateerd aan ctz( x ) = ffs( x ) − 1 (behalve wanneer de invoer nul is). Als bits zijn gelabeld vanaf 0 , tel dan nullen en zoek de eerste set zijn exact equivalente bewerkingen. Gegeven w bits per woord, wordt log ₂ gemakkelijk berekend uit de clz en vice versa door log ₂ ( x ) = w − 1 − clz( x ) .

Zoals aangetoond in het bovenstaande voorbeeld, kunnen de operaties find first zero, count leading one en count trailing ones worden geïmplementeerd door de invoer te negeren en de eerste set te gebruiken, voorloopnullen tellen en naloopnullen tellen. Het omgekeerde is ook waar.

Op platforms met een efficiënte log _2- bewerking zoals M68000, kan ctz worden berekend door:

ctz( x ) = log ₂ ( x & x )

waarbij & bitsgewijze AND aangeeft en −x het twee-complement van x aangeeft . De uitdrukking x & −x wist alles behalve de minst significante 1 bit, zodat de meest en minst significante 1 bit hetzelfde zijn.

Op platforms met een efficiënte telling voorloopnullen, zoals ARM en PowerPC, kan ffs worden berekend door:

ffs( x ) = w clz( x & −x ) .

Omgekeerd, op machines zonder log ₂ of clz- operators, kan clz worden berekend met ctz , zij het inefficiënt:

clz = w − ctz(2 ^{⌈log ₂ ( x )⌉} ) (wat afhangt van ctz die w teruggeeft voor de nulinvoer )

Op platforms met een efficiënte Hamming weight (populatietelling) operatie zoals SPARC 's POPCof Blackfin 's ONESis er:

ctz( x ) = popcount(( x & −x ) − 1) , of ctz( x ) = popcount(~( x | −x )) ,

ffs( x ) = aantal populaties( x ^ ~− x )

clz = 32 − popcount(2 ^{⌈log ₂ ( x )⌉} − 1)

waarbij ^ bitsgewijze exclusieve OF aangeeft, | geeft bitsgewijze OR aan en ~ geeft bitsgewijze negatie aan.

Het inverse probleem (gegeven i , produceer een x zodanig dat ctz( x ) = i ) kan worden berekend met een verschuiving naar links ( 1 << i ).

Vind eerste stel en soortgelijke maatregelen kunnen worden uitgebreid tot willekeurig groot bit reeksen op eenvoudige wijze door te beginnen aan één uiteinde en verloopt tot een woord dat niet alle nul (voor ffs , CTZ , CLZ ) of alle-on (voor FFZ , clo , cto ) wordt aangetroffen. Een boomgegevensstructuur die recursief bitmaps gebruikt om bij te houden welke woorden niet nul zijn, kan dit versnellen.

Software-emulatie

De meeste CPU's uit de late jaren 80 hebben bit-operators voor ffs of gelijkwaardig, maar een paar moderne zoals sommige van de ARM-Mx-serie hebben dat niet. In plaats van hardware-operatoren voor ffs, clz en ctz, kan software ze emuleren met shifts, integer rekenkunde en bitsgewijze operatoren. Er zijn verschillende benaderingen, afhankelijk van de architectuur van de CPU en in mindere mate de semantiek van de programmeertaal en de kwaliteit van de compilercode. De benaderingen kunnen losjes worden omschreven als lineair zoeken , binair zoeken , zoeken+tabel opzoeken, de Bruijn-vermenigvuldiging, drijvende-kommaconversie/exponentextract en bitoperator (branchless) methoden. Er zijn afwegingen tussen uitvoeringstijd en opslagruimte, evenals draagbaarheid en efficiëntie.

Software-emulaties zijn meestal deterministisch. Ze retourneren een gedefinieerd resultaat voor alle invoerwaarden; in het bijzonder is het resultaat voor een invoer van alle nulbits gewoonlijk 0 voor ffs, en de bitlengte van de operand voor de andere bewerkingen.

Als men een hardware-clz of equivalent heeft, kan ctz efficiënt worden berekend met bitbewerkingen, maar het omgekeerde is niet waar: clz is niet efficiënt om te berekenen in afwezigheid van een hardware-operator.

2 ^nee

De functie 2 " ^{log ₂ (x)"} ( ^afronden naar de dichtstbijzijnde macht van twee) met behulp van shifts en bitsgewijze OR's is niet efficiënt om te berekenen zoals in dit 32-bits voorbeeld en zelfs inefficiënter als we een 64-bit of 128 -bit operand:

function pow2(x):
    if x = 0 return invalid  // invalid is implementation defined (not in [0,63])
    x ← x - 1
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
    return x + 1

FFS

Aangezien ffs = ctz + 1 (POSIX) of ffs = ctz (andere implementaties), kunnen de toepasselijke algoritmen voor ctz worden gebruikt, met een mogelijke laatste stap van het toevoegen van 1 aan het resultaat en het retourneren van 0 in plaats van de operandlengte voor invoer van allemaal nul bits.

CTZ

Het canonieke algoritme is een lus die nullen telt, beginnend bij de LSB totdat een 1-bit wordt aangetroffen:

function ctz1 (x)
    if x = 0 return w
    t ← 1
    r ← 0
    while (x & t) = 0
        t ← t << 1
        r ← r + 1
    return r

Dit algoritme voert O(n)-tijd en bewerkingen uit en is in de praktijk onpraktisch vanwege een groot aantal voorwaardelijke vertakkingen.

Een opzoektabel kan de meeste vertakkingen elimineren:

table[0..2n-1] = ctz(i) for i in 0..2n-1
function ctz2 (x)
    if x = 0 return w
    r ← 0
    loop
        if (x & (2n-1)) ≠ 0
            return r + table[x & (2n-1)]
        x ← x >> n
        r ← r + n

De parameter n is vast (typisch 8) en vertegenwoordigt een tijd-ruimte-afweging . De lus kan ook volledig worden uitgerold . Maar als lineair opzoeken is deze benadering nog steeds O(n) in het aantal bits in de operand.

Een binaire zoekimplementatie heeft een logaritmisch aantal bewerkingen en vertakkingen, zoals in deze 32-bits versie: dit algoritme kan ook worden ondersteund door een tabel, waarbij de onderste drie "if" -instructies worden vervangen door een 256-entry-opzoektabel met de eerste niet -zero byte aangetroffen als een index.

function ctz3 (x)
    if x = 0 return 32
    n ← 0
    if (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16
    if (x & 0x000000FF) = 0: n ← n +  8, x ← x >>  8
    if (x & 0x0000000F) = 0: n ← n +  4, x ← x >>  4
    if (x & 0x00000003) = 0: n ← n +  2, x ← x >>  2
    if (x & 0x00000001) = 0: n ← n +  1
    return n

Als de hardware een clz-operator heeft, is de meest efficiënte benadering voor het berekenen van ctz als volgt:

function ctz4 (x)
    x &= -x
    return w - (clz(x) + 1)

Een algoritme voor 32-bits ctz gebruikt de Bruijn-reeksen om een minimale perfecte hashfunctie te construeren die alle takken elimineert. Dit algoritme gaat ervan uit dat het resultaat van de vermenigvuldiging wordt afgekapt tot 32 bit.

for i from 0 to 31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i  // table [0..31] initialized
function ctz5 (x)
    return table[((x & -x) * 0x077CB531) >> 27]

De uitdrukking (x & -x) isoleert opnieuw de minst significante 1 bit. Er zijn dan nog maar 32 mogelijke woorden, die de unsigned vermenigvuldiging en shift hash naar de juiste positie in de tabel brengen. (Dit algoritme verwerkt de nulinvoer niet.)

CLZ

Het canonieke algoritme onderzoekt één bit tegelijk vanaf de MSB totdat een niet-nul bit wordt gevonden, zoals in dit voorbeeld wordt getoond. Het wordt uitgevoerd in O(n)-tijd waarbij n de bitlengte van de operand is, en is geen praktisch algoritme voor algemeen gebruik.

function clz1 (x)
    if x = 0 return w
    t ← 1 << (w - 1)
    r ← 0
    while (x & t) = 0
        t ← t >> 1
        r ← r + 1
    return r

Een verbetering ten opzichte van de vorige lusbenadering onderzoekt acht bits tegelijk en gebruikt vervolgens een 256 (2 ⁸ ) invoer-opzoektabel voor de eerste niet-nul byte. Deze benadering is echter nog steeds O(n) in uitvoeringstijd.

function clz2 (x)
    if x = 0 return w
    t ← 0xff << (w - 8)
    r ← 0
    while (x & t) = 0
        t ← t >> 8
        r ← r + 8
    return r + table[x >> (w - 8 - r)]

Binair zoeken kan de uitvoeringstijd terugbrengen tot O(log ₂ n):

function clz3 (x)
    if x = 0 return 32
    n ← 0
    if (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16
    if (x & 0xFF000000) = 0: n ← n +  8, x ← x <<  8
    if (x & 0xF0000000) = 0: n ← n +  4, x ← x <<  4
    if (x & 0xC0000000) = 0: n ← n +  2, x ← x <<  2
    if (x & 0x80000000) = 0: n ← n +  1
    return n

De snelste draagbare benaderingen om clz te simuleren zijn een combinatie van binair zoeken en tabel opzoeken: een 8-bits tabel lookup ( ²⁸ = 256 1-byte items) kan de onderste 3 takken vervangen bij binair zoeken. 64-bits operanden vereisen een extra vertakking. Een zoekactie met een grotere breedte kan worden gebruikt, maar de maximale praktische tabelgrootte wordt beperkt door de grootte van de L1-datacache op moderne processors, die voor velen 32 KB is. Het opslaan van een branch wordt meer dan gecompenseerd door de latentie van een L1-cachemisser .

Een algoritme vergelijkbaar met de Bruijn-vermenigvuldiging voor CTZ werkt voor CLZ, maar in plaats van het meest significante bit te isoleren, rondt het af naar het dichtstbijzijnde gehele getal van de vorm 2 ⁿ −1 met behulp van verschuivingen en bitsgewijze OR's:

table[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}
function clz4 (x)
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
    return table[((x * 0x07C4ACDD) >> 27) % 32]

Voor processors met diepe pijplijnen, zoals Prescott- en latere Intel-processors, kan het sneller zijn om vertakkingen te vervangen door bitsgewijze EN- en OF-operators (hoewel er veel meer instructies nodig zijn) om pijplijnspoelingen voor verkeerd voorspelde vertakkingen te voorkomen (en dit soort vertakkingen zijn inherent onvoorspelbaar):

function 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);
   return r;

Op platforms die hardwareconversie van gehele getallen naar drijvende komma bieden, kan het exponentveld worden geëxtraheerd en afgetrokken van een constante om het aantal voorloopnullen te berekenen. Correcties zijn nodig om rekening te houden met afrondingsfouten. Drijvende-kommaconversie kan een aanzienlijke latentie hebben. Deze methode is in hoge mate niet-draagbaar en wordt meestal niet aanbevolen.

int x; 
int r;
union { unsigned int u[2]; double d; } t; 

t.u[LE] = 0x43300000;  // LE is 1 for little-endian
t.u[!LE] = x;
t.d -= 4503599627370496.0;
r = (t.u[LE] >> 20) - 0x3FF;  // log2
r++;  // CLZ

Toepassingen

De bewerking voorloopnullen (clz) kan worden gebruikt om normalisatie efficiënt te implementeren , die een geheel getal codeert als m  × 2 ^e , waarbij m zijn meest significante bit op een bekende positie heeft (zoals de hoogste positie). Dit kan op zijn beurt worden gebruikt om de Newton-Raphson-divisie te implementeren , om integer naar floating point- conversie in software en andere toepassingen uit te voeren.

Voorloopnullen tellen (clz) kunnen worden gebruikt om het 32-bits predikaat "x = y" (nul indien waar, één indien onwaar) te berekenen via de identiteit clz(x − y) >> 5 , waarbij ">>" niet is ondertekend rechter verschuiving. Het kan worden gebruikt om meer geavanceerde bitbewerkingen uit te voeren, zoals het vinden van de eerste reeks van n 1 bits. De uitdrukking clz(x − y)1 << (16 − clz(x − 1)/2) is een effectieve initiële schatting voor het berekenen van de vierkantswortel van een 32-bits geheel getal met behulp van de methode van Newton . CLZ efficiënt implementeren null-onderdrukking , snel datacompressie techniek die een geheel als het aantal nul bytes met de nul bytes codeert. Het kan ook efficiënt exponentieel verdeelde gehele getallen genereren door de clz van uniform willekeurige gehele getallen te nemen.

De logbase 2 kan worden gebruikt om te anticiperen of een vermenigvuldiging zal overlopen, aangezien ⌈log ₂ (xy)⌉ ≤ ⌈log ₂ (x)⌉ + ⌈log ₂ (y)⌉ .

Voorloopnullen tellen en naloopnullen tellen kunnen samen worden gebruikt om Gosper's lusdetectie-algoritme te implementeren , dat de periode van een functie van eindig bereik kan vinden met beperkte middelen.

Het binaire GCD-algoritme besteedt vele cycli aan het verwijderen van volgnullen; dit kan worden vervangen door een telling na nullen (ctz) gevolgd door een verschuiving. Een gelijkaardige lus verschijnt in berekeningen van de hagelsteenreeks .

Een bitarray kan worden gebruikt om een prioriteitswachtrij te implementeren . In deze context is find first set (ffs) nuttig bij het efficiënt implementeren van de "pop" of "pull element met de hoogste prioriteit". De realtime-planner van de Linux-kernel gebruikt sched_find_first_bit()hiervoor intern .

Het tellen van nullen geeft een eenvoudige optimale oplossing voor het probleem van de Toren van Hanoi : de schijven worden vanaf nul genummerd en bij zet k wordt schijfnummer ctz( k ) de minimaal mogelijke afstand naar rechts verplaatst (terug cirkelend naar de links laten liggen als dat nodig is). Het kan ook een Gray-code genereren door een willekeurig woord te nemen en bit ctz( k ) bij stap k om te draaien .

Zie ook

• Bit Manipulation Instruction Sets (BMI) voor Intel en AMD x86-gebaseerde processors
• achterstand nul
• Voorloopnul
• volgcijfer
• Voorloopcijfer

Opmerkingen:

Referenties

Verder lezen

• Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 red.). Addison Wesley - Pearson Education, Inc. ISBN-nummer 978-0-321-84268-8. 0-321-84268-5.
• Anderson, Sean Eron (2005) [1997]. "Beetje Twiddling Hacks" . Stanford-universiteit . Gearchiveerd van het origineel op 2020-01-08 . Ontvangen 03-01-2012 .(NB. Geeft een overzicht van verschillende efficiënte C-implementaties in het publieke domein voor het tellen van nullen en logbase 2 .)

Externe links

• Intel Intrinsieke Gids
• Chess Programming Wiki: BitScan : Een gedetailleerde uitleg van een aantal implementatiemethoden voor ffs (genaamd LS1B) en log base 2 (genaamd MS1B).