T07-Kodierung-von-Zahlen-und-Zehnerkomplement

Kodierung von Zahlen & Zehnerkomplement

Zusammenfassung

Dieses Thema behandelt die Kodierung ganzer Zahlen in Rechnersystemen — von positional notation über Festkommazahlen bis hin zu Vorzeichen-Darstellungen (Betrag/Vorzeichen, Einerkomplement, Zweierkomplement). Der zentrale Transfer-Skill für die Klausur ist die Verallgemeinerung des Zweierkomplements vom Binärsystem ins Dezimalsystem: das Zehnerkomplement. Die Klausur (A5, 16P) verlangt drei Beweise: (a) Induktion über die geometrische Summenformel, (b) Beweis der Zehnerkomplement-Addition , und (c) Vervollständigung eines Beweises zum Bit-Counting-Trick .

Wichtig: Die Vorlesung lehrt das Zweierkomplement (Basis 2). Die Klausur fragt das Zehnerkomplement (Basis 10) ab. Man muss den Beweis selbstständig auf Basis 10 übertragen.

Exam-Relevanz

Aufgabe 5 — Zehnerkomplement & Bit-Operationen (4 + 4 + 8 = 16 Punkte)

Teilaufgabe Punkte Inhalt
A5a 4P Induktionsbeweis:
A5b 4P Beweis: (Zehnerkomplement-Addition)
A5c 8P Beweis vervollständigen: Bit-Counting mit

Unterschied zwischen Klausuren

Klausur A5c Formel (Einleitung) C-Notation Beweis-Skeleton
WS 2024/25 (Exam) x & (~x + 1)
SoSe 2026 (probeklausur) x & (~x - 1)

Achtung: bedeutet bitweises Komplement (NOT), also in C-Notation. Der Beweis-Skeleton verwendet in beiden Klausuren , das das lowest set bit löscht. Der Einleitungstext nennt abweichende Formeln — möglicherweise Tippfehler oder Kontext. Siehe Abschnitt Bit-Counting Trick für Details.

In beiden Klausuren ist die Definition der Zehnerkomplement-Darstellung gegeben:

mit (Vorzeichen-"Bit") und für .

Zahlensysteme

Definition: Ein Zahlensystem ist ein Tripel mit:

  • : Basis des Stellenwertsystems
  • : -elementige Menge von Ziffern (Symbolen)
  • : umkehrbar eindeutige Abbildung

Übersicht

System Basis Ziffern
Dualsystem (Binär) 2
Oktalsystem 8
Dezimalsystem 10
Hexadezimalsystem 16

Positional Notation (Stellenwertsystem)

Der Wert einer nichtnegativen Festkommazahl

ist

Beispiel ():

Basiskonversion

  • Dezimal Basis : Wiederholte Division durch , Reste ergeben Ziffern (LSB zuerst)
  • Basis Dezimal: Auswerten der obigen Summenformel
  • Binär Oktal: Jeweils 3 Bits 1 Oktalziffer
  • Binär Hex: Jeweils 4 Bits 1 Hexziffer

Festkommazahlen

Eine Festkommazahl hat Vorkommastellen () und Nachkommastellen. Im Folgenden: Basis 2, (keine Nachkommastellen).

Das höchstwertigste Bit ist das Vorzeichenbit:

  • : nichtnegative Zahl
  • : negative Zahl (je nach Darstellung unterschiedlich interpretiert)

Drei Darstellungen negativer Zahlen

Betrag und Vorzeichen (BV):

Einerkomplement (1):

Zweierkomplement (2):

Vergleich (, 3-Bit-Zahlen)
000 0 0 0
001 1 1 1
010 2 2 2
011 3 3 3
100 0 -3 -4
101 -1 -2 -3
110 -2 -1 -2
111 -3 0 -1

Eigenschaften

Eigenschaft BV Einerkomplement Zweierkomplement
Bereich symmetrisch symmetrisch asymmetrisch
Kleinste Zahl
Größte Zahl
Inverses durch kompl. 1. Bit kompl. alle Bits kompl. alle Bits, add. 1
Null 2 Darstellungen 2 Darstellungen 1 Darstellung (eindeutig)

Festkommazahlen mit Nachkommastellen

Für gilt analog:

Einerkomplement mit Nachkommastellen:

Zweierkomplement mit Nachkommastellen:

Bei wird im Einerkomplement die größte darstellbare Zahl subtrahiert; im Zweierkomplement wird mehr subtrahiert als im Einerkomplement, um die Eindeutigkeit der Null zu gewährleisten.

Probleme von Festkommazahlen

  • Größte Zahl: , kleinste positive:
  • Operationen nicht abgeschlossen: nicht darstellbar
  • Assoziativgesetz gilt nicht (Bereichsüberschreitung)

