Find første sæt - Find first set

I computer software og hardware, finde første sæt ( FFS ) eller finde første er en smule operation , at i betragtning en usigneret maskine ord , betegner indeks eller positionen af den mindst betydende bit sæt til én i ordet optælling fra den mindst betydende bit position. En næsten ækvivalent handling er tællingsnuller ( ctz ) eller antal efterfølgende nuller ( ntz ), som tæller antallet af nul bits efter den mindst signifikante bit. Den supplerende operation, der finder det indeks eller position af de mest betydningsfulde sæt bit er totalslogaritmen 2 , såkaldte fordi det beregner den binære logaritmen ⌊log ₂ (x) ⌋ . Dette er tæt forbundet med at tælle førende nuller ( clz ) eller antallet af førende nuller ( nlz ), som tæller antallet af nul bits forud for den mest betydningsfulde ene bit. Der er to almindelige varianter af find første sæt, POSIX -definitionen, der starter indeksering af bits ved 1, heri mærket ffs, og varianten, der starter indeksering af bits ved nul, hvilket svarer til ctz og så vil blive kaldt ved dette navn.

De fleste moderne CPU -instruktionssæt -arkitekturer giver en eller flere af disse som hardware -operatører; softwareemulering leveres normalt til alle, der ikke er tilgængelige, enten som kompilatorens egen eller i systembiblioteker.

Eksempler

I betragtning af følgende 32-bit ord:

0000 0000 0000 0000 1000 0000 0000 1000

Den tællende efterfølgende nuloperation ville returnere 3, mens den tællende nuloperation returnerer 16. Den tællende nuloperation afhænger af ordstørrelsen: hvis dette 32-bit ord blev afkortet til et 16-bit ord, ville tællende førende nuller returnere nul . Findet første sæt operation ville returnere 4, hvilket angiver den 4. position fra højre. Brændefoden 2 er 15.

I betragtning af følgende 32-bit ord, den bitvise negation af ovenstående ord:

1111 1111 1111 1111 0111 1111 1111 0111

Tællingen efterfølgende operation ville returnere 3, den tællende ledende operation ville returnere 16, og find første nul operation ffz ville returnere 4.

Hvis ordet er nul (ingen bits er angivet), tæller ledende nuller og tællende nuller begge antallet af bits i ordet, mens ffs returnerer nul. Både logbase 2 og nulbaserede implementeringer af find første sæt returnerer generelt et udefineret resultat for nulordet.

Hardware support

Mange arkitekturer indeholder instruktioner til hurtigt at udføre find første sæt og/eller relaterede operationer, der er angivet nedenfor. Den mest almindelige operation er tællende nuller (clz), sandsynligvis fordi alle andre operationer kan implementeres effektivt med hensyn til det (se Egenskaber og relationer ).

På nogle Alpha -platforme er CTLZ og CTTZ emuleret i software.

Værktøj og biblioteksunderstøttelse

En række kompilator- og biblioteksleverandører leverer kompilatorens iboende egenskaber eller biblioteksfunktioner til at udføre find første sæt og/eller relaterede operationer, som ofte implementeres i forhold til hardwareinstruktionerne ovenfor:

Egenskaber og relationer

Hvis bits er mærket med start ved 1 (hvilket er konventionen, der bruges i denne artikel), tælles efterfølgende nuller og finder første sæt -operationer relateret af ctz ( x ) = ffs ( x ) - 1 (undtagen når input er nul). Hvis bits er mærket med start fra 0 , så tæl efterfølgende nuller og find første sæt er nøjagtigt ækvivalente operationer. Givet w bits pr. Ord beregnes log ₂ let fra clz og omvendt af log ₂ ( x ) = w - 1 - clz ( x ) .

Som demonstreret i eksemplet ovenfor kan operationerne med at finde første nul, tælle førende og tælle efterfølgende implementeres ved at negere input og bruge find første sæt, tælle førende nuller og tælle nulstillinger. Det omvendte er også sandt.

På platforme med en effektiv log ₂ -operation som M68000 kan ctz beregnes af:

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

hvor & betegner bitvis AND og −x betegner de tos komplement af x . Udtrykket x & −x rydder alle undtagen den mindst signifikante 1 bit, så den mest og mindst signifikante 1 bit er den samme.

På platforme med en effektiv tællende nuloperation, f.eks. ARM og PowerPC, kan ffs beregnes af:

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

Omvendt på maskiner uden log ₂ eller clz -operatører kan clz beregnes ved hjælp af ctz , omend ineffektivt:

clz = w - ctz (2 ^{⌈log ₂ ( x ) ⌉} ) (hvilket afhænger af ctz, der returnerer w for nulindgangen )

På platforme med en effektiv Hamming -vægt (befolkningstal), f.eks. SPARC 's POPCeller Blackfin 's ONES, er der:

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

