Zahlensysteme [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Zahlensysteme ======

**{{ :gf_informatik:gfif_zahlensysteme_dossier.pdf |Dossier Zahlensysteme}}**

++++ Lernziele|

Prüfungsrelevant ist alles, was in den Lektionen und Übungen behandelt wurde. Die Lernziele unten dienen als Gradmesser und sind nicht unbedingt komplett.

**Erklären:**
   * Was ist ein Zahlensystem? Erkläre mit Fachbegriffen.
   * Warum ist das Binärsystem wichtig in der Informatik?
   * Was bedeutet die Bit-Zahl bei einer Computerarchitektur?
   * Interpretation von (Binär-)Zahlen: Wie kann man eine gegebene Zahl auf verschiedene Arten interpretieren?
   * Wie stellt man negative Zahlen binär dar? Warum macht man das genau so?
   * Warum Hexadezimalsystem sehr praktisch ist, wenn man mit Binärzahlen arbeitet

**Rechnen:**
von Hand und direkt (also nicht z.B. vor Addition in 10er-System umrechnen):
   * Umrechnen binär -> dezimal
   * Uhrzeit von Binäruhr bestimmen
   * Umrechnen dezimal -> binär
   * binär addieren
   * 2er-Komplement bestimmen
   * binär subtrahieren
   * binär multiplizieren
   * direkt Umrechnen binär <-> hexadezimal
   * umrechnen: hexadezimal <-> dezimal

**Code:**
   * Umrechnen binär -> dezimal
   * Umrechnen dezimal -> binär
   * binär addieren
   * 2er-Komplement bestimmen (verwende binäre Addition)
   * binär subtrahieren (verwende 2er-Komplement und binäre Addition)

++++

==== Zusätzliche Infos ====

==== Erklärung negative Binärzahlen & Subtraktion ====

=== Negative Zahlen & 2er-Komplement ===

Computer arbeiten immer mit fixen Bitlängen. Zum Beispiel sind moderne Computer 64-Bit Computer. Das heisst, sie rechnen intern immer mit Zahlen mit einer Länge von 64 Bit.In den 80er-Jahren hingegen war 8-Bit der Standard. Lass uns einen solchen betrachten:

Möchte ein solcher Computer die Dezimalzahl 42 speichern, so speichert er die Binärzahl $0010\,1010$. Beachte,
dass die beiden Nullen links eigentlich unnötig sind, aber es müssen immer alle Bits gesetzt sein. Ein solcher Computer kann insgesamt $2^8 = 256$ verschiedene Zahlen darstellen. Wenn man einen Computer hat, der nur mit positiven ganzen Zahlen rechnen soll, ist die kleinste Zahl $0000\,0000 = 0$ und die grösste $1111\,1111 = 255_{10}$. Wenn man aber einen Computer haben möchte, der sowohl positive als auch negative Zahlen darstellen kann, müssen sich die positiven und negativen Zahlen die $256$ möglichen Plätze *teilen*. Der Fairness halber macht es Sinn, dass die positiven und negativen Zahlen jeweils die Hälfte der möglichen Plätze erhalten.

Es wird dann so gemacht, dass positive Zahlen mit einer $0$ links beginnen und negative Zahlen mit einer $1$. Die Dezimalzahl $+42$ wäre dann also die Binärzahl $0010\,1010$. Die positiven Zahlen gehen dann also von $0000\,0000 = 0$ bis $0111\,1111 = 127$. Es ist also *nicht* möglich, auf einem solchen Computer die Zahl $200$ zu speichern!

Doch welcher Dezimalzahl entspricht $1010\,1010$? Auf den ersten Blick mag es Sinn machen, zu denken, dass dies die Dezimalzahl $-42$ sei. Doch dies führt zu einem Problem: Addiert man die beiden Zahlen, so erhält man *nicht Null*:
$$0010\,1010 + 1010\,1010 = 1101\,0100$$

Stattdessen geht man wie folgt vor, um von einer Zahl (z.B. $42_{10} = 10\,1010$) die Gegenzahl ($-42_{10} = ???$) zu finden:

   1. **Bits hinzufügen:** Füge links gegebenenfalls $0$ hinzu, so dass Zahl gewünschte Länge hat. Denke daran: Positive (negative) Zahlen haben links eine 0 (1). Da wir einen $8-$Bit Computer betrachten also:
$$0010\,1010$$
   1. **Invertieren:** Nullen werden zu Einsen, Einsen zu Nullen:
$$1101\,0101$$
   1. **Eins Addieren:** Rechne $+1$:
$$1101\,0110$$

Dementsprechend gilt also $-42_{10} = 1101\,0110$, *falls* wir $8-$Bit Zahlen inkl. negative Zahlen betrachten. Ohne diese Information würde man die Zahl wohl als die positive Zahl $214_{10}$ interpretieren. Man muss also immer ganz klar sagen, *wie man eine jeweilige Zahl zu interpretieren hat!*

=== Subtraktion ===

**Beispiel 1:** Wir wollen in $8$-Bit die folgende Subtraktion durchführen:
$$0110\,1001 - 0001\,1101 = ?$$
Bei der Subtraktion wird die erste Zahl Minuend, die Zweite Subtrahend genannt.

   1. Zuerst müssen wir mithilfe des 2er-Komplements die Gegenzahl vom Subtrahend bestimmen (Invertieren, $+1$): $1110\,0011$
   1. Addiere Minuend mit 2er-Komplement von Subtrahend: $$0110\,1001 + 1110\,0011 = 1\,0100\,1100$$
   1. Beachte, dass wir ein $9.$ Bit aufgelesen haben. Ein $8-$Bit Computer kann dieses aber gar nicht erst speichern und es geht einfach verloren, also ist das Resultat:
$$0110\,1001 - 0001\,1101 = 0100\,1100$$

**Beispiel 2:** Wir wollen berechnen: $$1\,1011 - 101 = ?$$
Beachte, dass hier *keine* Angaben bzgl. Anzahl Bits gemacht werden. Wir fassen deshalb beide Zahlen ($1\,1011$ und $101$) als *positive* Zahlen, auch wenn die Bits ganz links eine $1$ sind. Deshalb müssen wir die beiden Zahlen so erweitern, dass:

   1. beide gleich lang sind
   1. beide links (mind.) eine $0$ haben

Also notieren also beide Zahlen als $6-$Bit Zahlen:
$$01\,1011 - 00\,0101 = ?$$
Jetzt können wir vorgehen wie in Beispiel 1:

   1. 2-er Komplement (Invertieren, $+1$): $11\,1011$
   1. Addieren: $$01\,1011 + 11\,1011 = 101\,0110$$
   1. Zusätzliches 7. Bit ignorieren. Da keine feste Bitzahl angegeben wurde, kann man auch noch die Nullen links ignorieren. Resultat ist also: $$1\,1011 - 101 = 1\,0110$$

$$01\,1011 - 00\,0101 = ?$$


=== Tipps: Code binäre Subtraktion ===

   1. Implementiere die Inversion (Umkehrung) einer Binärzahl, optimalerweise in einer eigenen Funktion.
   1. 2er-Komplement: Verwende dazu deinen Code/deine Funktion von 1. und addiere dann "1" dazu. Dazu kannst du deine `binary_add()`-Funktion von früher verwenden.
   1. Addiere zum Minuend das 2er-Komplement des Subtrahends. Verwende dazu wieder die `binary_add()`.


===== Lösungen =====

++++Binary to Decimal|

Nehmen wir `b = '100101'` als Beispiel. Jede Ziffer in diesem String steht an einer bestimmten Position:
```
Ziffer:   100101
Position: 012345
```
Um die Binärzahl in eine Dezimalzahl umzurechnen, müssen wir potenzieren:
$$1 \cdot 2^\color{red}{5} + 0 \cdot 2^\color{red}{4} + 0 \cdot 2^\color{red}{3} + 1 \cdot 2^\color{red}{2} + 0 \cdot 2^\color{red}{1} + 1 \cdot 2^\color{red}{0}$$

Zu jeder Ziffer gehört also die passende Potenz:
```
Ziffer:   100101
Position: 012345
Potenz:   543210
```
Die Schwierigkeit bei diesem Code ist, dass **Position und Exponent genau gegenteilig sind**: Die Position startet bei $0$ und zählt hoch, der Exponent startet bei $5$ und zählt herunter.

Dieses Problem kann man unterschiedlich lösen. Zwei mögliche Ansätze sind:

   1. Man macht **zwei separate Variablen**: Eine für die Position und eine für den Exponenten.
   2. Man **dreht den Binärstring um**, also aus `'100101'` wird `'101001'`: Jetzt stimmen Position und Exponent überein. Allerdings haben  wir nie besprochen, wie man diese Umkrehrung einfach erreichen kann.

Hier einige mögliche Lösungen für den ersten Ansatz:

<code python>
def binary_to_decimal_1a(b):
    """
    Löse mit zwei Variablen:
    - Variable i (der for-Schleife) zählt alle Positionen durch
    - Variable exponent legt Exponenten fest und zählt herunter
    """
    dec = 0 # Dezimalzahl
    exponent = len(b) - 1 # Exponent Startwert
    for i in range(len(b)): # Schleife über Position
        if b[i] == '1':
            dec = dec + 2**exponent
        exponent = exponent - 1
    return dec

print(binary_to_decimal_1a('100101'))

def binary_to_decimal_1b(b):
    """
    Wie Varianbte 1a, nur gehen wir mit for-Schleife direkt die Elemente des Binärstrings durch (ohne Position) 
    """
    dec = 0 # Dezimalzahl
    exponent = len(b) - 1 # Exponent Startwert
    for nr in b: # Schleife über Position
        if nr == '1':
            dec = dec + 2**exponent
        exponent = exponent - 1
    return dec

print(binary_to_decimal_1b('100101'))

def binary_to_decimal_1c(b):
    """
    Wie Varianbte 1b, nur ohne if. Dafür wandeln wir die Elemente des Binärstrings in eine Zahl um.
    """
    dec = 0 # Dezimalzahl
    exponent = len(b) - 1 # Exponent Startwert
    for nr in b: # Schleife über Position
        dec = dec + int(nr) * 2**exponent
        exponent = exponent - 1
    return dec

print(binary_to_decimal_1c('100101'))

def binary_to_decimal_1d(b):
    """
    Wie Varianbte 1a, nur wird exponent direkt aus i berechnet und muss dadurch nicht in jedem Schritt der Schleife um 1 reduziert werden. 
    """
    dec = 0 # Dezimalzahl
    for i in range(len(b)): # Schleife über Position
        exponent = len(b) - i - 1 # Berechnung Exponent
        if b[i] == '1':
            dec = dec + 2**exponent
    return dec

print(binary_to_decimal_1d('100101'))
</code>

++++

++++Decimal to Binary|

<code python>
def decimal_to_binary(d):
    b = ''
    while d > 0:
        b = str(d % 2) + b
        d = d // 2
    return b
</code>

++++

++++Binary Operations|

<code python>

def binary_add(b1,b2):
    b1 = b1.replace(" ","") # remove all blanks
    b2 = b2.replace(" ","") # remove all blanks
    # make sure strings have same length
    while len(b1) < len(b2):
        b1 = '0' + b1
    while len(b1) > len(b2):
        b2 = '0' + b2
 
    # add binary string
    summe = ''    
    i = len(b1) - 1
    carry = '0'
    while i >= 0:
        if b1[i] == '0' and b2[i] == '0' and carry == '0':
            summe = '0' + summe
            carry = '0'
        elif b1[i] == '1' and b2[i] == '1' and carry == '1':
            summe = '1' + summe
            carry = '1'
        elif (b1[i] == '1' and b2[i] == '1' and carry == '0') or (b1[i] == '1' and b2[i] == '0' and carry == '1') or (b1[i] == '0' and b2[i] == '1' and carry == '1'):
            summe = '0' + summe
            carry = '1'
        else:
            summe = '1' + summe
            carry = '0'
        i = i - 1
    if carry == '1':
        summe = '1' + summe
    return summe
 
def invert(b):
    b = b.replace(" ","") # remove all blanks
    inv = ""
    i = 0
    while i < len(b):
        if b[i] == '0':
            inv = inv + '1'
        else:
            inv = inv + '0'
        i = i + 1
    return inv
 
def complement(b):
    b = b.replace(" ","") # remove all blanks
    b = invert(b)
    b = binary_add(b,'1')
    return b
 
def binary_sub(b1,b2): # calc b1-b2
    b1 = b1.replace(" ","") # remove all blanks
    b2 = b2.replace(" ","") # remove all blanks    
    # make sure strings have same length
    while len(b1) < len(b2):
        b1 = '0' + b1
    while len(b1) > len(b2):
        b2 = '0' + b2
 
    # add additional zero at left (to distinguish between positive and negative numbers)
    b1 = '0' + b1
    b2 = '0' + b2
 
    result = binary_add(b1,complement(b2))
    result = result[1:] # remove first bit
    
    while len(result) > 1 and result[0] == '0': # remove all zeros at beginning (optional)
        result = result[1:]
    return result

def binary_mul(b1,b2):
    b1 = b1.replace(" ","") # remove all blanks
    b2 = b2.replace(" ","") # remove all blanks    
    result = ""
    
    i = len(b1) - 1
    while i >= 0:
        if b1[i] == '1':
            result = binary_add(result,b2)
        b2 = b2 + '0'
        i = i - 1
    
    while len(result) > 1 and result[0] == '0': # remove all zeros at beginning
        result = result[1:]

    return result
</code>

++++



===== Lösungen Code für Lehrpersonen =====