Zweierkomplement

Definition

Äquivalent: Für eine -Bit-Zahl (Bits ) gilt:

Wertebereich

Asymmetrisch: eine negative Zahl mehr als positive.

Inversionslemma

Lemma: Sei eine Festkommazahl, die Festkommazahl, die aus durch Komplementieren aller Bits () hervorgeht. Dann gilt:

Beweisidee (aus Blatt03 Aufgabe 3):

Sei . Dann ist , wobei .

Mit der geometrischen Summenformel :

Daher: .

Einerkomplement-Inversionslemma

Lemma: (Komplementieren aller Bits liefert direkt das Inverse).

Addition und Subtraktion

Die Addition im Zweierkomplement funktioniert wie gewöhnliche Binäraddition; eventuelle Überträge über das höchste Bit hinaus werden verworfen.

Beispiel (4-Bit Zweierkomplement):

:

Ü

:

Overflow-Erkennung

Ein Overflow tritt auf, wenn beide Operanden dasselbe Vorzeichen haben, das Ergebnis aber das entgegengesetzte Vorzeichen trägt.

Beispiel (6-Bit, aus Blatt08 Aufgabe 6):

: — kein Overflow.

: , nicht darstellbar in 6-Bit () — Overflow!

: , nicht darstellbar in 6-Bit — Overflow!

Zehnerkomplement

Dies ist der zentrale Transfer der Klausur. Die Vorlesung lehrt das Zweierkomplement (Basis 2). Die Klausur verlangt das analoge Vorgehen für Basis 10.

Definition

Analog zum Zweierkomplement im Binärsystem definiert man das Zehnerkomplement im Dezimalsystem:

mit (Vorzeichen) und für .

  • : nichtnegative Zahl, Wert
  • : negative Zahl, Wert

Wertebereich (für Ziffern + Vorzeichen)

Asymmetrisch (analog zum Zweierkomplement: ist darstellbar, nicht).

Neunerkomplement (analog zum Einerkomplement)

Komplementieren einer Ziffer : (analog zu im Binärsystem).

Lemma 1 (Neunerkomplement):

Zehnerkomplement: Komplementierung

Das Komplementieren erfolgt analog zum Binärsystem. Im Binärsystem (Basis ) komplementiert man alle Bits mit . Da im Binärsystem und das Vorzeichenbit ist, funktioniert dies auch für das Vorzeichenbit.

Im Dezimalsystem (Basis ) ist . Das Komplementieren der Ziffern erfolgt mit (Neunerkomplement). Das Vorzeichenbit wird jedoch wie im Binärsystem invertiert: .

Warum nicht ? Würde man das Vorzeichenbit mit komplementieren, erhielte man , was kein gültiges Vorzeichenbit ist. Die Zehnerkomplement-Darstellung verlangt . Daher wird das Vorzeichenbit separat behandelt: (flip ), während die restlichen Ziffern mit komplementiert werden.

Zusammenfassung der Komplementierung:

Ziffer Komplementierung
(Vorzeichen, )
für ()

Lemma 2 (Zehnerkomplement):

wobei aus durch Komplementieren aller Ziffern hervorgeht (Vorzeichenbit: , restliche Ziffern: ).

Beweis von Lemma 2 (A5b — 4P)

Zu beweisen:

Sei und mit und für .

Ausmultiplizieren:

Mit der Summenformel aus A5a, angewendet als :

Zusammenfassen ( hebt sich auf):

Erkenne die Definition von :

Daher:

Analogie zum Zweierkomplement: Der Beweis ist strukturell identisch mit dem Zweierkomplement-Beweis aus Blatt03 Aufgabe 3. Im Binärsystem gilt (denn ), im Dezimalsystem gilt (denn ). Der Rest des Beweises verläuft analog.

Verallgemeinerung auf beliebige Basis

Für ein Zahlensystem mit Basis gilt (aus Blatt04 Aufgabe 3d):

  • Komplementieren einer Ziffer :
  • -Komplement (analog Einerkomplement):
  • -Komplement (analog Zweierkomplement):
Binär () Dezimal ()
Einerkomplement Neunerkomplement
Zweierkomplement Zehnerkomplement
Ziffer komplementieren: Ziffer komplementieren:

Worked Example: Zehnerkomplement-Arithmetik

Beispiel (, 4-stellig mit Vorzeichen):

Stelle im Zehnerkomplement dar ():

Für : (negativ), und , also .
, also .

Komplementieren von (positive Zahl, ):

  1. Vorzeichenbit invertieren:
  2. Restliche Ziffern komplementieren ():
  3. Ergebnis: (Neunerkomplement mit invertiertem Vorzeichen)

