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!
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 = ?$$
Binary to Decimal
Verschiedene Versionen:
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
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