Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
198 Aufrufe

Hallo,

kann mir jemand die "Formeln" zur Berechnung der Schritte c) (Dualzahl in Vorzeichen-Betrag-Darstellung) und d) (Dualzahl in Einskomplement-Darstellung; siehe: XWizard-Link) genauer erläutern? Geht dies auch anders?

Viele Grüße

in ZAH-AG von  
erneut getaggt von
0 0
Was verstehen Sie denn nicht? Wie würden Sie es alternativ machen? Bei c) sehe ich eigentlich keine grundlegend andere Möglichkeit, das zu berechnen.
0 0
Ich habe Ihre Frage ein bisschen beantwortungs-freundlicher formatiert.
0 0
Haben Sie das jetzt eigentlich verstanden oder antworten wir hier ins Leere?

3 Antworten

1 Pluspunkt 0 Minuspunkte

Guten Morgen!

 

Als erstes ein kurzer Hinweis: Auf Seite 52/69 in den Tutoriumsfolien von Tut 5 hast du eine gute Übersicht, mit der man die Zahlendarstellungen gut verstehen kann.

Im Aufgabenteil c) wird gefragt, wie man den BitString als "Dualzahl in Vorzeichen-Betrag-Darstellung" interpretiert. Wie der Name schon sagt: das erste Bit steht für das Vorzeichen (in diesem Fall eine 1, also ein Minus). Der Rest steht für den Betrag. Du schreibst also ein Minus vor die Zahl und den Betrag rechnest du wie in Aufgabe b).

Im Aufgabenteil d) wird gefragt, wie man den BitString als "Dualzahl in Einskomplement-Darstellung" darstellt. Hier schaust du am besten mal auf den Zahlenstrahl, den ich angehängt habe. 

Die höchste Zweierpotenz ganz links ist negativ also -(2^31) Jedoch wird die in der Einskomplementdarstellung noch mit 1 subtrahiert. Der Rest ist wie in Aufgabenteil b). 

Ich hoffe das hilft,

Felix (Tutor)

von uwdtl uwdtl Tutor(in) (103k Punkte)  
0 Pluspunkte 0 Minuspunkte

Also ich habe es mir so erschlossen:

c) Der erste (linkeste) Bit steht für das Vorzeichen (1 bedeutet negativ), alle danach folgenden Bits werden entsprechend ihrer Stelle in eine Dualzahl umgeformt. So ergibt sich dann - (2^(28)+2^(27)+....)

Vielleicht könnten Sie mir kurz rückmelden, ob das so richtig ist.

d) Hier verstehe ich noch nicht die -[(2^(n-1))-1] ganz am Anfang der Auflösung. Ist dies eine Regel, dass man diese immer davor schreibt bei der Interpretation als Dualzahl in Eins-Komplement-Darstellung?

von  
0 0
Ja, c) ist soweit korrekt. Die Stelligkeit der Bits werden von rechts nach links von 0 bis 30 hochgezählt und das letzte Bit ist das Vorzeichenbit. Die Formel für 1- und 2-Komplement ergibt sich halt daraus, wie diese Systeme definiert sind. Felix hat das schon ganz gut in seiner Antwort dargestellt. Ich überlege mir mal, ob ich das noch intuitiver machen kann...
0 Pluspunkte 0 Minuspunkte

Zu c) wurde schon einiges Richtiges gesagt, ich denke, das können wir abhaken?

Zu d): Sagen wir mal, wir haben die Zahl $01100$ in 1-Komplementdarstellung (XWizard-Link). Dann können wir den Wert bestimmen wie in c), indem wir von links nach rechts die Zweierpotenzstelligkeiten durchgehen und jeweils mit dem Bit an dieser Stelle multiplizieren, also:
$$0 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2 + 1 \cdot 2^3 + 0 \cdot 2^4 = 12$$
Das funktioniert, weil wir hier den Fall einer positiven Zahl haben. Hätten wir dagegen den negativen Fall, wenn vorne also eine $1$ stünde, etwa $11100$ (XWizard-Link), dann müssten wir - naiv - den String zunächst invertieren zu $00011$, daraus den Wert
$$1 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 0 \cdot 2^4 = 3$$
berechnen und zuletzt, weil wir invertiert haben, ein Minus davorsetzen. Das Ergebnis wäre also $-3$.

Aber was haben wir hier eigentlich gemacht? Durch die Invertierung haben wir sozusagen in den letzten vier Stellen vom höchsten darstellbaren (absoluten) Wert (also $2^4-1=15$) den absoluten Wert des nicht-invertierten Strings, also $12$ abgezogen - und dann das ganze mit -1 multipliziert. Will man also eine geschlossene mathematische Form für das Vorgehen bei der Berechnung des Dezimalwerts aus einer 1-Komplementdarstellung angeben, dann ergibt sich genau die Formel aus der Aufgabe, nämlich, wenn die Anzahl der Bits $32$ ist:
$$1 \cdot 2^3 +1 \cdot 2^{22} + 1 \cdot2^{24} + 1 \cdot2^{27} + 1 \cdot2^{28}  \underbrace{- 1 \cdot(2^{31}-1)}_{\mbox{Invertierung}}$$
(Der String war $1001 1001 0100 0000 0000 0000 0000 1000$.) Wir addieren also immer die hinteren $31$ Stellen, ohne die vorderste, wie in c) zusammen - die Nuller-Bits habe ich weggelassen -, und subtrahieren am Ende noch diesen festen Wert, multipliziert mit der vordersten Stelle, sodass im Fall, dass diese $0$ ist, einfach nichts passiert und im Fall einer $1$ gerade die Invertierung stattfindet.

Für einen allgemeinen Binärstring $x \in \{0, 1\}^n$ ergibt sich also diese Formel (wobei wir von $0$ nach $n-1$ von rechts nach links durchgehen):
$$\underbrace{- x[n-1] \cdot (2^{n-1}-1)}_{\mbox{Invertierung}} + \sum_{i=0}^{n-2} x[i] \cdot 2^i$$
Und wenn wir dann zu Aufgabenteil e) übergehen, ergibt sich fast dieselbe Formel, nur dass auch noch das $-1$ in der Klammer wegfällt, weil beim 2-Komplement ja immer noch die Korrektur um $1$ mitgeführt werden muss.

von Dozent (10.1m Punkte)  
Bearbeitet von
...