Forum:  Algorithmen / Datenstrukturen
Thema: Zeigen, dass Formel für Berechnung der Bitlänge gilt
Themen-Übersicht
Chrispyk
Junior
Dabei seit: 01.09.2020
Mitteilungen: 8
Themenstart: 2020-09-01 16:46

Guten Tag, ich könnte etwas Hilfe zu folgender Aufgabe gebrauchen:

Die Bitlänge \(l_2(a)\) einer Zahl \(a \in \mathbb{N_0}\) ist die Anzahl der Bits, die zur Darstellung der Zahl benötigt wird, d. h. die Anzahl der Stellen in der Binärdarstellung von \(a.\)

Zeigen Sie:
(i) Für alle \(a \in \mathbb{N}\) gilt \( l_2(a) = \lfloor log_2 (a)\rfloor  + 1\)
(ii)Für alle \(a \in \mathbb{N_0}\) gilt \( l_2(a) = \lceil log_2 (a+1)\rceil \)

Mein Ansatz:
(i)
 \( l_2(a) = \lfloor log_2 (2^n)\rfloor  + 1\)

 \( l_2(a) = \lfloor n\rfloor  + 1\)

Wie stelle ich jetzt einen zusammenhang zwischen \(l_2(a)\) und \(n\) her?
Und wie löst man Floor/Ceiling auf?
Bei der zweiten Aufgabe weiß ich leider noch weniger weiter.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6672
Herkunft: Milchstraße
Beitrag No.1, eingetragen 2020-09-01 19:50

Hallo Chrispyk,

das mit dem n ist doch schon mal ne ganz gute Idee.

Setze einfach \(n:=l_2(a)\). Dann ist \(2^{n-1}\leq a<2^n\). Klar wieso? Bekommst du den Rest nun selbst hin?

Bei (ii) gilt \(2^{n-1}<a+1\leq2^n\). Allerdings sehe ich nicht, wieso die Formel für a = 0 gelten soll. 0 hat doch 1 Binärziffer.


Chrispyk
Junior
Dabei seit: 01.09.2020
Mitteilungen: 8
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-02 10:56

\(n = \lfloor log_2(a) \rfloor + 1\)

mit \(2^{n-1} \le a \lt 2^n\) da \(2^n\) Bits nur die Zahlen von \(0\) bis \(2^{n-1}\) darstellen können.

Das bedeutet, dass die Floorfunktion alles auf genau \(2^{n-1}\) abrundet.

\(n = log_2(2^{n-1})  + 1\)

\(n = n-1 + 1\)

\(n = n\)

Vielen Dank dafür StrgAltEntf.

Zu Aufgabe (ii): Ich hab mal geguckt ob ich die Aufgabe falsch abgetippt habe, ist aber nicht der Fall. Ist mir auch ein Rätsel, ich frag mal meinen Prof.



StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6672
Herkunft: Milchstraße
Beitrag No.3, eingetragen 2020-09-02 12:19

An einer Stelle hast du n mit \(2^n\) verwechselt. Außerdem finde ich noch ein wenig schwammig formuliert, was du schreibst.

Verwende folgende Definition der Floor-Funktion:

Für \(x\in\IR\) ist \(\lfloor x\rfloor\) die (eindeutig bestimmte) ganze Zahl k, für die \(k\leq x<k+1\).

Beweise damit die Aussage (i)

Analog:

Für \(x\in\IR\) ist \(\lceil x\rceil\) die (eindeutig bestimmte) ganze Zahl k, für die \(k-1<x\leq k\).

Beweise damit die Aussage (ii) für a > 0.


Chrispyk
Junior
Dabei seit: 01.09.2020
Mitteilungen: 8
Beitrag No.4, vom Themenstarter, eingetragen 2020-09-02 17:39

\(l_2(a) = n = \lfloor log_2(a) \rfloor + 1\)

Da das \(n\)te Bit denn darstellbaren Zahlenbereich um \(2^{n-1}\) bis \(2^n-1\) erweitert und die Anzahl der Bits repräsentiert, die zur Darstellung von \(a\) benötitgt werden, gilt:
\(2^{n-1} \le a \lt 2^n\).

daraus folgt:
\( log_2(2^{n-1}) \le log_2(a) \lt log_2(2^n) \)

Für \( x\in\IR \) ist \( \lfloor x\rfloor \) die (eindeutig bestimmte) ganze Zahl \(k\), für die \(k\leq x<k+1\) sodass:
\( \lfloor log_2(a)\rfloor = log_2(2^{n-1})\)

\(n = log_2(2^{n-1})  + 1\)

\(n = n-1 + 1\)

\(n = n\)

Die zweite Aufgabe sieht vom Prinzip her gleich aus.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6672
Herkunft: Milchstraße
Beitrag No.5, eingetragen 2020-09-03 22:48

Vermutlich sind deine Gedankengänge richtig. Aber die Form der Darstellung gefällt mir noch nicht.

2020-09-02 17:39 - Chrispyk in Beitrag No. 4 schreibt:
\(2^{n-1} \le a \lt 2^n\).

daraus folgt:
\( log_2(2^{n-1}) \le log_2(a) \lt log_2(2^n) \)

Für \( x\in\IR \) ist \( \lfloor x\rfloor \) die (eindeutig bestimmte) ganze Zahl \(k\), für die \(k\leq x<k+1\) sodass:
\( \lfloor log_2(a)\rfloor = log_2(2^{n-1})\)

\(n = log_2(2^{n-1})  + 1\)

\(n = n-1 + 1\)

\(n = n\)

Ich würde es eher so aufschreiben:

Aus
\(2^{n-1} \le a \lt 2^n\)
folgt
\(\log_2(2^{n-1})\le\log_2(a)\lt\log_2(2^n)\),
also
\(n-1 \le\log_2(a) \lt n\).

Für \( x\in\IR \) ist \(\lfloor x\rfloor\) die (eindeutig bestimmte) ganze Zahl \(k\), für die \(k\leq x<k+1\)

Mit k = n - 1 ist also
\(\lfloor\log_2(a)\rfloor=n-1\)
bzw.
\(n=\lfloor\log_2(a)\rfloor+1\)

Grüße
StrgAltEntf


Chrispyk
Junior
Dabei seit: 01.09.2020
Mitteilungen: 8
Beitrag No.6, vom Themenstarter, eingetragen 2020-09-04 13:43

Ja, die Darstellung fällt mir öfter schwer.
Vielen Danke für deine Hilfe.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249238=5103
Druckdatum: 2021-02-26 19:13