Erstes Set finden - Find first set

In Computer - Software und Hardware, finden ersten Satz ( FFS ) oder Finden der erste Eins a Bitoperation , dass ein unsigned gegebenes Maschinenwort , um den Index oder die Position des niedrigstwertigen Bit auf einen in der Wortzählung von dem niedrigstwertigen Bit bezeichnet Position. Eine nahezu äquivalente Operation ist das Zählen von nachgestellten Nullen ( ctz ) oder die Anzahl von nachgestellten Nullen ( ntz ), die die Anzahl von Null-Bits zählt, die dem niederwertigsten Bit folgen. Die komplementäre Operation, die den Index oder die Position des höchstwertigen gesetzten Bits findet, ist die logarithmische Basis 2 , so genannt, weil sie den binären Logarithmus ⌊log ₂ (x)⌋ berechnet . Dies steht in engem Zusammenhang mit der Zählung führender Nullen ( clz ) oder der Anzahl der führenden Nullen ( nlz ), die die Anzahl der Nullbits vor dem höchstwertigen Bit zählt. Es gibt zwei gängige Varianten von Find First Set, die POSIX- Definition, die die Indizierung von Bits bei 1 beginnt, hier als ffs bezeichnet, und die Variante, die die Indizierung von Bits bei Null beginnt, die äquivalent zu ctz ist und daher mit diesem Namen bezeichnet wird.

Die meisten modernen CPU- Befehlssatzarchitekturen bieten einen oder mehrere davon als Hardwareoperatoren; Softwareemulation wird normalerweise für alle bereitgestellt, die nicht verfügbar sind, entweder als intrinsische Compiler oder in Systembibliotheken.

Beispiele

Gegeben das folgende 32-Bit-Wort:

0000 0000 0000 0000 1000 0000 0000 1000

Die Operation zum Zählen der abschließenden Nullen würde 3 zurückgeben, während die Operation zum Zählen der führenden Nullen 16 zurückgibt. Die Zählung der führenden Nullen hängt von der Wortgröße ab: Wenn dieses 32-Bit-Wort auf ein 16-Bit-Wort gekürzt würde, würde die Zählung der führenden Nullen Null zurückgeben . Die Operation Find first set würde 4 zurückgeben, was die vierte Position von rechts anzeigt. Die Logbasis 2 ist 15.

In ähnlicher Weise gilt für das folgende 32-Bit-Wort die bitweise Negation des obigen Wortes:

1111 1111 1111 1111 0111 1111 1111 0111

Die Operation zum Zählen der nachfolgenden Einsen würde 3 zurückgeben, die Operation zum Zählen der führenden Einsen würde 16 zurückgeben und die Operation zum Finden der ersten Null ffz würde 4 zurückgeben.

Wenn das Wort null ist (keine Bits gesetzt), geben führende Nullen zählen und nachfolgende Nullen zählen beide die Anzahl der Bits im Wort zurück, während ffs null zurückgibt. Sowohl log-Basis-2- als auch nullbasierte Implementierungen von find first set geben im Allgemeinen ein undefiniertes Ergebnis für das Null-Wort zurück.

Hardware-Unterstützung

Viele Architekturen enthalten Anweisungen zum schnellen Durchführen von Find-First-Set- und/oder verwandten Operationen, die unten aufgelistet sind. Die gebräuchlichste Operation ist das Zählen führender Nullen (clz), wahrscheinlich weil alle anderen Operationen in Bezug darauf effizient implementiert werden können (siehe Eigenschaften und Beziehungen ).

Auf einigen Alpha-Plattformen werden CTLZ und CTTZ in Software emuliert.

Tool- und Bibliotheksunterstützung

Eine Reihe von Compiler- und Bibliotheksanbietern bieten Compiler-Intrinsic- oder Bibliotheksfunktionen an, um Find-First-Set- und/oder verwandte Operationen durchzuführen, die häufig in Bezug auf die obigen Hardware-Anweisungen implementiert werden:

Eigenschaften und Beziehungen

Wenn Bits beginnend bei 1 beschriftet sind (was die in diesem Artikel verwendete Konvention ist), dann zählen nachfolgende Nullen und die Operationen zum Suchen des ersten Satzes sind durch ctz( x ) = ffs( x ) − 1 verbunden (außer wenn die Eingabe null ist). Wenn Bits beginnend bei 0 beschriftet sind , dann zählen nachfolgende Nullen und Find First Set sind genau äquivalente Operationen. Bei w Bits pro Wort lässt sich log ₂ leicht aus clz berechnen und umgekehrt durch log ₂ ( x ) = w − 1 − clz ( x ) .

