Ich habe untersucht, wie Java Bits zählt, die von einem int. gesetzt wurden Ich hatte so etwas Einfaches (was ich für richtig halte):
%Vor% Stattdessen habe ich eine Methode gefunden, von der ich absolut keine Ahnung habe, was vorgeht (scheint mir magisch): %Vor%Könnte jemand helfen, zu verstehen, was das tut und warum eine einfache Funktion wie die, die ich als erste gedacht habe, schlecht ist / könnte?
Sicher
%Vor% Das Bitmuster von 5 ist 0101 (vier Bits), also ist die Maske eine Wiederholung des Bitmusters 01 sechzehnmal. Diese Zeile zählt die Anzahl der Bits in jedem Zwei-Bit-Paar der Anzahl. Wenn Sie Zwei-Bit-Paare in Betracht ziehen, erhält (i >>> 1) & 0x1 das höherwertige Bit in der niederwertigen Position. Jetzt gibt es vier mögliche Zwei-Bit-Muster
und jedes Zwei-Bit-Paar enthält jetzt die Anzahl der Bits, die das Original in diesen Positionen hatte.
%Vor% Als nächstes zählen wir die Bits, die in jeder Vier-Bit-Gruppe waren (aka Nibble). Indem ein Nibble mit 0x3 = 0011(b) maskiert wird, erhalten wir die Anzahl von Bits, die in den zwei Bits niedrigerer Ordnung des Nibbles waren, und (i >>> 2) & 0x3 erhält den Zählwert von den zwei Bits höherer Ordnung des Nibbles. Diese Zählungen werden jetzt hinzugefügt. Da jede Zählung höchstens 2 betrug, ist die Summe höchstens 4 und verlässt das Nibble nicht.
Jetzt werden die Bits in jedem Oktett gezählt. Jedes Nibble enthält die Anzahl der Bits, die im Original an dieser Stelle gesetzt sind. Die Verschiebung nach rechts um vier Bits verschiebt den Zählwert von dem Nibble höherer Ordnung an jeder Stelle zu dem Nibble niedrigerer Ordnung, diese werden addiert. Dann haben wir auch den Zählwert vom Nibble niedrigerer Ordnung in das Nabel höherer Ordnung des benachbarten Oktetts verschoben, das durch & 0x0f0f0f0f maskiert wird. Da jedes Oktett maximal acht Bits gesetzt haben kann, verlässt die Zählung das Nibble niedriger Ordnung des Oktetts nicht.
Jetzt fügen wir die Anzahl der Paare benachbarter Oktette hinzu.
%Vor%Nun addieren wir die Summen der Zählungen in den zwei Oktetts höherer Ordnung und den zwei niedriger Ordnung.
%Vor%Schließlich werden alle Oktette außer dem Oktett der niedrigsten Ordnung maskiert, da die Oktette höherer Ordnung noch Zwischenzahlen enthielten.
Der Grund, warum Ihre einfache Implementierung als schlecht angesehen wird, ist die Leistung. Der gefaltete Bit-Hack verwendet weniger Operationen und keine Verzweigungen, also ist er schneller. Es ist jedoch viel einfacher, falsch zu liegen.
Eine weitere nette Methode, um die gesetzten Bits in int (oder long ) zu zählen, ist
Das funktioniert, weil n = n & (n-1) das zuletzt gesetzte Bit in n löscht und alles andere unberührt lässt. Wenn das Bitmuster von n mit
Das Bitmuster von n-1 ist
und die Bits vor dem letzten 1-Bit in n sind gleich. In Java funktioniert das garantiert auch für negative Zahlen, weil der Integer-Überlauf eine Wrap-Around-Semantik hat. Wenn also n = Integer.MIN_VALUE , wird das Bitmuster 100...0 und n - 1 wird Integer.MAX_VALUE mit dem Bitmuster 011...1 .
Die coole Methode funktioniert nur, da der Computer einen endlichen Wertebereich für int hat. es wird nicht funktionieren (und so andere coole Bits Algorithmen) so leicht für unendliche Reichweite (wie BigInteger), da Sie alle benötigten Masken vor der Berechnung kennen müssen.
Auf jeden Fall können Sie lesen, wie es funktioniert: Ссылка
es ist am Ende dieses Kapitels.
Tags und Links java integer bit-manipulation