Der schnellste Weg? Nachschlagetabellen sind fast immer der schnellste Weg. Erstellen Sie ein int [] [] -Array mit vier Milliarden Einträgen, eins für jedes int, das ein Array der gewünschten Zahlen enthält. Die Initialisierung der Tabelle dauert natürlich einige Zeit, aber die Lookups werden unglaublich schnell sein.
Ich habe bemerkt, dass Sie nicht gesagt haben, was "am schnellsten" bedeutet, und zwar mit hinreichender Genauigkeit, damit jemand die Frage tatsächlich beantworten kann. Bedeutet dies die schnellste amortisierte Zeit einschließlich der Startzeit oder die minimale Nachschlagezeit unter der Annahme, dass die Startkosten vernachlässigt werden können? Meine Lösungsskizze geht von letzterem aus.
Offensichtlich hat eine 32-Bit-Maschine mit 2 Milliarden Byte Adressraum nicht genug Adressraum, um dreißig Milliarden Byte an Arrays zu speichern. Holen Sie sich eine 64-Bit-Maschine. Sie müssen mindestens so viel physischen Speicher installiert haben, wenn Sie wollen, dass es schnell ist - das Paging wird Sie sonst töten.
Ich hoffe, dass die paar Nanosekunden, die Sie bei jeder Suche sparen, es wert sind, all diese zusätzliche Hardware zu kaufen. Oder vielleicht wirklich wollen die schnellste Weg?
: -)
Ein Nachschlage-Array für Bits mit einem Byte sollte in der Nähe des schnellsten sicheren C # -Codes liegen. Verschiebe jedes der 4 Bytes aus der Ganzzahl (gieße bei Bedarf nach uint) und indexiere in das Array.
Die Elemente des Lookup-Arrays könnten ein Array von Exponenten sein, oder, je nachdem, was Sie mit den Bits machen, vielleicht Delegaten, die funktionieren.
Nur zum Spaß, hier ist ein One-Liner mit LINQ.
Es ist sicherlich nicht der schnellste Weg, es zu tun, obwohl es nicht weit hinter den anderen Antworten ist, die yield und Iterator-Blöcke verwenden.
Für eine schnellere Lösung würde ich wahrscheinlich eine einfache Sammlung zurückgeben, anstatt einen Iteratorblock zu verwenden. Etwas wie das:
%Vor%Am schnellsten bei welcher Verteilung für die Eingabe? Wenn normalerweise nur ein Bit gesetzt ist, könnte dies schneller sein als das Durchlaufen der Suche nach gesetzten Bits.
Ausgehend von der akzeptierten Antwort für die Suche nach der Position des am wenigsten signifikanten Bits , das von Bit Twiddling Hacks genommen wurde, Löschen und Zurückgeben der Position jedes nachfolgenden niedrigstwertigen Bits.
%Vor%Es wird nur so oft wiederholt, wie Bits gesetzt sind.
Tags und Links optimization c# performance bit-manipulation