1er Komplementdarstellung

Question

Guten Tag ich habe eine Gleichung von der 1er Komplementdarstellung und es ist mir nicht ganz Schlüssig, wie man von dem vorletzten Schritt auf den letzten kommt. Die Gleichung lauter :

-X_1c = $\sum\limits_{n=0}^{n-1}{(1-x_i)*2^i}$ = $\sum\limits_{n=0}^{n-1}{2^i}$- $\sum\limits_{n=0}^{n-1}{x_i*2^i}$ = 2^n - 1 - |X_1c|

wobei |X_1c| = $\sum\limits_{n=0}^{n-1}{x_i*2^i}$

also genauer gefragt, wie kommt man von $\sum\limits_{n=0}^{n-1}{2^i}$ auf 2^n - 1

Answer 1

Aloha :)

In $(0001'1111)_2$ sind die Bits von 0 bis 4 gesetzt. Eine $1$ dazu addiert ergibt $(0010'0000)_2$, das heißt die Bits 0 bis 4 werden gelöscht, dafür wird Bit 5 gesetzt. Formal haben wir folgende Situation:

$$\left(\sum\limits_{i=0}^{4}2^i\right)+1=2^5\quad\Leftrightarrow\quad\sum\limits_{i=0}^{4}2^i=2^5-1$$Mit dieser Idee ist sofort klar:

$$\sum\limits_{i=0}^{n-1}2^i=2^n-1$$

Answer 2

Die Gleichung $\sum\limits_{i=0}^{n-1}{2^i}$ =2ⁿ - 1 kann man durch vollständige Induktion beweisen.

Comments

Das im binären (zur Basis 2) z.B.

1111 + 1 = 10000

gilt sollte eventuell klar sein. nichts anderes besagt die Gleichung.

Answer 3

Das ist die Formel für die geometrische Reihe.

z.B. für n=4

2⁰ + 2¹ + 2² + 2³ = 2⁴ - 1

 1 + 2 + 4 + 8    = 16 - 1

                   15   =   15