Dezimalzahl, binäre Darstellun < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:23 Do 27.03.2008 | | Autor: | Pein |
| Aufgabe | Für eine ganze Dezimalzahl x bezeichne z(x) die binäre Darstellung von x mit n Stellen und Zweierkomplement.
Mit z(x) + z(y) sei die normale Addition von Binärzahlen (ohne spezielle behandlung von Komplementen) bezeichnet.
Gilt die Beziehung z(x) + z(y) = z(x+y)?
Bweisen Sie entweder die Gültigkeit oder geben Sie ein Gegenbeispiel an. Überlaufprobleme dürfen Sie hierbei ignorieren. |
Hi
Also ich würde sagen, die Formel gilt.
Z. B. haben wir die Dezimalzahl 10 und die Dezimalzahl 7
[mm] (10)_{10} [/mm] = ( 10 10 [mm] )_2
[/mm]
[mm] (5)_{10} [/mm] = ( 01 01 [mm] )_2
[/mm]
10 + 5 = 15
[mm] (15)_{10} [/mm] = ( 11 11 [mm] )_2 [/mm] = ( 10 10 [mm] )_2 [/mm] + ( 01 01 [mm] )_2
[/mm]
Das ist so meine Überlegung, stimmt die Überlegung?
Ganz frech gefragt, wie ist der Beweis?
Grüße
Pein
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:01 So 30.03.2008 | | Autor: | bazzzty |
Hallo Pein,
ich denke, daß man als gegeben annehmen kann, daß das für positive Zahlen x,y funktioniert. Die Addition zweier Zahlen muß ja von der Darstellung unabhängig sein.
Die Frage zielt ziemlich sicher auf folgendes ab:
Wenn ich x und y addiere und mindestens eins davon negativ ist, funktioniert das trotzdem mit der "normalen" Addition im Binären wenn also 7=0111B und -1=1111B ist, dann stimmt 0111B+1111B=(1)0110B=6. Ist das immer so?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:13 Mo 31.03.2008 | | Autor: | Pein |
Hallo
> ich denke, daß man als gegeben annehmen kann, daß das für
> positive Zahlen x,y funktioniert. Die Addition zweier
> Zahlen muß ja von der Darstellung unabhängig sein.
> Die Frage zielt ziemlich sicher auf folgendes ab:
> Wenn ich x und y addiere und mindestens eins davon negativ
> ist, funktioniert das trotzdem mit der "normalen" Addition
> im Binären wenn also 7=0111B und -1=1111B ist, dann stimmt
> 0111B+1111B=(1)0110B=6. Ist das immer so?
Wenn du schon so fragst. Nein? aber warum geht das nicht immer?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:40 Mo 31.03.2008 | | Autor: | bazzzty |
> > ich denke, daß man als gegeben annehmen kann, daß das für
> > positive Zahlen x,y funktioniert. Die Addition zweier
> > Zahlen muß ja von der Darstellung unabhängig sein.
> > Die Frage zielt ziemlich sicher auf folgendes ab:
> > Wenn ich x und y addiere und mindestens eins davon negativ
> > ist, funktioniert das trotzdem mit der "normalen" Addition
> > im Binären wenn also 7=0111B und -1=1111B ist, dann stimmt
> > 0111B+1111B=(1)0110B=6. Ist das immer so?
>
> Wenn du schon so fragst. Nein? aber warum geht das nicht
> immer?
Gibt es denn einen Fall, in dem das fehlschlägt, obwohl sich x und y und x+y eindeutig in Komplementschreibweise kodieren lassen, also für n-Stellige Binärzahlen zwischen 2^(n-1) und -2^(n-1), die man nicht einfach wie zwei ganz normale Binärzahlen addieren kann (und einen Überlauf ignoriert), so daß das Ergebnis wieder stimmt?
3+4=0011B+0100B=0111B=7
3-4=0011B+1100B=1111B=-1
-3+4=1101B+0100B=(1)0001=1
-3-4=1101B+1100B=(1)1001B=-7
Noch ein Tipp: Warum nimmt man denn nicht das ganz normale Komplement für die Darstellung negativer Zahlen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:21 Mo 31.03.2008 | | Autor: | Pein |
> Gibt es denn einen Fall, in dem das fehlschlägt, obwohl
Mir ist gerade erst aufgefallen, dass du das immer addierst und nicht subtrahierst. Dann würde ich sagen, die Formel gilt wieder
> sich x und y und x+y eindeutig in Komplementschreibweise
> kodieren lassen, also für n-Stellige Binärzahlen zwischen
> 2^(n-1) und -2^(n-1), die man nicht einfach wie zwei ganz
> normale Binärzahlen addieren kann (und einen Überlauf
> ignoriert), so daß das Ergebnis wieder stimmt?
>
> 3+4=0011B+0100B=0111B=7
> 3-4=0011B+1100B=1111B=-1
> -3+4=1101B+0100B=(1)0001=1
> -3-4=1101B+1100B=(1)1001B=-7
>
> Noch ein Tipp: Warum nimmt man denn nicht das ganz normale
> Komplement für die Darstellung negativer Zahlen?
Was ist denn für dich das ganz normale Komplement? Ich kenne nur das, wo die 1 für Minus und die Null für Plus vorne steht. Und wir hatten es auch nur so, dass wir dann -3-4 = 1101B - 1100B = 0001B = 1 gerechnet haben. Deswegen meine Vermutung, dass es nicht galt. Und am Anfang dachte ich, es galt. Und jetzt glaube ich es wieder
Kannst du einen noch deutlicheren Hinweis geben?
|
|
|
| |
|
Hallo Pein!
> > Gibt es denn einen Fall, in dem das fehlschlägt, obwohl
>
> Mir ist gerade erst aufgefallen, dass du das immer addierst
> und nicht subtrahierst. Dann würde ich sagen, die Formel
> gilt wieder
Aber du addierst ja teilweise negative Zahlen, was wieder dem Subtrahieren entspricht...
> > sich x und y und x+y eindeutig in Komplementschreibweise
> > kodieren lassen, also für n-Stellige Binärzahlen zwischen
> > 2^(n-1) und -2^(n-1), die man nicht einfach wie zwei ganz
Das müsste doch aber glaube ich, zwischen [mm] 2^{n-1}-1 [/mm] und [mm] -2^{n-1} [/mm] sein, denn die positiven sind doch immer eins weniger. 
> > normale Binärzahlen addieren kann (und einen Überlauf
> > ignoriert), so daß das Ergebnis wieder stimmt?
> >
> > 3+4=0011B+0100B=0111B=7
> > 3-4=0011B+1100B=1111B=-1
> > -3+4=1101B+0100B=(1)0001=1
> > -3-4=1101B+1100B=(1)1001B=-7
> >
> > Noch ein Tipp: Warum nimmt man denn nicht das ganz normale
> > Komplement für die Darstellung negativer Zahlen?
>
> Was ist denn für dich das ganz normale Komplement? Ich
Das "ganz normale Komplement" ist wohl das Einerkomplement, im Gegensatz zum Zweierkomplement, das du hier benutzen sollst. Wenn du dir obige Beispiele mal ganz genau anschaust, stellst du fest, dass das nicht nur die 0 für + und die 1 für - ist, sondern erstens sind alle Bits invertiert (wenn wir eine negative Zahl haben) (das wäre dann das Einerkomplement), und zweitens wird noch eins addiert bzw. subtrahiert - damit haben wir dann das Zweierkomplement. Vielleicht schaust du dir die Definitionen dazu, oder zumindest zum Zweierkomplement, nochmal ganz genau an. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:04 Di 01.04.2008 | | Autor: | bazzzty |
> Das müsste doch aber glaube ich, zwischen [mm]2^{n-1}-1[/mm] und
> [mm]-2^{n-1}[/mm] sein, denn die positiven sind doch immer eins
> weniger.
Aber natürlich. Ich hätte schwören können, daß ich die Eins mit hingeschrieben habe.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:20 Di 01.04.2008 | | Autor: | bazzzty |
> > Gibt es denn einen Fall, in dem das fehlschlägt, obwohl
>
> Mir ist gerade erst aufgefallen, dass du das immer addierst
> und nicht subtrahierst. Dann würde ich sagen, die Formel
> gilt wieder
Nun, ich kann Dir glaube ich verraten: Sie gilt. Wenn man Binärzahlen im Zweierkomplement kodiert, dann kann man "einfach addieren und Überträge ignorieren", und kann auf eine Sonderbehandlung verzichten. Warum das so ist, war wohl die Frage, mit der Du Dich beschäftigt hast.
Der Beweis ist kurz und hat was mit der Restgruppe [mm]\IZ/2^n\IZ[/mm] zu tun. Davor solltest Du Dir aber erstmal wirklich klarmachen, was das Zweierkomplement vom Einerkomplement unterscheidet, und mal an ein paar Beispielen durchprobieren (so wie ich in meinem Beispiel). Vielleicht kommst Du selbst auf eine Beweisidee.
> Was ist denn für dich das ganz normale Komplement? Ich
> kenne nur das, wo die 1 für Minus und die Null für Plus
> vorne steht. Und wir hatten es auch nur so, dass wir dann
> -3-4 = 1101B - 1100B = 0001B = 1 gerechnet haben.
Du solltest entweder Deine Unterlagen oder andere Quellen (Wikipedia?) nochmal genauer durchsehen.
Wenn -3=1101B (3=0011B), dann ist weder nur eine Eins als Vorzeichen vorne geändert worden , noch wurde nur invertiert (Einerkomplement). Negative Zahlen werden gebildet, in dem man erstens alle Bit invertiert (1100B) und dann eine 1 dazuaddiert (1101B) wie oben. Dann kann man addieren und subtrahieren, ohne auf Vorzeichen zu achten.
Die Rechnung oben muß allerdings so aussehen:
[mm](-3)-(-4) = 1101B - 1100B = 0001B = 1[/mm] und dann stimmt sie auch, sowohl was die Komplementbildung, als auch was das Ergebnis angeht.
> Kannst du einen noch deutlicheren Hinweis geben?
Lies Dir die Definition von Zweierkomplement durch. Rechne damit (wie in meinen Beispielen). Das Ergebnis sollte stimmen, solange alle Zahlen x,y,x+y den Wertebereich nicht verlassen.
Danach kannst Du darüber nachdenken, warum das so ist. Die Restklassengruppe, die dafür relevant ist, habe ich Dir schon genannt, aber ich helfe dann auch gerne weiter.
|
|
|
|