Wie im obigen Beispiel gezeigt, können die Operationen Erste Null finden, führende Einsen zählen und nachfolgende Einsen zählen implementiert werden, indem die Eingabe negiert und erster Satz gefunden, führende Nullen zählen und nachfolgende Nullen zählen verwendet werden. Das Umgekehrte gilt auch.

Auf Plattformen mit einem effizienten Log- _2- Betrieb wie M68000 kann ctz wie folgt berechnet werden:

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

wo & Bezeichnet bitweise UND und -x bezeichnet das Zweier - Komplement von x . Der Ausdruck x & −x löscht alle außer dem niederwertigsten 1 Bit, sodass das höchstwertige und das niedrigstwertige 1 Bit gleich sind.

Auf Plattformen mit einer effizienten Operation zum Zählen führender Nullen wie ARM und PowerPC kann ffs wie folgt berechnet werden:

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

Im Gegensatz dazu auf Maschinen ohne log ₂ oder clz Operatoren clz berechnet werden unter Verwendung von ctz , wenn auch ineffizient:

CIZ = w - CTZ (2 ^{⌈log ₂ ( x ) ⌉} ) (die davon abhängt , CTZ zurückkehr w für den Null - Eingang)

Auf Plattformen mit einem effizienten Hamming - Gewicht (Bevölkerungszahl) Betrieb wie SPARC ‚s POPCoder Blackfin ‘ s ONESgibt es:

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

ffs( x ) = Popcount( x ^ ~− x )

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

wobei ^ bitweises Exklusiv-ODER bezeichnet, | bezeichnet bitweises ODER und ~ bezeichnet bitweise Negation.

Das umgekehrte Problem (bei i , erzeugt eine x , so daß CTZ ( x ) = i ) mit einer Linksverschiebung (berechnet wird 1 << i ).

Find first set und verwandte Operationen können auf einfache Weise auf beliebig große Bit-Arrays erweitert werden, indem an einem Ende begonnen und bis zu einem Wort fortgefahren wird , das nicht ganz null (für ffs , ctz , clz ) oder nicht ganz eins (für ffz .) ist , clo , cto ) gefunden wird. Eine Baumdatenstruktur, die rekursiv Bitmaps verwendet, um zu verfolgen, welche Wörter ungleich Null sind, kann dies beschleunigen.

Softwareemulation

Die meisten CPUs aus den späten 1980er Jahren haben Bitoperatoren für ffs oder gleichwertig, einige moderne CPUs wie einige der ARM-Mx-Serien jedoch nicht. Anstelle von Hardware-Operatoren für ffs, clz und ctz kann Software diese mit Verschiebungen, Integer-Arithmetik und bitweisen Operatoren emulieren. Es gibt verschiedene Ansätze, die von der Architektur der CPU und in geringerem Maße von der Programmiersprachensemantik und der Qualität der Compilercodegenerierung abhängen. Die Ansätze können lose beschrieben werden als lineare Suche , binäre Suche , Suche + Tabellensuche, de Bruijn-Multiplikation, Gleitkomma-Umwandlung/Exponenten-Extraktion und Bitoperator-(verzweigungslose) Verfahren. Es gibt Kompromisse zwischen Ausführungszeit und Speicherplatz sowie Portabilität und Effizienz.

Softwareemulationen sind normalerweise deterministisch. Sie geben für alle Eingabewerte ein definiertes Ergebnis zurück; insbesondere ist das Ergebnis für eine Eingabe aller Nullbits normalerweise 0 für ffs und die Bitlänge des Operanden für die anderen Operationen.

Wenn man eine Hardware-Clz oder ein Äquivalent hat, kann ctz effizient mit Bitoperationen berechnet werden, aber das Gegenteil ist nicht der Fall: clz ist ohne einen Hardware-Operator nicht effizient zu berechnen.

2 ⁿ

Die Funktion 2 ^{⌈log ₂ (x)⌉} ( ^aufgerundet auf die nächste Zweierpotenz) mit Verschiebungen und bitweisen ODERs ist nicht effizient zu berechnen wie in diesem 32-Bit-Beispiel und noch ineffizienter, wenn wir eine 64-Bit- oder 128-Bit-Funktion haben -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) oder ffs = ctz (andere Implementierungen) sind, können die anwendbaren Algorithmen für ctz verwendet werden, mit einem möglichen letzten Schritt des Addierens von 1 zum Ergebnis und der Rückgabe von 0 anstelle der Operandenlänge für die Eingabe von alle Nullbits.

