Wenn wir neue Kandidaten interviewen, bitten wir sie normalerweise, einen Teil des C-Codes zu schreiben, um die Anzahl der Bits mit dem Wert 1 in einer gegebenen Bytevariablen zu zählen (z.B. enthält das Byte 3 zwei 1-Bits). Ich kenne alle gängigen Antworten, wie die achtfache Verschiebung nach rechts oder die Indexierung einer konstanten Tabelle mit 256 vorberechneten Ergebnissen.
Aber gibt es einen klügeren Weg, ohne den vorberechneten Tisch zu benutzen? Was ist die kürzeste Kombination von Byteoperationen (UND, ODER, XOR, +, -, binäre Negation, linke und rechte Verschiebung), die die Anzahl von 1 Bits berechnet?
Es gibt mindestens zwei schnellere Lösungen mit unterschiedlichen Leistungsmerkmalen:
Subtrahieren Sie eins und UND die neuen und alten Werte. Wiederholen bis Null. Zählen Sie die Anzahl der Iterationen. Komplexität: O (B), wobei B die Anzahl der Ein-Bits ist.
%Vor%Fügen Sie Paare von Bits, dann Gruppen von vier, dann Gruppen von acht hinzu, bis Sie die Wortgröße erreichen. Es gibt einen Trick, mit dem Sie alle Gruppen auf jeder Ebene in einem einzigen Durchgang hinzufügen können. Komplexität: O (log (N)), wobei N die Gesamtzahl der Bits ist.
%Vor%Diese Version ist ein bisschen naiv. Wenn Sie darüber nachdenken, können Sie einige der Operationen vermeiden.
Java macht es so (mit 32-Bit-Ganzzahlen) (14 Berechnungen)
%Vor%Für 16-Bit-Integer (kurz) kann die Methode folgendermaßen umgeschrieben werden:
%Vor%Für 8-Bit-Ganzzahlen (Byte) ist es etwas komplizierter, aber die allgemeine Idee ist da.
Sie können diesen Link für weitere Informationen über schnelle Bitzählfunktionen aufrufen: Ссылка
Der schnellste / einfachste Weg für eine ganze Zahl, nämlich O (0) für den besten Fall und O (n) für den schlimmsten Fall (wobei n die Anzahl der Bits im Wert ist) ist
%Vor%Tags und Links c bitwise-operators