Wie zähle ich die führenden Nullen in einem Int32? Also, was ich tun möchte, ist eine Funktion schreiben, die 30 zurückgibt, wenn meine Eingabe Int32 2 ist, denn in binär bin ich 0000000000000010.
Nehmen wir die Zahl 10 als Beispiel. Es kann wie folgt im Binärformat angegeben werden:
%Vor%Zuerst "schmieren" wir das höchstwertige Bit über die unteren Bitpositionen durch Rechtsverschiebung und bitweise ODER-Verknüpfung über sich selbst.
%Vor%dann
%Vor%Hier, weil es eine kleine Zahl ist, haben wir den Job bereits abgeschlossen, aber indem wir den Prozess bis zu einer rechten Verschiebung von 16 Bits wiederholen, können wir sicherstellen, dass für jede 32-Bit-Zahl alle gesetzt sind die Bits von 0 bis zum MSB der ursprünglichen Zahl auf 1.
Wenn wir jetzt die Anzahl der 1er in unserem "smeared" Ergebnis zählen, können wir sie einfach von 32 subtrahieren, und uns bleibt die Anzahl der führenden Nullen im ursprünglichen Wert.
Wie zählen wir die Anzahl der gesetzten Bits in einer ganzen Zahl? Diese Seite hat einen magischen Algorithmus, um genau das zu tun (" eine Variable- Präzisions-SWAR-Algorithmus zur Durchführung einer Baumreduzierung "... wenn du es bekommst, bist du klüger als ich!", was wie folgt in C # übersetzt wird:
%Vor%Indem wir diese Methode mit unserer obigen "Smearing" -Methode eingliedern, können wir eine sehr schnelle, schleifenfreie und bedingungsfreie Methode zum Zählen der führenden Nullen einer ganzen Zahl erzeugen.
%Vor%Schauen Sie Ссылка nach, um weitere Informationen zum Bitscanning zu erhalten.
Wenn Sie Assemblercode mischen können, verwenden Sie die modernen LZCNT-, TZCNT- und POPCNT-Prozessorbefehle.
Sehen Sie sich andernfalls die Implementierung von Java für Integer an.
%Vor%Komm schon Leute, hör auf zu fragen, "warum du das oder das tun willst". Antworte, wenn du kannst oder mach einfach weiter. Das Zählen von führenden Nullen ist eine häufige Aufgabe bei vielen Problemen (z. B. Komprimierungsalgorithmen). Dafür gibt es sogar x86-Hardware-Anweisungen (clz, bsr). Leider können Sie diese Hardware-Anweisungen nicht in C # verwenden, da Intrinsics (noch) nicht unterstützt werden. Umwandlung in eine Schnur war ein Witz, nehme ich an.
Binäre Darstellung von int hat sehr gut definierte Grenzen. Tatsächlich ist in C # int nur ein Alias für Int32. Wie der Name schon sagt, ist "Int32" immer eine 32-Bit-Ganzzahl mit Vorzeichen, selbst wenn Sie Ihr Projekt für x64 kompilieren.
Und du brauchst keine spezielle Voodo-Magie, um führende Nullen zu berechnen: Hier ist eine einfache mathematische Lösung, die funktioniert:
Hier ist "x" Ihr int (Int32):
%Vor%Bearbeiten: Sorry, ich habe meine Formel überprüft und korrigiert. Wegen Präzisionsfehlern der Doppelarithmetik kann das Ergebnis für einige Grenzfälle falsch sein. Es braucht also noch etwas "Voodo-Magie". Die zweite Zeile behandelt diese Fälle und erzeugt ein korrektes Ergebnis.
In C:
%Vor% (aus http://aggregate.org/MAGIC/#Leading Zero Count )
Die Übersetzung in C # bleibt dem Leser als eine triviale Aufgabe.
BEARBEITEN
Der Grund, warum ich den Link gab, war, dass ich folgendes nicht kopieren muss (wieder in C):
%Vor%zählen führenden Nullen / erste Satz / Bit-Scan-Reverse zu finden ist eine so häufige Sache in OS und andere Low-Level-Programmierung wollen die meisten Hardware unterstützt clz in Form eines einzigen Zyklus Anweisung. Und die meisten c / c ++ Compiler haben einen intrinsischen Compiler dafür.
auch die meisten Hardware und Compiler haben auch zählen nachgestellte Nullen, Pop-Count / Bitzähler / Anzahl Einsen, Parität, Bswap / Flip Endien, und einige andere Quarky aber sehr nützliche Bit Twiddling-Operationen.
Wenn Sie Assembler-Code für Spitzenleistung mischen möchten. So machen Sie das in C #.
Zuerst der unterstützende Code, um es zu ermöglichen:
%Vor%Dann ist hier die Assembly, um die Funktionen zu generieren:
%Vor%Um die Assembly zu generieren, habe ich ein neues VC ++ - Projekt gestartet, die gewünschten Funktionen erstellt und bin dann zu Debug -> Windows -> Disassembly gegangen. Für Compiler-Optionen deaktivierte ich Inlining, aktivierte Intrinsics, bevorzugten schnellen Code, ausgelassene Frame-Pointer, deaktivierte Sicherheits-Checks und SDL-Checks. Der Code dafür lautet:
%Vor%Ganzzahlen haben keine führenden Nullen, noch unterstützen sie 32 Ziffern. Allerdings sollten Sie in der Lage sein, eine Funktion zu erstellen, indem Sie die Ganzzahl in eine Zeichenfolge konvertieren und die Länge überprüfen:
%Vor%