Probe mit Lemma 2: .

Um das tatsächliche Inverse () zu erhalten, addiere :

Addition im Zehnerkomplement:

Als Ziffernaddition: . Der Übertrag () wird verworfen .

Analogie zum Binärsystem: Im Zweierkomplement funktioniert die Subtraktion als , wobei durch Komplementieren aller Bits und erhalten wird. Der Übertrag über das höchste Bit hinaus wird verworfen. Genauso funktioniert das Zehnerkomplement: durch Komplementieren der Ziffern und , Übertrag über hinaus verwerfen.

Bit-Counting Trick

A5c (8P) — unabhängig von A5a/A5b. Verlangt das Vervollständigen eines Beweises.

Der Trick

Die Operation löscht das niedrigste gesetzte Bit (lowest set bit) von .

Beispiel:

Das Bit an Position 2 (Wert 4) wurde gelöscht. Wiederholung:

Nach 2 Iterationen ist , also hatte ursprünglich 2 gesetzte Bits.

Beweisstruktur (klausurrelevant)

Der Beweis aus der Klausur (sowohl Exam.md als auch probeklausur) hat folgende Struktur:

Sei k := 0.
So lange die Zahl x nicht 0 ist:
  x = a_n..a_{n-i+1} 1 0..0  (wo i die Anzahl an 0 nach der 1 ist)
  ⇐⇒ x - 1 = a_n..a_{n-i+1} 0 1..1
  =⇒ x := x & (x - 1) = a_n..a_{n-i+1} 0 0..0
  k := k + 1
  Jetzt hat x genau eine '1' weniger, während k um genau eins erhöht wird.
End der Schleife.
Insgesamt ist also k genau die Anzahl von Einsern in x am Anfang.

Zu vervollständigen sind die leeren Felder — d.h. man muss die einzelnen Schritte begründen:

  1. Darstellung von : Wenn , hat eine niedrigste 1 an Position (mit Nullen danach):
  2. Subtraktion von 1: (Borrow propagiert durch die Nullen, dreht die 1 zu 0 und alle Nullen zu Einsen)
  3. Bitweises AND: : Die Bits oberhalb von Position bleiben gleich (beide haben dort gleiche Bits), an Position wird , und darunter wird .
  4. Ergebnis: Genau das niedrigste gesetzte Bit wurde gelöscht. Alle anderen Bits unverändert.
  5. Schleifeninvariante: zählt die Anzahl gelöschter Bits = Anzahl der ursprünglichen Einsen.

Popcount-Algorithmus

int popcount(unsigned int x) {
    int k = 0;
    while (x != 0) {
        x = x & (x - 1);  // lösche lowest set bit
        k++;
    }
    return k;
}

Laufzeit: — effizienter als für -Bit-Zahlen mit wenigen Einsen.

Klausurvariante: vs.

Der Beweis-Skeleton verwendet in beiden Klausuren (löscht das lowest set bit). Der Einleitungstext erwähnt jedoch unterschiedliche Formeln:

Klausur Einleitungstext C-Notation Bedeutung
WS 2024/25 x & (~x + 1) : isoliert das lowest set bit
SoSe 2026 x & (~x - 1) : andere Operation

Wichtig: Der Beweis-Skeleton in beiden Klausuren verwendet , nicht die im Einleitungstext genannte Formel. bedeutet bitweises Komplement (). Im Zweierkomplement gilt .

  • : löscht das lowest set bit (der Beweis-Skeleton)
  • : isoliert das lowest set bit (WS 2024/25 Einleitung)

Diese beiden Operationen sind verschieden, aber verwandt: .

In der Klausur: Fülle den Beweis-Skeleton aus, der verwendet. Der Einleitungstext beschreibt möglicherweise den Kontext oder enthält einen Tippfehler. Konzentriere dich auf das, was der Skeleton verlangt.

Induktionsbeweis (Summenformel)

A5a (4P) — Induktionsbeweis der geometrischen Summenformel.

Zu beweisen (Klausur)

Die Klausur (sowohl Exam als auch probeklausur) gibt vor:

Hinweis: Diese Formel ist für Basis 10 mathematisch nicht korrekt (z.B. : ). Die korrekte Formel ist — dies ist die direkte Verallgemeinerung von (Basis 2), denn für und für . Die Klausur formuliert vermutlich oder verwendet die allgemeine geometrische Summenformel . In der Klausur: Beweise die Formel, die tatsächlich gefordert ist.

Beweis: (korrigierte Version)

Induktionsanfang ():

Induktionsvoraussetzung (IV): Für ein festes gelte:

Induktionsbehauptung (IB): Für gilt:

Induktionsschritt ():

Alternative: Allgemeine geometrische Summenformel

ü