CTZ

Der kanonische Algorithmus ist eine Schleife, die Nullen beginnend beim LSB zählt, bis ein 1-Bit angetroffen wird:

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

Dieser Algorithmus führt O(n) Zeit und Operationen aus und ist in der Praxis aufgrund einer großen Anzahl von bedingten Verzweigungen unpraktisch.

Eine Nachschlagetabelle kann die meisten Verzweigungen eliminieren:

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

Der Parameter n ist fest (normalerweise 8) und repräsentiert einen Zeit-Raum-Kompromiss . Die Schlaufe kann auch vollständig ausgerollt werden . Aber als lineares Nachschlagen ist dieser Ansatz immer noch O(n) in der Anzahl der Bits im Operanden.

Eine binäre Suchimplementierung erfordert eine logarithmische Anzahl von Operationen und Verzweigungen, wie in dieser 32-Bit-Version: Dieser Algorithmus kann auch durch eine Tabelle unterstützt werden, indem die unteren drei "if"-Anweisungen durch eine Lookup-Tabelle mit 256 Einträgen ersetzt werden, die das erste nicht -null Byte als Index gefunden.

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

Wenn die Hardware einen clz-Operator hat, ist der effizienteste Ansatz zur Berechnung von ctz daher:

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

Ein Algorithmus für 32-Bit-ctz verwendet de Bruijn-Sequenzen , um eine minimale perfekte Hash-Funktion zu konstruieren , die alle Verzweigungen eliminiert. Dieser Algorithmus geht davon aus, dass das Ergebnis der Multiplikation auf 32 Bit gekürzt wird.

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]

Der Ausdruck (x & -x) isoliert wiederum das niederwertigste 1 Bit. Es gibt dann nur noch 32 mögliche Wörter, die durch die vorzeichenlose Multiplikation und Shift an die richtige Position in der Tabelle gehasht werden. (Dieser Algorithmus verarbeitet die Nulleingabe nicht.)

CLZ

Der kanonische Algorithmus untersucht ein Bit nach dem anderen, beginnend mit dem MSB, bis ein Nicht-Null-Bit gefunden wird, wie in diesem Beispiel gezeigt. Er wird in O(n)-Zeit ausgeführt, wobei n die Bitlänge des Operanden ist und kein praktischer Algorithmus für den allgemeinen Gebrauch ist.

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

Eine Verbesserung gegenüber dem vorherigen Schleifenansatz untersucht acht Bits gleichzeitig und verwendet dann eine Nachschlagetabelle mit 256 (2 ⁸ ) Einträgen für das erste Byte ungleich Null. Dieser Ansatz ist jedoch immer noch O(n) in der Ausführungszeit.

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

Die binäre Suche kann die Ausführungszeit auf O(log ₂ n) reduzieren :

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

Die schnellsten portablen Ansätze zur Simulation von clz sind eine Kombination aus binärer Suche und Tabellensuche: Eine 8-Bit-Tabellensuche (2 ⁸ = 256 1-Byte-Einträge) kann die unteren 3 Zweige der binären Suche ersetzen. 64-Bit-Operanden erfordern einen zusätzlichen Zweig. Ein Lookup mit größerer Breite kann verwendet werden, aber die maximale praktische Tabellengröße wird durch die Größe des L1-Datencaches auf modernen Prozessoren begrenzt, die für viele 32 KB beträgt. Das Speichern einer Verzweigung wird durch die Latenzzeit eines L1-Cache- Fehltreffers mehr als ausgeglichen .

Ein Algorithmus ähnlich der de Bruijn-Multiplikation für CTZ funktioniert für CLZ, aber anstatt das höchstwertige Bit zu isolieren, rundet er mithilfe von Verschiebungen und bitweisen ODERs auf die nächste ganze Zahl der Form 2 ⁿ −1 auf:

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]

Bei Prozessoren mit tiefen Pipelines, wie Prescott und späteren Intel-Prozessoren, kann es schneller sein, Verzweigungen durch bitweise AND- und ODER-Operatoren zu ersetzen (auch wenn viel mehr Anweisungen erforderlich sind), um Pipeline-Flushes für falsch vorhergesagte Verzweigungen zu vermeiden (und diese Arten von Verzweigungen sind von Natur aus .) unvorhersehbar):

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;

