## Binärzahl-Operationen mit Python
### Umwandlung Binär-Dezimal
Nehmen wir `b = '101010'` als Beispiel. Jede Ziffer in diesem String steht an einer bestimmten Position:
^ Position | `0` | `1` | `2` | `3` | `4` | `5` |
^ Ziffer | `1` | `0` | `1` | `0` | `1` | `0` |
Um die Binärzahl in eine Dezimalzahl umzurechnen, müssen wir potenzieren:
$$1 \cdot 2^\color{red}{5} + 0 \cdot 2^\color{red}{4} + 1 \cdot 2^\color{red}{3} + 0 \cdot 2^\color{red}{2} + 1 \cdot 2^\color{red}{1} + 0 \cdot 2^\color{red}{0}$$
Zu jeder Ziffer gehört also die passende Zweierpotenz:
^ Position | `0` | `1` | `2` | `3` | `4` | `5` |
^ Ziffer | `1` | `0` | `1` | `0` | `1` | `0` |
^ Exponent | `5` | `4` | `3` | `2` | `1` | `0` |
^ Potenz | `32` | `16` | `8` | `4` | `2` | `1` |
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. **Zwei separate Variablen**: Eine für die Position und eine für den Exponenten.
2. **Binärstring umkehren**, also aus `'101010'` wird `'010101'`: Jetzt stimmen Position und Exponent überein. [[.:binary_collection#rueckwaerts|Hier]] hat es Ideen.
3. Das Zwischenresultat wird **fortlaufend mit 2 multipliziert**.
++++Lösung|
def binary_to_decimal(b):
"""Wandelt Binärzahl b in Dezimalzahl um."""
d = 0
exponent = len(b) - 1
for digit in b:
if digit == '1':
d = d + 2**exponent
exponent = exponent - 1
return d
print(binary_to_decimal("101010"))
++++
### Umwandlung Dezimal-Binär
Der {{gf_informatik:gfif_zahlensysteme_dossier_hof.pdf#page.8|Restwertalgorithmus wird im Dossier}} erklärt: Wir bilden fortlaufend den Rest und den Ganzzahl-Quotienten. Der Algorithmus funktioniert übrigens für alle Basen!
++++Lösung|
def decimal_to_binary(d):
"""Wandelt Dezimalzahl mit dem Restwertalgorithmus in Binärzahl um."""
b = ""
while d > 0:
rest = d % 2
d = d // 2
b = str(rest) + b
return b
print(decimal_to_binary(42))
++++
### Binär-Addition
Umsetzungsidee:
* Beide Strings paarweise [[gf_informatik:zahlensysteme:binary_collection#rueckwaerts|von rechts nach links]] durchlaufen.
* An jeder Position das Bit aus `a` und `b` sowie einen allfälligen Übertrag addieren.
* Das Resultat-Bit an der Position ist `1`, wenn die Summe `1` oder `3` ist, sonst `0`.
* Tipp: also genau das Resultat von `summe % 2`...
* Der Übertrag auf die nächste Stelle ist `1` wenn die Summe `2` oder `3` ist.
* Also genau dem Resultat von ...?
++++Lösung|
def fill_zeros(b, digits):
while len(b) < digits:
b = "0" + b
return b
def binary_add(a, b):
"""Addiert zwei Binärzahlen beliebiger Länge."""
n = max(len(a), len(b))
a = fill_zeros(a, n)
b = fill_zeros(b, n)
out = ""
carry = 0 # Übertrag
index = n - 1
while index >= 0:
digit_a = int(a[index])
digit_b = int(b[index])
sum = digit_a + digit_b + carry
bit = sum % 2
carry = sum // 2
out = str(bit) + out
index = index - 1
if carry != 0:
out = str(carry) + out
return out
print(binary_add("101010", "10111"))
++++
### Binär-Subtraktion
++++Lösung|
def invert(b):
"""Erstellt einen neuen String, wobei 0en und 1en vertauscht sind."""
result = ""
for digit in b:
if digit == "0":
result = result + "1"
else:
result = result + "0"
return result
def zweierkomplement(b, stellen=8):
"""Berechnet das Zweierkomplement von b in der gewünschten Anzahl Stellen."""
# 1) Auffüllen auf stellen bits
b = fill_zeros(b, stellen)
# 2) Invertieren (1->0, 0->1)
b = invert(b)
# 3) Addiere 1
return binary_add(b, "1")
def binary_subtraction(a, b, stellen=8):
"""Subtraktion als Addition des Zweierkomplements."""
complement = zweierkomplement(b, stellen)
result = binary_add(a, complement)
result = result[-stellen:] # Vorderstes Bit auslassen
return result
++++
### Ausprobieren
Kopiere alle Funktionen oben in die gleiche Python-Datei. Überprüfe danach die Funktionsweise:
a_dec = 42
b_dec = 19
a_bin = decimal_to_binary(a_dec)
b_bin = decimal_to_binary(b_dec)
difference_bin = binary_subtraction(a_bin, b_bin, 8)
difference_dec = binary_to_decimal(difference_bin)
print(f"{a_dec} - {b_dec} = {a_bin} - {b_bin} = {difference_bin} = {difference_dec}")
Resultat:
42 - 19 = 101010 - 10011 = 00010111 = 23