Ich versuche gerade, eine Nachschlagetabelle für einen Huffman-Baum zu erstellen, indem ich einen ziemlich einfachen Preorder-Traversalalgorithmus verwende, aber ich bleibe bei der Ausführung sehr grundlegender bitweiser Operationen stecken. Der Pseudo-Code folgt:
%Vor%Ich bin ziemlich verwirrt darüber, wie man die in den Zeilen (1) und (2) definierten Operationen ausführt.
Welchen Datentyp verwendet man, um Binärzahlen darzustellen und auszudrucken? Im obigen Beispiel habe ich die Zahl als int dargestellt, aber ich bin mir ziemlich sicher, dass das falsch ist. Wie addieren oder subtrahieren Sie Werte? Ich verstehe, wie & amp; und | Typen funktioniert, aber ich bin verwirrt, wie man diese Art von Operationen im Code ausführt.
Könnte jemand einige sehr einfache Beispiele veröffentlichen?
Hier sind einige grundlegende Beispiele für binäre Operationen. Ich habe hier hauptsächlich Operationen an Ort und Stelle benutzt.
%Vor%Wenn Sie eine Binärzahl drucken möchten, müssen Sie es selbst tun ... Hier ist eine leicht ineffiziente, aber mäßig lesbare Art, es zu tun:
%Vor%[edit] Wenn ich schnelleren Code wollte, könnte ich eine Nachschlagetabelle mit den 8-Bit-Folgen für alle Zahlen von 0-255 vorgenerieren (oder hardcodieren).
%Vor%Stattdessen könnten Sie Folgendes tun:
%Vor%Oder einfach die ganze Sache ausrollen. ; -)
%Vor%Natürlich haben diese 8 Bytes im Lookup die gleiche Länge wie eine 64-Bit Integer ... Also was ist damit? Viel schneller als all diese sinnlosen mäanderförmigen Character-Arrays.
%Vor%Natürlich würden Sie im obigen Code Ihre Lookup-Werte als int64 anstelle von Strings darstellen.
Wie auch immer, nur darauf hinzuweisen, dass Sie es schreiben können, ist jedoch für Ihre Zwecke geeignet. Wenn Sie optimieren müssen, macht es Spaß, aber für die meisten praktischen Anwendungen sind solche Optimierungen vernachlässigbar oder sinnlos.
Wenn Ihre binären Sequenzen nicht länger als die Anzahl der Bits in einem int werden, können Sie einfach einen int.
verwendenUm eine 0 am Ende der aktuellen Repräsentation von a hinzuzufügen, können Sie verwenden a & lt; & lt; 1
Um eine 0 am Ende der aktuellen Darstellung von a durch eine 1 zu ersetzen, können Sie verwenden a ^ = 1
Beachten Sie, dass Sie, um ein int auf diese Weise zu verwenden, auch verfolgen müssen, wo im int Ihre Bits beginnen, so dass Sie, wenn Sie zB den Wert 0x0 haben, wissen können, welche von 0, 00, 000 ... ist es.
Operationen in Ihrem Code:
%Vor%Sie müssen jedoch auch die Länge der Sequenz beibehalten.
Wenn die Länge eines int für Sie gut genug ist, gibt es keinen Grund, sie nicht zu verwenden. Im Huffman-Algorithmus würde dies jedoch wirklich von den Daten abhängen. C ++ - Programmierer sollten boost :: dynamic_bitset für Bitfolgen beliebiger Länge verwenden. Es unterstützt auch die obigen Bitoperationen. Ссылка