Beweisen Sie die folgende Formel: (Summe (b_(i)2^{i} )mod 2 = b_(0)

Question

Aufgaben:

1. Beweisen Sie die folgende Formel:

\( \left(\sum \limits_{i=0}^{n-1} b_{i} \cdot 2^{i}\right) \bmod 2=b_{0} \)

wobei \( n \in \mathbb{N}, b_{i} \in\{0,1\}, i \in\{0, \ldots, n-1\} \) und \( mod \) der Rest der ganzzahligen Division ist.

2. Wie kann die Formel aus obiger Teilaufgabe zur Konvertierung einer nichtnegativen Ganzzahl \( x \) in das Binärsystem verwendet werden? Entwickeln Sie einen Algorithmus, der angibt, wie die Konvertierung von \( x \in \mathbb{N}_{0} \) durchzuführen ist.

Hinweis: Vergessen Sie nicht, die Eingaben und Ausgaben des Algorithmus zu definieren sowie eine korrekte Endbedingung zu formulieren.

Answer 1

Zu 1)

Zweierpotenzen gehen ganz prima durch 2, ohne dass ein Rest bleibt. Nur 2⁰=1 ist die Ausnahme.

Zu 2)

$$\frac{1}{2}\left(\sum_{i=0}^{n-1}b_i\cdot2^i -b_0\right)\operatorname{mod} 2=b_1$$Ich mach Dir ein Beispiel:

13 mod 2 = 1

6 mod 2 = 0

3 mod 2 = 1

1 mod 2 = 1

Ergebnis: 13 = 1101₂

Comments

Die zweite habe ich nicht ganz verstanden...

---

In 1) hast Du gesehen, wie man die letzte Ziffer b₀ bestimmt. Der Trick ist jetzt, die zu entfernen, und dann b₁ zur letzten Ziffer zu machen. Die Formel dafuer hab ich Dir aufgeschrieben. Dann geht es immer so weiter, bis man alle Ziffern hat. Siehe Bsp.