ffs ( x ) = popcount ( x ^ ~ - x )

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

hvor ^ betegner bitvis eksklusiv-OR, | betegner bitvis ELLER og ~ betegner bitvis negation.

Det omvendte problem (givet i , producer et x, således at ctz ( x ) = i ) kan beregnes med et venstre-shift ( 1 << i ).

Find første sæt og relaterede operationer kan udvides til vilkårligt store bit-arrays på en ligetil måde ved at starte i den ene ende og fortsætte indtil et ord, der ikke er alle-nul (for ffs , ctz , clz ) eller ikke all-one (for ffz , clo , cto ) opstår. En trædatastruktur, der rekursivt bruger bitmaps til at spore, hvilke ord der er nul, kan fremskynde dette.

Softwareemulering

De fleste CPU'er fra slutningen af ​​1980'erne og fremefter har bitoperatører til ffs eller tilsvarende, men et par moderne som f.eks. Nogle af ARM-Mx-serierne gør det ikke. I stedet for hardware -operatører til ffs, clz og ctz kan software efterligne dem med skift, heltal aritmetik og bitvise operatører. Der er flere tilgange afhængigt af arkitekturen i CPU'en og i mindre grad programmeringssprogets semantik og kompileringskodegenereringskvalitet. Fremgangsmåderne kan løst beskrives som lineær søgning , binær søgning , søgning+tabelopslag, de Bruijn -multiplikation, flydende punktkonvertering/eksponentekstrakt og bitoperator (grenløse) metoder. Der er afvejninger mellem udførelsestid og lagerplads samt portabilitet og effektivitet.

Softwareemuleringer er normalt deterministiske. De returnerer et defineret resultat for alle inputværdier; især er resultatet for et input af alle nul bits normalt 0 for ffs og bitlængden af ​​operanden for de andre operationer.

Hvis man har en hardware clz eller tilsvarende, kan ctz effektivt beregnes med bitoperationer, men det modsatte er ikke sandt: clz er ikke effektiv at beregne i fravær af en hardware -operatør.

2 ⁿ

Funktionen 2 ^{⌈log ₂ (x) ⌉} (rund op til den nærmeste effekt af to) ved hjælp af skift og bitvis OR'er er ikke effektiv til at beregne som i dette 32-bit eksempel og endnu mere ineffektiv, hvis vi har en 64-bit eller 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

Da ffs = ctz + 1 (POSIX) eller ffs = ctz (andre implementeringer), kan de gældende algoritmer for ctz bruges, med et muligt sidste trin med at tilføje 1 til resultatet og returnere 0 i stedet for operandlængden for input af alle nul bits.

CTZ

Den kanoniske algoritme er en loop-tælling af nuller, der starter ved LSB, indtil der opstår en 1-bit:

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

Denne algoritme udfører O (n) tid og operationer og er upraktisk i praksis på grund af et stort antal betingede grene.

Et opslagstabel kan fjerne de fleste grene:

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

Parameteren n er fast (typisk 8) og repræsenterer en afvejning mellem tid og rum . Sløjfen kan også være fuldt udrullet . Men som et lineært opslag er denne fremgangsmåde stadig O (n) i antallet af bits i operanden.

En implementering af binær søgning tager et logaritmisk antal operationer og filialer, som i denne 32-bit version: Denne algoritme kan også assisteres af en tabel og erstatter de tre nederste "if"-sætninger med en 256-opslagstabel ved hjælp af den første ikke -nul -byte stødt på som et indeks.

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

Hvis hardwaren har en clz -operator, er den mest effektive tilgang til computing ctz således:

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

En algoritme til 32-bit ctz bruger de Bruijn-sekvenser til at konstruere en minimal perfekt hash-funktion, der eliminerer alle grene. Denne algoritme antager, at resultatet af multiplikationen er afkortet til 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]

Udtrykket (x & -x) isolerer igen den mindst signifikante 1 bit. Der er da kun 32 mulige ord, som den usignerede multiplikation og flytter hash til den korrekte position i tabellen. (Denne algoritme håndterer ikke nulindgangen.)

CLZ

Den kanoniske algoritme undersøger en bit ad gangen fra MSB, indtil der findes en bit, der ikke er nul, som vist i dette eksempel. Det udføres i O (n) tid, hvor n er operandens bitlængde, og er ikke en praktisk algoritme til generel brug.

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

En forbedring i forhold til den tidligere looping-tilgang undersøger otte bits ad gangen og bruger derefter en 256 (2 ⁸ ) opslagstabel for den første byte uden nul. Denne fremgangsmåde er dog stadig O (n) i udførelsestiden.

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)]