Auf Plattformen, die eine Hardwarekonvertierung von ganzen Zahlen in Gleitkommazahlen bereitstellen, kann das Exponentenfeld extrahiert und von einer Konstanten subtrahiert werden, um die Anzahl der führenden Nullen zu berechnen. Korrekturen sind erforderlich, um Rundungsfehler zu berücksichtigen. Die Gleitkomma-Konvertierung kann eine beträchtliche Latenzzeit haben. Diese Methode ist in hohem Maße nicht tragbar und wird normalerweise nicht empfohlen.

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

Anwendungen

Die Operation zum Zählen führender Nullen (clz) kann verwendet werden, um eine Normalisierung effizient zu implementieren , die eine ganze Zahl als m  × 2 ^e codiert , wobei m sein höchstwertiges Bit an einer bekannten Position (wie der höchsten Position) hat. Dies kann wiederum verwendet werden, um eine Newton-Raphson-Division zu implementieren , eine Ganzzahl-zu- Gleitkomma- Umwandlung in Software durchzuführen und andere Anwendungen.

Zählen führender Nullen (clz) kann verwendet werden, um das 32-Bit-Prädikat "x = y" (null wenn wahr, eins wenn falsch) über die Identität clz(x − y) >> 5 zu berechnen , wobei ">>" vorzeichenlos ist rechte Shifttaste. Es kann verwendet werden, um komplexere Bitoperationen wie das Finden der ersten Folge von n 1 Bits durchzuführen . Der Ausdruck clz(x − y)1 << (16 − clz(x − 1)/2) ist eine effektive Anfangsschätzung für die Berechnung der Quadratwurzel einer 32-Bit-Ganzzahl unter Verwendung der Newton-Methode . CLZ effizient implementieren Nullunterdrückung , eine schnelle Datenkompressionstechnik , die eine ganze Zahl als die Anzahl von führenden Null - Bytes zusammen mit dem Nicht - Null - Bytes codiert. Es kann auch effizient exponentiell verteilte ganze Zahlen erzeugen, indem es die clz von gleichmäßig zufälligen ganzen Zahlen nimmt.

Die logarithmische Basis 2 kann verwendet werden, um zu antizipieren, ob eine Multiplikation überlaufen wird, da log ₂ (xy)⌉ log ₂ (x)⌉ + ⌈log ₂ (y)⌉ .

Führende Nullen zählen und nachfolgende Nullen zählen können zusammen verwendet werden, um den Schleifenerkennungsalgorithmus von Gosper zu implementieren , der die Periode einer Funktion mit endlichem Bereich unter Verwendung begrenzter Ressourcen finden kann.

Der binäre GCD-Algorithmus verbringt viele Zyklen damit, nachfolgende Nullen zu entfernen; dies kann durch eine Zählung mit nachgestellten Nullen (ctz) gefolgt von einer Verschiebung ersetzt werden. Eine ähnliche Schleife tritt bei Berechnungen der Hagelkornfolge auf .

Ein Bit-Array kann verwendet werden, um eine Prioritätswarteschlange zu implementieren . In diesem Zusammenhang ist Find First Set (ffs) nützlich beim effizienten Implementieren der "Pop"- oder "Pull-Element mit der höchsten Priorität"-Operation. Zu diesem Zweck wird intern der Echtzeit-Scheduler des Linux-Kernels verwendet sched_find_first_bit().

Die Operation Count Trailing Zeros liefert eine einfache optimale Lösung für das Turm-von-Hanoi- Problem: Die Scheiben werden von Null aus nummeriert, und bei Bewegung k wird die Scheibennummer ctz( k ) um den kleinstmöglichen Abstand nach rechts verschoben (Rückkreisen um die links nach Bedarf). Er kann auch einen Gray-Code erzeugen , indem er ein beliebiges Wort nimmt und das Bit ctz( k ) in Schritt k umkehrt .

Siehe auch

• Bit Manipulation Instruction Sets (BMI) für Intel und AMD x86-basierte Prozessoren
• Nachgestellte Null
• Führende Null
• Nachgestellte Ziffer
• Führende Ziffer

Anmerkungen

Verweise

Weiterlesen

• Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 Aufl.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
• Anderson, Sean Eron (2005) [1997]. "Bitte drehende Hacks" . Stanford-Universität . Archiviert vom Original am 08.01.2020 . Abgerufen 2012-01-03 .(Hinweis: Listet mehrere effiziente Public-Domain-C-Implementierungen für die Anzahl nachgestellter Nullen und die Log-Basis 2 auf .)

Externe Links

• Intel Intrinsics-Leitfaden
• Schachprogrammier-Wiki: BitScan : Eine detaillierte Erklärung einer Reihe von Implementierungsmethoden für ffs (genannt LS1B) und Log-Basis 2 (genannt MS1B).