Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:zahlensysteme [2023-05-25 07:52] – [Code binäre Subtraktion] scagf_informatik:zahlensysteme [2023-06-06 21:30] (aktuell) – [Lösungen] sca
Zeile 25: Zeile 25:
    * binär multiplizieren    * binär multiplizieren
    * direkt Umrechnen binär <-> hexadezimal    * direkt Umrechnen binär <-> hexadezimal
 +   * umrechnen: hexadezimal <-> dezimal
  
 **Code:** **Code:**
Zeile 37: Zeile 38:
 ==== Zusätzliche Infos ==== ==== Zusätzliche Infos ====
  
-=== Beispiel binäre Subtraktion ===+==== Erklärung negative Binärzahlen & Subtraktion ====
  
-Wir wollen berechnen 1101001 - 11101, wobei beide Zahlen als positive Zahlen aufzufassen sind.+=== 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. Bei der Subtraktion wird die erste Zahl Minuend, die Zweite Subtrahend genannt.
  
-   1. Befülle mit 0, so dass beide gleich lang: 1101001 - 0011101 +   1. Zuerst müssen wir mithilfe des 2er-Komplements die Gegenzahl vom Subtrahend bestimmen (Invertieren, $+1$): $1110\,0011$ 
-   1. Füge links ein zusäzliches Bit hinzu, damit wir auch negative Zahlen haben können: 01101001 - 00011101 +   1. Addiere Minuend mit 2er-Komplement von Subtrahend: $$0110\,1001 + 1110\,0011 = 1\,0100\,1100$$ 
-   1. Finde 2er-Komplement von Subtrahend (Invertieren, +1): 11100011 +   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: 
-   1. Addiere Minuend mit 2er-Komplement von Subtrahend: 01101001 + 11100011 = ... +$$0110\,1001 - 0001\,1101 = 0100\,1100$$ 
-   1. Entferne Bit ganz links, da dieses nur für die Berechnung verwendet wurde: 1001100+ 
 +**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 = ?$$
  
  
Zeile 57: Zeile 99:
  
 ===== Lösungen ===== ===== Lösungen =====
- 
-<nodisp 1> 
  
 ++++Binary to Decimal| ++++Binary to Decimal|
Zeile 105: Zeile 145:
 ++++ ++++
  
-++++Binary Add|+++++Binary Operations|
  
 <code python> <code python>
-import random 
  
 def binary_add(b1,b2): def binary_add(b1,b2):
-    # make sure strings have identical length+    b1 = b1.replace(" ","") # remove all blanks 
 +    b2 = b2.replace(" ","") # remove all blanks 
 +    # make sure strings have same length
     while len(b1) < len(b2):     while len(b1) < len(b2):
         b1 = '0' + b1         b1 = '0' + b1
     while len(b1) > len(b2):     while len(b1) > len(b2):
         b2 = '0' + b2         b2 = '0' + b2
-    + 
     # add binary string     # add binary string
     summe = ''         summe = ''    
Zeile 138: Zeile 179:
         summe = '1' + summe         summe = '1' + summe
     return 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> </code>
  
 ++++ ++++
  
-</nodisp> 
  
  
Zeile 257: Zeile 352:
 </code> </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> </nodisp>
  
  • gf_informatik/zahlensysteme.1685001167.txt.gz
  • Zuletzt geändert: 2023-05-25 07:52
  • von sca