log₂(x) beantwortet die Frage: Welche Potenz von 2 ergibt x? Also 2^(log₂(x)) = x. Beispiele: log₂(8) = 3 (denn 2³ = 8), log₂(256) = 8 (denn 2⁸ = 256). In der Informatik besonders wichtig für Binärsystem und Algorithmenanalyse.
Warum ist log₂ in der Informatik so wichtig?
Computer arbeiten im Binärsystem (Basis 2). log₂ gibt an: Wie viele Bits braucht man für n Zustände (ceil(log₂(n))), wie tief ist ein balancierter Binärbaum (log₂(n)), wie viele Schritte braucht binäre Suche (O(log₂ n)). Speichergrößen sind Zweierpotenzen: 1 KiB = 2¹⁰ = 1.024 Bytes.
Wie rechne ich log₂ in log₁₀ oder ln um?
Mit der Basiswechselformel: log₂(x) = ln(x)/ln(2) = log₁₀(x)/log₁₀(2). Die Umrechnungsfaktoren: log₂(x) = log₁₀(x) · 3,3219... = ln(x) · 1,4427...
Was ist eine Zweierpotenz?
Eine Zweierpotenz ist eine Zahl der Form 2^n: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... Diese Zahlen haben einen ganzzahligen log₂. In der Informatik sind sie fundamental für Speichergrößen, Adressräume und effiziente Berechnungen.
Was ist die Bit-Anzahl einer Zahl?
Die Anzahl der Bits, die zur Darstellung einer positiven ganzen Zahl n benötigt werden, ist ceil(log₂(n+1)). Beispiel: Für n = 255 braucht man ceil(log₂(256)) = 8 Bits (1 Byte). Für n = 1.000 braucht man ceil(log₂(1001)) = 10 Bits.
Gilt die Logarithmus-Eigenschaft auch für log₂?
Ja, alle Logarithmenregeln gelten unabhängig von der Basis: log₂(a·b) = log₂(a) + log₂(b), log₂(a/b) = log₂(a) - log₂(b), log₂(a^n) = n·log₂(a), log₂(1) = 0, log₂(2) = 1.
Was ist die O-Notation mit log₂?
In der Algorithmenanalyse beschreibt O(log n) logarithmische Komplexität (die Basis ist dabei irrelevant, da alle Logarithmen nur um einen konstanten Faktor abweichen). Beispiele: binäre Suche O(log n), ausgeglichene Bäume O(log n), Merge Sort O(n log n).
Für welche Zahlen ist log₂ definiert?
Im Bereich der reellen Zahlen ist log₂(x) nur für x > 0 definiert. Für x = 1 ist das Ergebnis 0. Für Werte zwischen 0 und 1 ist das Ergebnis negativ. Für 0 und negative Zahlen gibt es keinen reellen Logarithmus.
Warum ist die Basis beim O-Logarithmus egal?
Logarithmen mit unterschiedlichen Basen unterscheiden sich nur um einen konstanten Faktor. In der O-Notation werden konstante Faktoren nicht betrachtet. Für konkrete Rechenwerte ist die Basis trotzdem wichtig, weil log₂(1.024) ein anderes Ergebnis liefert als log₁₀(1.024).
Wie unterscheide ich log₂ von Bitlänge?
log₂(n) liefert den Exponenten zur Basis 2. Die Bitlänge beschreibt dagegen, wie viele Binärstellen eine ganze Zahl braucht. Für positive ganze Zahlen gilt meist floor(log₂(n)) + 1. Die Werte 0 bis 255 passen in 8 Bits, der Wert 256 braucht bereits 9 Bits.