Ganzzahlige Logarithmusbasis 2 in O (1)

Es ist oft notwendig, den gesamten Teil der Logarithmusbasis 2 einer ganzen Zahl zu berechnen.



Die direkte Entscheidung besteht darin, eine Schleife zu erstellen und in dieser Schleife die Zahl ständig durch zwei zu teilen, bis sie Null wird. Wie viele solcher Unterteilungen aufgetreten sind, ist der Wert des Logarithmus. Ja, diese Methode funktioniert und hat das Recht auf Leben, aber ich möchte zeigen, wie dies ohne Zyklen und komplexe Strukturen möglich ist.



Wir wollen also die folgende Formel berechnen:

$$

$$y = [log_2(x)], x - ,$$

Entscheidung

Für diejenigen, die nicht an der Argumentation interessiert sind, werde ich sofort vorgefertigte Funktionen zur Berechnung des Logarithmus geben:

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

Erklärungen

Lassen Sie uns zunächst die Zahl x in eine binäre Notation einer bestimmten Länge konvertieren.



Zum Beispiel Länge = 8, aber das ist nicht wichtig und die Länge der Zahl kann beliebig sein.



Denken Sie nun daran, worauf die Übersetzung einer Zahl in eine binäre Notation basiert. Darstellung der Zahl als Summe von Zweierpotenzen. Die Gradzahl bestimmt die Position des Bits, nämlich 1. Zum Beispiel:$$$45 = 32 + 8 + 4 + 1 = 2^5 + 2^3 + 2^2 + 2^0$... Jene. Potenznummern 5, 3, 2 und 0. Dies bedeutet, dass das 5., 3., 2., 0. Bit gleich 1 ist. Der Rest der Bits zwischen ihnen ist gleich Null. Bits beginnen auf der rechten Seite. Es stellte sich heraus, dass$$$45_{10} = 101101_2$



Es kann angemerkt werden, dass die Übersetzung in die binäre Notation eng mit der Potenzierung zusammenhängt und der Logarithmus die Umkehrung der Potenzierung ist und gleich dem Exponenten ist.

$$

$$2^y = x, y = log_2(x)$$

Darüber hinaus ist der Exponent, auf den Sie 2 erhöhen müssen, die Nummer eines einzelnen Bits in einer binären Notation. Es stellt sich heraus, dass, wenn Sie die Nummer eines einzelnen Bits finden, wir den ganzzahligen Teil des Wertes des Logarithmus auf Basis zwei erhalten. Wenn beispielsweise 32 = 100000 ist, befindet sich das eine Bit an fünfter Stelle, sodass der Logarithmus 5 ist.



Da es jedoch mehrere geben kann, nicht 1, stellt sich die Frage, welches Bit zum Finden des Logarithmus benötigt wird. Die Antwort ist die Nummer des letzten Bits, beginnend auf der rechten Seite der Zahlenaufzeichnung, da die höchste Zweierpotenz den gesamten Teil des Logarithmus bestimmt, der Rest den Bruchteil des Logarithmus ausmacht.



Betrachten Sie ein anderes Beispiel - eine Zahl$$$45_{10} = 101101_2$... Das letzte Bit steht an fünfter Stelle, daher ist der ganzzahlige Teil des Logarithmus von 45 5. und tatsächlich$$$log_2(45)=5.4919$... Wir verwerfen den Bruchteil und lassen 5.



Es funktioniert auch mit anderen Zahlen.



Als Ergebnis haben wir festgestellt, dass der ganzzahlige Teil des Logarithmus gleich der Nummer des letzten Bits ist und von rechts zählt. Frage: Wie finde ich die Nummer des letzten Bits?



Dafür gibt es Funktionen, die auf bitweisen Operationen basieren, die ich in dem Buch von G. Warren "Algorithmische Tricks für Programmierer" gefunden habe.

• Abrunden auf eine Zweierpotenz (oder Hervorheben des letzten Bits in der binären Notation einer Zahl). Sie können zwar aufrunden, aber dann wird auch der Wert des Logarithmus aufgerundet.
• Zählen der Anzahl einzelner Bits in der binären Notation einer Zahl

Beide Funktionen sind dort gut beschrieben, und ich habe ihren Code früher angegeben.



Unter Verwendung dieser beiden Funktionen lautet der Algorithmus zum Berechnen des Algorithmus wie folgt:

1. Wählen Sie das letzte Bit in der Nummer. Jetzt wurde die Nummer als 100000 geschrieben
2. Subtrahieren Sie eins von der resultierenden Zahl. Dann lautet die Nummer wie folgt: 011111
3. Zählen Sie die Anzahl der Einheitsbits und dies ist der ganzzahlige Wert des Logarithmus

Außergewöhnliche Situation

Der Logarithmus hat eine Ausnahmesituation, wenn x = 0. Theoretisch existiert ein solcher Algorithmus nicht (oder in der Grenze ist er gleich -∞). Da wir jedoch beim Programmieren ein wenig von den Gesetzen der Mathematik abweichen, funktionieren die Funktionen auch dann noch, wenn die Eingabe der Funktion Null ist. In diesem Fall beträgt der Wert des Logarithmus 32 (wenn die Zahl 32-Bit ist). Dies geschieht, weil die Funktion des Rundens auf die nächste Zweierpotenz 0 ergibt, dann subtrahieren wir eins von Null und erhalten die Zahl 0xFFFFFFFF, und diese Zahl enthält 32 Einheiten, sodass der Logarithmus 32 beträgt.



Ja, aus mathematischer Sicht ist dies falsch, aber es gibt Fälle. wenn es aus programmtechnischer Sicht nützlich ist.

Zählen der Länge eines Binärcodes

Es ist unwahrscheinlich, dass eine solche Funktion zur Berechnung des mathematischen Logarithmus verwendet wird, da Logarithmen häufiger aus reellen Zahlen und nicht aus ganzen Zahlen betrachtet werden.

Die Berechnung der Länge eines Binärcodes ist in der Praxis jedoch eine häufigere Aufgabe.



Es sei ein Binärcode einer bestimmten Länge gegeben. Dies kann beispielsweise ein Pfad in einem Binärbaum sein. Wenn ein einzelnes Bit vor diesen Code geschrieben wird, können Sie die Länge dieses Codes ohne Verwendung von Hilfsvariablen berechnen, indem Sie einen ganzzahligen Logarithmus verwenden.



Lassen Sie zum Beispiel den Code 0001110110 angeben. Er wird beispielsweise in eine Zelle mit 32 Bit geschrieben, und wir müssen häufig die Länge dieses Codes lesen. Fügen Sie dazu vor dem Code ein zusätzliches Bit hinzu.



Wir erhalten: 10001110110. Und jetzt können wir die Länge dieses Codes sicher über den ganzzahligen Logarithmus berechnen, ohne die Länge dieses Codes separat an einer anderen Stelle zu speichern.



Wenn wir die Länge des Codes berücksichtigen, in der alle Nullen sind, gibt die Funktion die Länge = 32 zurück, was möglicherweise falsch ist. Daher muss diese Situation vorausgesehen werden. In einigen Situationen ist es nützlich, dass die Funktion 32 zurückgibt, in anderen beispielsweise Null.

Quellen

1. G. Warren Algorithmische Tricks für Programmierer. Überarbeitete Ausgabe. ", 2004