Binärer Logarithmus (log2) Rechner

💻 Zweierpotenzen und Logarithmen

Direkter Zusammenhang zwischen Binärpotenzen und Logarithmen:

\[2^0 = 1 \Rightarrow \log_2(1) = 0\] \[2^1 = 2 \Rightarrow \log_2(2) = 1\] \[2^2 = 4 \Rightarrow \log_2(4) = 2\] \[2^3 = 8 \Rightarrow \log_2(8) = 3\] \[2^{10} = 1024 \Rightarrow \log_2(1024) = 10\]

🔄 Logarithmusgesetze für log₂

Spezielle Rechenregeln für den binären Logarithmus:

\[\text{Produktregel: } \log_2(x \cdot y) = \log_2(x) + \log_2(y)\] \[\text{Quotientenregel: } \log_2\left(\frac{x}{y}\right) = \log_2(x) - \log_2(y)\] \[\text{Potenzregel: } \log_2(x^n) = n \cdot \log_2(x)\] \[\text{Basiswechsel: } \log_2(x) = \frac{\ln(x)}{\ln(2)} = \frac{\ln(x)}{0{,}693}\]

📊 Bit-Berechnungen verstehen

Praktische Bedeutung des binären Logarithmus:

\[\text{Anzahl Bits für } n \text{ Werte: } \lceil\log_2(n)\rceil\] \[\text{Beispiel: } 256 \text{ Werte} \Rightarrow \log_2(256) = 8 \text{ Bits}\] \[\text{Beispiel: } 1000 \text{ Werte} \Rightarrow \lceil\log_2(1000)\rceil = 10 \text{ Bits}\] \[\text{Maximale Werte mit } n \text{ Bits: } 2^n\]

📝 Beispiel 1: Bit-Anzahl bestimmen

Aufgabe: Wie viele Bits braucht man für 1000 verschiedene Werte?
Berechnung:

\[\text{Benötigte Bits} = \lceil\log_2(1000)\rceil\] \[\log_2(1000) = \frac{\ln(1000)}{\ln(2)} \approx \frac{6{,}908}{0{,}693} \approx 9{,}97\] \[\lceil9{,}97\rceil = 10 \text{ Bits}\] \[\text{Verifikation: } 2^{10} = 1024 \geq 1000 \checkmark\]

Antwort: 10 Bits können 1024 verschiedene Werte darstellen

📝 Beispiel 2: Algorithmus-Komplexität

Aufgabe: Binäre Suche in Array mit 1.000.000 Elementen
Berechnung:

\[\text{Maximale Schritte} = \lceil\log_2(n)\rceil\] \[\log_2(1.000.000) \approx \log_2(2^{20}) = 20\] \[\text{Genauer: } \log_2(1.000.000) \approx 19{,}93\] \[\lceil19{,}93\rceil = 20 \text{ Schritte maximum}\]

Informatik: Binäre Suche hat O(log₂ n) Komplexität

📝 Beispiel 3: Binärbaum-Tiefe

Aufgabe: Minimale Tiefe für vollständigen Binärbaum mit 1000 Knoten
Berechnung:

\[\text{Minimale Tiefe} = \lfloor\log_2(n)\rfloor\] \[\log_2(1000) \approx 9{,}97\] \[\lfloor9{,}97\rfloor = 9\] \[\text{Maximale Tiefe} = \lceil\log_2(n)\rceil = 10\]

Datenstrukturen: Balancierte Bäume haben log₂ n Höhe

💻 Bit-Berechnungstabelle

📊 Big-O Notation

Häufige Algorithmus-Komplexitäten mit log₂:

\[O(\log n): \text{ Binäre Suche, Heap-Operationen}\] \[O(n \log n): \text{ Merge Sort, Heap Sort, Quick Sort (average)}\] \[O(\log^2 n): \text{ Einige Divide-and-Conquer-Algorithmen}\] \[\text{Beispiel: } n = 1.000.000 \Rightarrow \log_2(n) \approx 20 \text{ Schritte}\]

🔄 Divide-and-Conquer

Rekursionstiefe bei Divide-and-Conquer-Algorithmen:

\[\text{Rekursionstiefe} = \log_2(n)\] \[\text{Master Theorem: } T(n) = aT(n/b) + f(n)\] \[\text{Für } a = 2, b = 2: T(n) = 2T(n/2) + O(n)\] \[\text{Lösung: } T(n) = O(n \log n)\]

📡 Shannon-Entropie

Informationsgehalt und Entropie:

\[\text{Informationsgehalt: } I = -\log_2(P)\] \[\text{Entropie: } H = -\sum_{i} P_i \log_2(P_i)\] \[\text{Beispiel: Münzwurf } P = 0{,}5\] \[I = -\log_2(0{,}5) = -\log_2(2^{-1}) = 1 \text{ Bit}\]

📊 Logarithmus-Vergleichstabelle

💻 Code-Beispiele

Implementation in verschiedenen Programmiersprachen:

JavaScript:
Math.log2(x) // binärer Logarithmus
Math.log2(8) // = 3

Python:
import math
math.log2(x) # binärer Logarithmus
math.log2(16) # = 4

C++:
#include <cmath>
log2(x) // binärer Logarithmus
log2(64) // = 6

Hinweis: Moderne Programmiersprachen haben eine eigene log2-Funktion