Binärzahlen in r Bits. Implementieren Sie Ihren Algorithmus.

Question

Aufgabe:

Seien a, b ∈ {0, 1}r Binärzahlen in r Bits.

(a) Beschreiben Sie ein Verfahren, das aus a und b die Summe bestimmt, d.h. für minimal mögliches s ein c ∈ {0, 1} s mit φ2,s(c) = φ2,r(a) + φ2,r(b).

(b) Implementieren Sie Ihren Algorithmus (auch in Form von Pseudocode) und erproben Sie ihn an Beispielen.

Answer 1

Antwort mit KI erzeugt

Teil (a) – Beschreibung des Verfahrens

Ein einfaches Verfahren, um die Summe zweier Binärzahlen \(a\) und \(b\) zu bestimmen, die beide \(r\) Bits lang sind, verwendet das Konzept der bitweisen Addition, ähnlich wie die Addition im Dezimalsystem, nur dass es hierbei um Binärzahlen geht und dementsprechend andere Überlaufregeln gelten.

Schritte zur Addition zweier Binärzahlen:

1. Initialisierung: Beginnen Sie von rechts, also mit dem niedrigstwertigen Bit (LSB, least significant bit) beider Zahlen.

2. Addition jedes Bits: Addieren Sie jedes Bit von \(a\) und \(b\) unter Berücksichtigung eines eventuell vorhandenen Übertrags (carry) aus der vorherigen Addition. Für Binärzahlen gibt es vier mögliche Szenarien für die Addition zweier Bits (0 oder 1) plus dem Übertrag:
- \(0 + 0 + 0 = 0\), Übertrag ist \(0\)
- \(0 + 1 + 0 = 1\) oder \(1 + 0 + 0 = 1\), Übertrag ist \(0\)
- \(1 + 1 + 0 = 10\), das Ergebnis ist \(0\) mit einem Übertrag von \(1\)
- \(1 + 1 + 1 = 11\), das Ergebnis ist \(1\) mit einem Übertrag von \(1\)

3. Übertrag: Wenn ein Übertrag vorhanden ist, nachdem das höchstwertige Bit (MSB, most significant bit) addiert wurde, bedeutet dies, dass das Ergebnis ein Bit länger ist als \(a\) und \(b\).

4. Ergebnis: Das Ergebnis der Addition ist eine Binärzahl \(c\) mit minimal möglichem \(s \geq r\), wobei \(\phi_{2,s}(c) = \phi_{2,r}(a) + \phi_{2,r}(b)\).

Teil (b) – Implementierung und Test des Algorithmus

Pseudocode:

function addBinary(a, b):
    # Initialisiere die Übertragsvariable
    carry = 0
    # Initialisiere das Ergebnis
    result = ""
    
    # Beginnen Sie mit dem niedrigstwertigen Bit
    for i from r-1 downto 0:
        # Berechnen Sie die Summe der aktuellen Bits plus Übertrag
        sum = a[i] + b[i] + carry
        
        if sum == 2:
            carry = 1
            result = "0" + result
        elif sum == 3:
            carry = 1
            result = "1" + result
        else:
            carry = 0
            result = str(sum) + result
    
    # Überprüfen Sie, ob ein Übertrag vorhanden ist, fügen Sie ihn hinzu
    if carry == 1:
        result = "1" + result
    
    return result

Python-Beispielcode:

python
def add_binary(a, b):
    max_length = max(len(a), len(b))
    
    # Füllen Sie kürzere Zahlen mit führenden Nullen
    a = a.zfill(max_length)
    b = b.zfill(max_length)
    
    result = ""
    carry = 0
    
    # Iterieren Sie durch die Zahlen rückwärts
    for i in range(max_length - 1, -1, -1):
        sum = carry
        sum += int(a[i]) + int(b[i])
        
        if sum == 2:  # Benötigt einen Übertrag
            carry = 1
            result = "0" + result
        elif sum == 3:  # Ergebnis ist 1, Übertrag für nächsten Schritt
            carry = 1
            result = "1" + result
        else:  # Kein Übertrag, fügen Sie sum direkt ein
            carry = 0
            result = str(sum) + result
            
    # Verarbeiten des letzten Übertrags
    if carry != 0:
        result = "1" + result
    
    return result

# Testen des Algorithmus
a = "1101"  # Dezimal 13
b = "1011"  # Dezimal 11

print(f"{a} + {b} = {add_binary(a, b)}")  # Sollte "11000" ausgeben (Dezimal 24)

In diesem Beispiel werden zwei Binärzahlen \(a = 1101\) und \(b = 1011\) addiert. Der erwartete Ausdruck von \(1101 + 1011\) ist \(11000\), was der dezimalen Summe \(24\) entspricht. Der Python-Code implementiert den oben beschriebenen Algorithmus, fügt bei Bedarf Nullen hinzu, um die Länge beider Zahlen auszugleichen, addiert die Zahlen bitweise und berücksichtigt dabei den Übertrag, um das korrekte Ergebnis zu liefern.