====== Zahlensysteme ======

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

++++ 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!*

=== Subraktion ===

**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|

Verschiedene Versionen:
<code python>
def binary_to_decimal_1(b):
    d = 0 # decimal nr
    i = 0
    while i < len(b):
        d = d + int(b[len(b)-i-1]) * 2**i # len(b)-i-1 to go through b in reverse order
        i = i + 1
    return d

def binary_to_decimal_2(b):
    d = 0 # decimal nr
    i = 0
    while i < len(b):
        d = d + int(b[-i-1]) * 2**i # can also use negative indices to go through d in reverse order
        i = i + 1
    return d

def binary_to_decimal_3(b):
    d = 0 # decimal nr
    i = len(b) - 1
    power = 1
    while i >= 0:
        d = d + int(b[i]) * power
        power = power * 2
        i = i - 1
    return d
</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 =====

<nodisp 2>
++++Lösung|
<code python>
def binary_to_decimal(b):
    n = len(b)
    d = 0 # decimal number
    for i in range(n):
        d = d + int(b[i]) * 2**(n-i-1)
    return d
 
def decimal_to_binary(d,bits=None):
    b = ""
    while d > 0:
        b = str(d%2) + b
        d //= 2
    if bits:
        while len(b) < bits:
            b = '0' + b
    return b
 
def binary_add(a,b):
    # PREPARE NUMBERS
    a = a.replace(" ","") # remove blanks
    b = b.replace(" ","")
    # ADD 0 TO HAVE SAME LENGTH
    while len(a) < len(b): a = "0" + a
    while len(b) < len(a): b = "0" + b
 
    # ADD NUMBERS
    n = len(a)
    out = "" # string mit Resultat
    rest = 0
    for i in range(n):
        k = n-1-i
        summe = int(a[k])+int(b[k])+rest
        out = str(summe%2) + out
        rest = summe // 2
    if rest != 0:
        out = str(rest) + out
    return out

def binary_add_list(L):
    # adds all binary numbers in list L
    b = L[0]
    for i in range(len(L)-1):
        b = binary_add(b,L[i+1])
    return b

def binary_invert(a):
    a = a.replace(" ","") # remove blanks
    out = ""
    for c in a:
        if c == "0":
            out += "1"  
        else:
            out += "0"
    return out

def binary_complement(a,bits=None):
    a = a.replace(" ","") # remove blanks
    if bits == None: bits = len(a)
    while len(a) < bits:
        a = "0" + a
    out = binary_add(binary_invert(a),"1")
    if len(out) > bits:
        out = out[1::]
    return out

def binary_sub(a,b):
    a = a.replace(" ","") # remove blanks
    b = b.replace(" ","")
    while len(a) < len(b): a = "0" + a
    while len(b) < len(a): b = "0" + b
    bits = len(a)
    # extend by one bit
    a = "0" + a
    b = "0" + b
    out = binary_add(a,binary_complement(b))
    return out[len(out)-bits::] # make sure to cut right number of bits from left side
    

def binary_mult(a,b):
    # PREPARE NUMBERS
    a = a.replace(" ","") # remove blanks
    b = b.replace(" ","")
    out = ""
    for i in range(len(a)):
        j = len(a)-1-i
        if a[j] == "1":
            out = binary_add(out,b + i*"0")
    # remove zeros on left side
    while out[0] == "0" and len(out) > 1:
        out = out[1::]
    return out


print(binary_to_decimal("0010000100"))
print(decimal_to_binary(42))
print(binary_add("10101010","101000"))
print(binary_complement("00101101"))
print(binary_sub("1000 0000","0001 1111"))
print(binary_sub("1010 1011","0110 1011"))
print(binary_sub("1111 0010","1000 1111"))
# binary multiplication
print(binary_mult("1101","1111") == "11000011")
print(binary_mult("10010010","01100011") == "11100001110110")
print(binary_mult("11111011","11101011") == "1110011001101001")
print(binary_mult("1100101100111101","1110011101111010") == "10110111110001001110011000010010")
</code>
++++

++++Function Testing|

<code python>
### FUNCTION TESTING CODE
for i in range(1000):
    da = random.randint(0,165)
    db = random.randint(0,165)
    if db > da: da,db = db,da
    a = bin(da)[2:]
    b = bin(db)[2:]
    if not a == invert(invert(a)):
        print("ERROR Invert: ",a,invert(a))
    
    if not binary_add(a,b) == bin(int(a,2)+int(b,2))[2:]:
        print("ERROR Add: ",a,b)
    
    if not binary_sub(a,b) == bin(int(a,2)-int(b,2))[2:]:
        print("ERROR Sub: ",a,b)
</code>
++++

++++Exercise Generator|
<code python>
### EXERCISE GENERATOR
for i in range(3):
    da = random.randint(128,256)
    db = random.randint(128,256)
    if db > da: da,db = db,da
    a = bin(da)[2:]
    b = bin(db)[2:]    
    print("Berechne schriftlich von Hand (Bemerkung & isPencil-Feld), trage Resultat ins Antwortfeld ein:\n" + a + " + " + b )
    print("LOESUNG: " + binary_add(a,b) + "\n")

for i in range(3):
    da = random.randint(128,256)
    a = bin(da)[2:]
    print("Berechne schriftlich von Hand (Bemerkung & isPencil-Feld), trage Resultat ins Antwortfeld ein. 2-er Komplement in 8-Bit von:\n" + a)
    print("LOESUNG: " + binary_complement(a) + "\n")

for i in range(3):
    da = random.randint(128,256)
    db = random.randint(128,256)
    if db > da: da,db = db,da
    a = bin(da)[2:]
    b = bin(db)[2:]    
    print("Berechne schriftlich von Hand (Bemerkung & isPencil-Feld), trage Resultat ins Antwortfeld ein. Lasse überflüssige Nullen auf linker Seite weg.\n" + a + " - " + b )
    print("LOESUNG: " + binary_sub(a,b) + "\n")

for i in range(3):
    da = random.randint(1,15)
    db = random.randint(1,15)
    if db > da: da,db = db,da
    a = bin(da)[2:]
    b = bin(db)[2:]
    while len(a) < 4: a = '0' + a  
    while len(b) < 4: b = '0' + b  
    print("Berechne schriftlich von Hand (Bemerkung & isPencil-Feld), trage Resultat ins Antwortfeld ein.\n" + a + " * " + b )
    print("LOESUNG: " + bin(da*db)[2:] + "\n")
</code>
++++


</nodisp>