Binær søgning kan reducere udførelsestiden til 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 hurtigste bærbare metoder til simulering af clz er en kombination af binær søgning og tabelopslag: et 8-bit tabelopslag (2 ⁸ = 256 1-byte poster) kan erstatte de nederste 3 grene i binær søgning. 64-bit operander kræver en ekstra gren. Et opslag med større bredde kan bruges, men den maksimale praktiske bordstørrelse er begrænset af størrelsen på L1 -datacache på moderne processorer, hvilket er 32 KB for mange. At gemme en gren opvejes mere end forsinkelsen af ​​en L1 -cache -miss.

En algoritme, der ligner de Bruijn-multiplikation for CTZ, fungerer for CLZ, men i stedet for at isolere den mest signifikante bit, runder den op til det nærmeste helt tal i formen 2 ⁿ −1 ved hjælp af skift og bitvis OR:

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]

For processorer med dybe rørledninger, som Prescott og senere Intel -processorer, kan det være hurtigere at udskifte filialer med bitvise AND- og OR -operatører (selvom der kræves mange flere instruktioner) for at undgå pipeline -skylninger for fejlforudsagte grene (og disse typer grene er iboende uforudsigelig):

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;

På platforme, der leverer hardwarekonvertering af heltal til flydende punkt, kan eksponentfeltet ekstraheres og trækkes fra en konstant for at beregne antallet af førende nuller. Korrektioner er nødvendige for at tage højde for afrundingsfejl. Konvertering af flydende punkter kan have betydelig latenstid. Denne metode er meget ikke-bærbar og anbefales normalt ikke.

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

Ansøgninger

Den tællende førende nuller (clz) operation kan bruges til effektivt at implementere normalisering , som koder et helt tal som m  × 2 ^e , hvor m har sin mest betydende bit i en kendt position (f.eks. Den højeste position). Dette kan igen bruges til at implementere Newton – Raphson division , udføre heltal til floating point konvertering i software og andre applikationer.

Tæl ledende nuller (clz) kan bruges til at beregne 32-bit prædikatet "x = y" (nul hvis sandt, en hvis falsk) via identiteten clz (x-y) >> 5 , hvor ">>" er usigneret højre skift. Det kan bruges til at udføre mere sofistikerede bitoperationer som at finde den første streng med n 1 bits. Udtrykket clz (x-y) 1 << (16-clz (x-1)/2) er et effektivt indledende gæt til beregning af kvadratroden af ​​et 32-bit heltal ved hjælp af Newtons metode . CLZ kan effektivt implementere null -undertrykkelse , en hurtig datakomprimeringsteknik , der koder for et helt tal som antallet af førende nulbytes sammen med ikke -nulbytes. Det kan også effektivt generere eksponentielt distribuerede heltal ved at tage clz af ensartet tilfældige heltal.

Logbasen 2 kan bruges til at forudse, om en multiplikation vil flyde over, da ⌈log ₂ (xy) ⌉ ≤ ⌈log ₂ (x) ⌉ + ⌈log ₂ (y) ⌉ .

Tæl ledende nuller og tæll nulstillede nuller kan bruges sammen til at implementere Gospers loop-detekteringsalgoritme , som kan finde perioden for en funktion af begrænset rækkevidde ved hjælp af begrænsede ressourcer.

Den binære GCD -algoritme bruger mange cyklusser til at fjerne efterfølgende nuller; dette kan erstattes af et tællingsnuller (ctz) efterfulgt af et skift. En lignende sløjfe vises i beregninger af haglstenssekvensen .

Et bit array kan bruges til at implementere en prioritetskø . I denne sammenhæng er det første sæt (ffs) nyttigt til effektivt at implementere operationen "pop" eller "pull prioriteret element" effektivt. Den Linux-kernen realtid scheduler internt bruger sched_find_first_bit()til dette formål.

Den tællende nuloperation giver en enkel optimal løsning på Tower of Hanoi -problemet: diske er nummereret fra nul, og ved træk k flyttes disknummer ctz ( k ) den mindst mulige afstand til højre (cirkler tilbage rundt til efter behov). Det kan også generere en grå kode ved at tage et vilkårligt ord og vende bit ctz ( k ) i trin k .

Se også

• Bitmanipulation Instruction Sets (BMI) til Intel og AMD x86-baserede processorer
• Efterfølgende nul
• Førende nul
• Efterfølgende ciffer
• Ledende ciffer

Noter

Referencer

Yderligere læsning

• Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 red.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
• Anderson, Sean Eron (2005) [1997]. "Bit Twiddling Hacks" . Stanford University . Arkiveret fra originalen 2020-01-08 . Hentet 2012-01-03 .(NB. Lister over flere effektive C -implementeringer i det offentlige domæne til tælling af efterfølgende nuller og logbase 2. )

eksterne links

• Intel Intrinsics Guide
• Chess Programming Wiki: BitScan : En detaljeret forklaring på en række implementeringsmetoder for ffs (kaldet LS1B) og logbase 2 (kaldet MS1B).