Zahlensysteme

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:

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$$
Invertieren: Nullen werden zu Einsen, Einsen zu Nullen: $$1101\,0101$$
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.

Zuerst müssen wir mithilfe des 2er-Komplements die Gegenzahl vom Subtrahend bestimmen (Invertieren, $+1$): $1110\,0011$
Addiere Minuend mit 2er-Komplement von Subtrahend: $$0110\,1001 + 1110\,0011 = 1\,0100\,1100$$
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:

beide gleich lang sind
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:

2-er Komplement (Invertieren, $+1$): $11\,1011$
Addieren: $$01\,1011 + 11\,1011 = 101\,0110$$
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

Implementiere die Inversion (Umkehrung) einer Binärzahl, optimalerweise in einer eigenen Funktion.
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.
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:

Man macht zwei separate Variablen: Eine für die Position und eine für den Exponenten.
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:

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'))

Decimal to Binary

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

Binary Operations

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

Lösungen Code für Lehrpersonen

Lösung

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")

Function Testing

### 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)

Exercise Generator

### 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")