Kompilierzeit Berechnung der Anzahl der Bits benötigt, um n verschiedene Zustände zu kodieren
Bearbeiten: In der ersten Frage hatte eine falsche Formel und der Algorithmus versuchte etwas völlig anderes als das, was beabsichtigt war. Ich entschuldige mich und ich beschloss, die Frage neu zu schreiben, um alle Verwirrung zu beseitigen.
Ich muss zum Zeitpunkt der Kompilierung berechnen (das Ergebnis wird als nicht-typischer Template-Parameter verwendet) die minimale Anzahl an Bits, die zum Speichern von n verschiedenen Zuständen benötigt werden:
oder über Vorlage
Die Ergebnisse sollten lauten:
%Vor%Die anfängliche (irgendwie korrigierte) Version als Referenz:
Ich muss zum Zeitpunkt der Kompilierung berechnen (das Ergebnis wird als Template-Parameter ohne Typ verwendet) die minimale Anzahl an Bits, die zum Speichern von n verschiedenen Zuständen benötigt wird, dh den Integralanteil (abgerundet) vom binären Logarithmus aufgerundet:
Das ist, was ich gefunden habe ( total falsch ):
%Vor% Dies erzeugt das korrekte Ergebnis (für num_states_ != 0 ), aber die Rekursion bläst exponentiell aus und ist praktisch unbrauchbar für jede Eingabe größer als 10 (die Speichernutzung Während der Kompilierung wächst über 2GB, das Betriebssystem friert ein und der Compiler stürzt ab).
Wie kann ich das zur Kompilierzeit praktisch berechnen?
6 Antworten
Die minimale Anzahl von Bits, die zum Speichern von n verschiedenen Zuständen benötigt wird, ist ceil(log2(n)) .
Beachten Sie, dass ceillog2(1) == 0 . Das ist völlig in Ordnung, denn wenn Sie ein Objekt serialisieren möchten und Sie wissen, dass eines seiner Datenelemente nur den Wert 42 annehmen kann, müssen Sie für dieses Element nichts speichern. Weisen Sie einfach 42 bei der Deserialisierung zu.
Versuchen Sie Folgendes:
%Vor%Einfacherer Ausdruck, korrektes Ergebnis .
EDIT : "Korrektes Ergebnis" wie in "der vorgeschlagene Algorithmus kommt nicht einmal nahe"; natürlich berechne ich die "Anzahl der Bits, um den Wert x darzustellen"; subtrahiere 1 vom Argument, wenn du wissen möchtest, wie viele Bits von 0 bis x-1 zählen. Um 1024 darzustellen, benötigen Sie 11 Bits, um von 0 bis 1023 (1024 Zustände) zu zählen, benötigen Sie 10.
EDIT 2 : Die Funktion wurde umbenannt, um Verwechslungen zu vermeiden.
vielleicht
%Vor%wie Sie es als tempalte-Parameter verwenden, können Sie überprüfen, was boost hat zu bieten
Etwas, das ich in meinem eigenen Code verwendet habe:
%Vor% Es erfordert, dass C ++ 14 als constexpr verwendet wird, aber es hat die nette Eigenschaft, dass es zur Laufzeit ziemlich schnell ist - etwa eine Größenordnung schneller als die Verwendung von std::log und std::ceil - und ich ' Ich habe überprüft, dass es die gleichen Ergebnisse für alle darstellbaren Werte ungleich Null liefert (log ist undefiniert auf Null, obwohl 0 ein sinnvolles Ergebnis für diese Anwendung ist; Sie benötigen keine Bits, um Nullwerte zu unterscheiden) mit dem folgenden Programm:
Dies sollte nicht zu schwer sein, um auch auf andere Argumentbreiten zu verallgemeinern.
Tags und Links c++ c++11 compile-time constexpr logarithm