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

<bottom-exercise session="page" id="bin2dec">
<script type="text/x-starter">
def binary_to_decimal(b):
    """Wandelt Binärzahl b in Dezimalzahl um."""
</script>
<script type="text/x-test">
assert binary_to_decimal("101010") == 42
assert binary_to_decimal("1000011") == 67
</script>
<script type="text/x-solution">
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"))
</script>
</bottom-exercise>


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

<bottom-exercise session="page" id="dec2bin">
<script type="text/x-starter">
def decimal_to_binary(d):
    """Wandelt Dezimalzahl mit dem Restwertalgorithmus in Binärzahl um."""

</script>
<script type="text/x-test">
assert decimal_to_binary(42) == "101010"
assert decimal_to_binary(67) == "1000011"
</script>
<script type="text/x-solution">
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))
</script>
</bottom-exercise>
### Binär-Addition

Die Addition von Binärzahlen erfolgt wie die schriftliche Addition von Dezimalzahlen: Jede Stelle wird für sich addiert, dabei ergibt sich der Wert für diese Stelle im Resultat sowie der Übertrag ("Behalte") für die nächste Stelle. Ein Übertrag erfolgt, sobald die Stellensumme die Zahl 2 erreicht.

{{.:binary_solutions:pasted:20260428-152720.png?nolink&283}}

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.
    * Achtung: Die einzelnen Positionen eines Strings sind die Buchstaben `'0'` oder `'1'`, nicht die Zahlen `0` oder `1`. Wandle sie mit `int()` in Zahlen um!
  * 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 ...?

<bottom-exercise id="binary-add" showsolution>
<script type="text/x-starter">
def binary_add(a, b):
    """Addiert zwei Binärzahlen beliebiger Länge."""
    # 1) Beide Zahlen auf die gleiche Länge auffüllen mit Nullen.
    # 2) Von rechts nach links über die einzelnen Stellen laufen.
    # 3) An jeder Stelle: Resultat und Übertrag berechnen.

print(binary_add("11001011", "10101110"))
</script>
<script type="text/x-test">
assert binary_add("101", "010") == "111"
assert binary_add("101", "001") == "110"
assert binary_add("101", "011") == "1000"
assert binary_add("101", "10") == "111"
assert binary_add("101010", "10111") == "1000001"
</script>
<script type="text/x-solution">
def fill_zeros(b, digits):
    """Füllt einen Binärstrings links bis zu digits Stellen mit Nullen auf."""
    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     # Resultat-Bit ist 1, wenn die Summe ungerade ist
        carry = sum // 2  # Übertrag ist 1, wenn die Summe 2 oder 3 ist
        out = str(bit) + out

        index = index - 1
        
    if carry != 0:
        out = str(carry) + out
    return out

print(binary_add("101010", "10111"))
</script>
</bottom-exercise>


### Binär-Subtraktion
Für die Subtraktion im Binärsystem wird das {{gf_informatik:gfif_zahlensysteme_dossier_hof.pdf#subsection.3.4|Zweierkomplement}} des Subtrahends _addiert_. Wir benötigen also Code für das Berechnen des Zweierkomplements:

1. Auffüllen mit Nullen auf die gewünschte Anzahl Bits
2. Invertieren
3. `"1"` addieren mit Binär-Addition

Der Code aus der vorherigen Aufgabe wird für die Addition benötigt.

<bottom-exercise id="binary-subtract" showsolution style="max-height:20lh;">
<script type="text/x-starter">
def invert(b):
    """Erstellt einen neuen String, wobei 0en und 1en vertauscht sind."""

def zweierkomplement(b, stellen=8):
    """Berechnet das Zweierkomplement von b in der gewünschten Anzahl Stellen."""
    # 1) Auffüllen auf stellen bits
    # 2) Invertieren (1->0, 0->1)
    # 3) Addiere 1

def binary_subtraction(a, b, stellen=8):
    """Subtraktion als Addition des Zweierkomplements."""

print(binary_subtraction("1000", "111"))
</script>
<script type="text/x-test">
assert binary_subtraction("1000", "111") == "00000001"
</script>
<script type="text/x-solution">
def fill_zeros(b, digits):
    """Füllt einen Binärstrings links bis zu digits Stellen mit Nullen auf."""
    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
    
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
</script>
</bottom-editor>


### Ausprobieren

Kopiere alle Funktionen oben in die gleiche Python-Datei. Überprüfe danach die Funktionsweise:

<bottom-editor session="page">
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}")
</bottom-editor>

Resultat:
<code>
42 - 19 = 101010 - 10011 = 00010111 = 23
</code>