Spezialfälle:

Basis Formel Verwendung
Zweierkomplement-Beweis (Blatt03 A3)
Zehnerkomplement-Beweis (A5b)
A5b (direkt anwendbar)

Im Zehnerkomplement-Beweis (A5b) benötigt man die Formel in der Form:

Beweis: (für Zweierkomplement)

IA ():

IV:

IS ():

Typische Klausuraufgabe

Struktur von A5 (16P)

Die Aufgabe besteht aus drei unabhängigen Teilen:

A5a (4P) — Induktionsbeweis:

  • Gegeben: Formel (oder korrigierte Version)
  • Gefordert: Vollständige Induktion (IA, IV, IB)
  • Zeitaufwand: ~4 Minuten
  • Häufige Fehler: Falscher Induktionsanfang, fehlende IV, Rechenfehler im IS

A5b (4P) — Zehnerkomplement-Beweis:

  • Gegeben: Definition
  • Gefordert: Beweis von (wobei komplementierte Ziffern)
  • Werkzeug: Geometrische Summenformel aus A5a, Definition des Zehnerkomplements
  • Transfer: Analog zum Zweierkomplement-Beweis aus Blatt03 Aufgabe 3
  • Zeitaufwand: ~4 Minuten

A5c (8P) — Bit-Counting Beweis:

  • Gegeben: Beweis-Skeleton mit Lücken
  • Gefordert: Lücken ausfüllen und begründen
  • Inhalt: löscht das lowest set bit (bzw. Klausurvariante mit )
  • Hinweis: Probe mit
  • Zeitaufwand: ~7 Minuten
  • Häufige Fehler: Falsche Bit-Darstellung, AND nicht korrekt ausgewertet

Was gegeben ist

  • Die Definition der Zehnerkomplement-Darstellung
  • Die zu beweisenden Formeln
  • Der Beweis-Skeleton für A5c (mit Lücken)

Was erwartet wird

  • Sauberer Induktionsbeweis mit allen Schritten (IA, IV, IS explizit)
  • Algebraische Manipulation der Zehnerkomplement-Definition unter Verwendung der Summenformel
  • Logisches Schlussfolgern beim Bit-Counting-Beweis (Bit-Darstellung, AND-Verhalten)
  • Probe-Rechnung mit dem gegebenen Beispiel

Übungsblätter

Blatt Aufgabe Punkte Inhalt Link
3 Aufgabe 2 4P Konvertierung in BV/Einer-/Zweierkomplement Blatt03
3 Aufgabe 3 3P Beweis Inversionslemma Blatt03
4 Aufgabe 3 8P Neunerkomplement, Zehnerkomplement, Verallgemeinerung Basis Blatt04
4 Aufgabe 4 5P Festkommazahlen mit Nachkommastellen, Zweierkomplement 8-Bit Blatt04
8 Aufgabe 6 3P 6-Bit Zweierkomplement-Addition, Overflow-Erkennung Blatt08

Wichtigste Übungen für A5

  1. Blatt03 Aufgabe 3 — Der Zweierkomplement-Inversionsbeweis. Dies ist die direkte Vorlage für A5b. Man muss diesen Beweis auf Basis 10 übertragen.
  2. Blatt04 Aufgabe 3 — Entwickelt das Neunerkomplement und Zehnerkomplement von Grund auf. Teil d) verlangt die Verallgemeinerung auf beliebige Basis .

Quellen

Typ Titel Link
Slide 2.1 Kodierung von Zeichen k210-Kodierung_von_Zeichen
Slide 2.2 Kodierung von Zahlen k220-Kodierung_von_Zahlen
Exercise Übungsblatt 3 Blatt03
Exercise Übungsblatt 4 Blatt04
Exercise Übungsblatt 8 Blatt08
Exam Klausur WS 2024/25 Exam
Exam Probeklausur SoSe 2026 probeklausur

Priorität

CRITICAL — A5 ist eine von 6 Klausuraufgaben (16P von 96P = 17%). Diese Aufgabe ist rein beweisorientiert und erfordert keine Kreativität, sondern Beherrschung von:

  1. Vollständiger Induktion (Standardtechnik)
  2. Algebraischer Manipulation der Komplement-Definitionen
  3. Bit-Operationen und deren Beweis

Lernstrategie:

  1. Den Zweierkomplement-Inversionsbeweis (Blatt03 A3) auswendig verstehen
  2. Den Transfer auf Basis 10 üben (Blatt04 A3)
  3. Den Bit-Counting-Beweis mit Beispiel durchspieln
  4. Induktionsbeweis der geometrischen Summenformel üben (sowohl als auch )

Zeitbudget in der Klausur: ~15 Minuten für A5 (von 90 Minuten gesamt)