Frage zu neg. Dualzahlen, Einer- bzw. Zweierkomplement

[mittelding]

Hallo!

Habe diesen Thread absichtlich im Programmierforum eröffnet, da die meisten Informatiker früher oder später sicherlich mal mit dem Thema zu tun hatten. Es geht um nix weltbewegendes, Informatik Oberstufe.
Vorrangig geht es mir um die Darstellung negativer Dualzahlen. Hier gibt es ja mehrere Möglichkeiten, habe zu allen (?) 3 jedoch Fragen.


Im wesentlichen haben wir 3 Systeme angesprochen. Erstens das Verwenden des Most significant Bit als Vorzeichen vor die dualzahl (0 = positiv, 1 = negativ), dann noch das Einer- und Zweierkomplement.

1.) Frage zur einfachsten Variante mit Vorzeichen: wir sollten die -18 (dez.) als Dualzahl darstellen. Ich dachte gut, die 18 in dual wäre ja 10010, negativ einfach eine 1 vorne hin und man erhält 110010. Auf dem Lösungsblatt steht nun aber 10010010, warum? Kann es sein, dass der Lehrer einfach grundsätzlich von 8 Bit ausgeht und beide Lösungen eigentlich identisch sind? Wäre 1000000000010010 dann genauso richtig, nur eben in 16 bit dargestellt?

2.) Frage zum Einerkomplement: Der Vorteil soll ja sein, dass man Einerkomplemente einfach addieren und subtrahieren kann, ohne auf das MSB aufpassen zu müssen. Dennoch gibt das MSB an, ob die Zahl pos. oder neg. ist?
Das würde bedeuten, die Mindestanzahl an Bits die ich brauche um die 4 negativ darzustellen, ist 4? (100 wäre negiert 001, aber es muss ja ne eins ganz vorne stehen weil negativ.. also 1001).

3.) Dann noch zum Zweierkomplement. Die Bildung ist klar, wie beim Einerkomplemnt, nur eben noch ne 1 draufaddiert. Aber wieder die selbe Frage wie oben: Wäre
1111111111111111 genau das selbe wie 1111, nämlich -1? Nur einmal als 16bit und einmal als 4 bit?


Ich verstehe noch nicht ganz, wie man da den Überblick behalten soll, wenn man Binärzahlen vorgesetzt bekommt und damit rechnen soll.
Die 11111111 könnte nämlich für die -1 stehen (im ZK), sie könnte aber genauso gut für die 255 stehen, wenn man sie als ganz normale binärzahl ansieht ohne diesen Komplementkram.
Das gleiche gilt für die Anzahl der Stellen.. bei Komplementen kann ein und diselbe Zahl durch beliebig viele Stellen ausgedrückt werden, im ganz normalen binär/Dualzahlsystm hat hingegen jede Zahl auch nur eine ganz bestimmte Ziffernfolge, da ist die 1111111 eben etwas anderes als die 1111.
Das lässt für mich eigentlich nur einen Schluss zu: um damit rechen zu können, muss in der Aufgabe genau angegeben sein, in welchem System man sich befindet?!


Fragen über Fragen, danke mal

[Gast]

Du hast gerade den Grund gefunden warum seit Jahren über 32 vs 64 bit diskutiert wird ;) bzw. warum es da noch immer soviel Schwierigkeiten gibt.
Natürlich muss man für eine Diskussion über (binäre) Zahlensysteme immer die anzahl der Stellen kennen, sonst hat das ganze keinen Sinn. Schon der Begriff "most significant bit" setzt ja voraus dass du weißt wie lang dein Wort ist, wie willst du denn sonst feststellen welches das MSB ist...

Zu Frage 1: Deine Lösung ist richtig wenn du einen 6-bit Wortbreite voraussetzt. Da üblicherweise heutzutage 1Byte=8Bit ist die Lösung deines Lehrers richtig. Gib mal in einen Binärrechner der neg. Zahlen kann deine Lösung ein, und du wirst mit 99,9% Wahrscheinlichkeit nicht -18 erhalten

[Coda]

Wäre 1111111111111111 genau das selbe wie 1111, nämlich -1? Nur einmal als 16bit und einmal als 4 bit?
Ja, das ist auf jeden Fall korrekt. Mit den anderen Systemen beschäftige ich mich nicht, weil sie praktisch nicht verwendet werden.

[Monger]

Vielleicht hilft es ja dem Verständnis:
das zweier Komplement entsteht dadurch, dass man einfach die eine - und zwar die obere - Zahlenhälfte für die negativen Zahlen reserviert. Und zwar genau gespiegelt, damit wenn man 1 zu 1111 hinzuaddiert, durch den Überlauf genau wieder auf Null kommt. Das +1 des Zweierinkrements kommt durch die Asymmetrie, weil Null noch zu den positiven Zahlen zählt.

Das Zweierkomplement funktioniert nur mit einer fixen Anzahl an Bitstellen, ist also direkt von der Rechnerarchitektur abhängig. Die muss eigentlich in der Aufgabe mit angegeben sein. Ansonsten könntest du ja auch mit 64 Bit rechnen! Mal sehen was der Lehrer dazu sagt :tongue:

[Gast]

Warum lernt man den Schmarn überhaupt? Wir machen das auch gerade. Bis jetzt habe ich noch nicht rausgefunden, was es mir beim Programmieren helfen soll Zahlensysteme manuell umzurechnen, Dualzahlen zu addieren etc. ? Nutz ich den Taschenrechner, geht schneller :D

[Die_Allianz]

naja wie willst du denn eine negative zahl speichern?

[Monger]

Nutz ich den Taschenrechner, geht schneller :D
Wenn man jetzt nicht gerade den TI-92+ nimmt, hat jeder Taschenrechner den ich kenne eine sehr begrenzte Anzahl an Stellen! ;)

Da passen oftmals nichtmal 32 Bit drauf.

[Tiamat]

Ja das ist schon richtig
Es muss stets angegeben werden, wieviel Bit die Wortbreite beträgt und ob es eine vorzeichenlose oder vorzeichenbehaftete Zahl ist. Bei vorzeichenlosen muss noch angegeben werden, wie diese codiert sind.
Wenn nicht alle Angabe vorhanden sind, nachfragen!

Im Falle von unsigned können bei n Bits 2 hoch n verschiedene positive Werte gespeichert werden, bei signed hingegen nur 2 hoch (n-1), da ein Bit als Vorzeichenbit verwendet wird.

Beim EK muss im Fall einer Addition die 1 noch drauf addiert werden, beim ZK geschieht dies schon bei der Komplementbildung und muss dann bei der Addition nicht mehr getan werden, was natürlich praktisch ist, wenn man einmal das Komplement gebildet hat, und dann beliebig oft mit der Zahl hin und her rechnet.
Das EK hat wiederum den Nachteil, dass die 0 nicht eindeutig ist, weil es zwei Nullen gibt. Das ZK hat diesen Nachteil nicht.

Warum man das ganze macht, ist weil man sich auf der Hardwareebene ein möglicherweise komplexes Subtrahierwerk sparen kann, es wird nur mit OR-Gattern bzw. NOR und Invertern bei der Addition gearbeitet.

[Gast]

Warum lernt man den Schmarn überhaupt? Wir machen das auch gerade. Bis jetzt habe ich noch nicht rausgefunden, was es mir beim Programmieren helfen soll Zahlensysteme manuell umzurechnen, Dualzahlen zu addieren etc. ? Nutz ich den Taschenrechner, geht schneller :D
Damit bei folgendem Code deine Alarmglocken losgehen:

char x = 'a';
x += 120;

Nix wissen über Binärzahlen und den ganzen "Schmarrn" -> nix wissen das obiges schiefgeht und warum...

[fezie]

Damit bei folgendem Code deine Alarmglocken losgehen:

char x = 'a';
x += 120;

Nix wissen über Binärzahlen und den ganzen "Schmarrn" -> nix wissen das obiges schiefgeht und warum...

Also für den Fall reichts aus zu wissen das char signed sein kann und somit ein Wert von -128 bis +127 gespeichert werden kann und es somit zum overflow kommt.
Durch den Thread hier les ich zum ersten mal was von Einer- und Zweierkomplement und geschadet hat es mir denk ich ned darüber bisher nix zu lesen.
Aber gut ich programmier au ned viel in C.

[Der_Donnervogel]

Ich denke auch es ist gut wenn man das mal gehört hat, selbst wenn man es praktisch nie braucht. Es schadet nicht zu verstehen, wie die Dinge im Untergrund ablaufen.

Um mit so etwas in Berührung zu kommen muss man schon sehr Low-Level programmieren. Eine gewisse Relevanz könnte das höchstens dann haben, wenn man wirklich auf Bit-Ebene operiert, also mit Bitmasken, Shifts usw.
int a = -2000000000;
int b = a << 1;
int c = b >> 1;
int d = c | (1 << 31);

Ergebnisse:
a = -2000000000
b = 294967296
c = 147483648
d = -2000000000

Aber wie oft macht man solche Sachen schon. ;)

[pest]

Aber wie oft macht man solche Sachen schon. ;)

kommt drauf an was du programmierst, mein geliebtes libavcodec ist voll davon

[Gast]

kommt drauf an was du programmierst, mein geliebtes libavcodec ist voll davon
Ganz genau, habe erst letztens einen Octree programmiert und als Node-ID Bitmasken (je 3bit Tripel) verwendet, und dann musst du nur mal auf die Idee kommen dir die ID zu Debug Zwecken binär auszugeben... :) Ist eigentlich das typische Anfängerbeispiel wenns um bitshifts, maskierung usw. geht: Gib einen int als Binärzahl aus.


Also für den Fall reichts aus zu wissen das char signed sein kann und somit ein Wert von -128 bis +127 gespeichert werden kann und es somit zum overflow kommt.
Jaja, aber das weißt du nur weil du eben über Binärzahlen Bescheid weißt - oder wie kommst du sonst ausgerechnet auf -128 / 127? ;)

[Der_Donnervogel]

kommt drauf an was du programmierstDas stimmt. Wie ich weiter oben schon angedeutet habe, gibt es Einsatzgebiete wo man auf dieser Low-Level-Ebene operiert. Ich könnte selbst das eine oder andere Beispiel nennen. Das sind aber eher spezielle Anwendungen, wo man explizit Bitoperationen einsetzen muss. Bei den allermeisten Programmen im PC-Bereich kommt man ohne so etwas aus.

[fezie]

Jaja, aber das weißt du nur weil du eben über Binärzahlen Bescheid weißt - oder wie kommst du sonst ausgerechnet auf -128 / 127? ;)

Um ehrlich zu sein hab ichs nachgeguckt auf dem Online Buch C von A bis Z ;)
Das 1. System was der TS beschreibt ist mir ja geläufig nur das 2. und 3. eben bis vor diesen Thread nicht.

[Gast]

Das stimmt. Wie ich weiter oben schon angedeutet habe, gibt es Einsatzgebiete wo man auf dieser Low-Level-Ebene operiert. Ich könnte selbst das eine oder andere Beispiel nennen. Das sind aber eher spezielle Anwendungen, wo man explizit Bitoperationen einsetzen muss. Bei den allermeisten Programmen im PC-Bereich kommt man ohne so etwas aus.
Ich würde nichtmal soweit gehen das als Low-Level zu bezeichnen. Brauchst dir nur mal aktuelle Netzwerkprotokolle anschauen (802.11n oder so), da wimmelts nur so von Bitoperationen.
Wenn du mit den "allermeisten Programmen im PC-Bereich" natürlich meinst dass das Programm aus einer GUI mit ein bisschen Logik dahinter (Wenn drücke Knopf A führe Aktion B aus, aber nur wenn Knopf C nicht aktiviert ist) besteht, hast du recht, da braucht man sowas nicht. Aber sowas zählt meiner Meinung nach nicht als "Programm" - das ist nichts weiter als ein automatisiertes Aufrufen vorgefertigter Funktionalität mit ein bisschen Benutzeroberfläche drumherum.

Für alles was darüber hinausgeht (also richtiges programmieren ;) ) sind Bitoperationen weder besonders speziell noch Low Level sondern einfach Grundwissen das man haben sollte.

[Monger]

Ich würde nichtmal soweit gehen das als Low-Level zu bezeichnen. Brauchst dir nur mal aktuelle Netzwerkprotokolle anschauen (802.11n oder so), da wimmelts nur so von Bitoperationen.

Du musst gar nicht so tief runtergehen. Das fängt schon bei so simplen Operationen wie HashCode errechnen an, oder das Ver-ODERn und maskieren von Bit Flags. Das macht man z.B. in der .NET Welt auch mit Enums ganz gerne. Wenn die nicht sauber gesetzt sind, gibt das ganz hässliche Fehler - die sich kaum debuggen lassen, wenn du keine Ahnung von Bit Operationen hast.

Bit Gewurschtel ist in den Hochsprachen seltener geworden, kommt aber immer noch regelmäßig vor.

[Der_Donnervogel]

Es kommt auf jeden Fall noch vor, wobei es stark davon abhängt was man macht und womit. Dabei möchte ich mich gar nicht erst auf die Diskussion einlassen was ein "richtiges" Programm ist. ;)

Ich selbst haben mit Bitoperationen eigentlich nur einmal viel arbeiten müssen, als ich mal was für ein embedded Gerät gemacht habe. Das war aber "richtiges" programmieren. ;) Mit falsch gesetzten Bits im falschen Register hätte man da locker die Hardware grillen können. ;D

Wie oft man Bitoperationen einsetzt ist aber schon unterschiedlich. Ich brauche die wirklich nur sehr selten. Das mag durchaus auch an der Sprache liegen, da ich hauptsächlich mit Java arbeite.

Du musst gar nicht so tief runtergehen. Das fängt schon bei so simplen Operationen wie HashCode errechnen an, oder das Ver-ODERn und maskieren von Bit Flags. Das macht man z.B. in der .NET Welt auch mit Enums ganz gerne.Wobei so viel ich weiß (mache allerdings fast nichts mit .Net), z.B. die Enums (oder sind es Konstanten?) so gemacht sind, dass man sie nicht zwingend verodern muss, sondern dass auch eine Addition geht, wie zB:
MsgBox("Hallo", MsgBoxStyle.Information + MsgBoxStyle.OkOnly)
' ist das selbe wie
MsgBox("Hallo", MsgBoxStyle.Information Or MsgBoxStyle.OkOnly)
Die Konstanten wurden so gewählt, dass das funktioniert. So lange man nur mit Zahlen die 2^n entsprechen arbeitet ist ja (a | b) und (a + b) äquivalent, solange a != b gilt. Fast alle Konstanten sind Zweierpotenzen. Die wenigen die dem nicht entsprechen wurden so gewählt, dass es keine Überschneidungen gibt.

Je nachdem ob man das also mit "Addition" oder "Oder" handhabt, fallen da viele (offensichtlichen) Bitoperationen weg.

Wie es sich mit der HashCode Funktion verhält weiß ich nicht. Ich habe die in .Net noch nie benutzen müssen. Ich weiß deshalb ehrlich gesagt auch nicht wozu man dort unbedingt Bitoperationen braucht. In Java verwendet man die für Vergleiche und da braucht man keine Bitoperationen und zum Erstellen von HashCodes ist in Java AFAIK kein bestimmter Hashalgorithmus vorgeschrieben, ist das bei .Net anders?

[pest]

es gab zeiten, da wussten leute noch, was ne hash-funktion ist, und wie man die schreibt :wink:

ich nehm das zeug nichmal wenn es angeboten wird
wer weiß was da alles passiert, man weiß ja nie :freak:

[Monger]

Wobei so viel ich weiß (mache allerdings fast nichts mit .Net), z.B. die Enums (oder sind es Konstanten?) so gemacht sind, dass man sie nicht zwingend verodern muss, sondern dass auch eine Addition geht, wie zB:
MsgBox("Hallo", MsgBoxStyle.Information + MsgBoxStyle.OkOnly)
' ist das selbe wie
MsgBox("Hallo", MsgBoxStyle.Information Or MsgBoxStyle.OkOnly)
Die Konstanten wurden so gewählt, dass das funktioniert.

Im .NET Framework hat Microsoft das natürlich so gemacht, dass sowas passt. Wenn man sich selber ein Enum festlegt, und mehrere Flags gleichzeitig erlauben will, sollte man aber zumindest mal verstehen, warum man Zahlen im 2^n Raum dafür festlegen sollte! ;)

Und wenn man diese Bitmuster wieder auseinander zwiebelt, sollte man wissen wie man eine solche Zahl maskiert.
Das ist zugegebenermaßen kein besonders häufiges Szenario, aber ich wollte ja auch nur demonstrieren, dass Bit Operationen selbst in Hochsprachen noch ihre Berechtigung haben.


Wie es sich mit der HashCode Funktion verhält weiß ich nicht. Ich habe die in .Net noch nie benutzen müssen.

Genauso wie in Java sollte auch in .NET der HashCode immer zusammen mit Equals überschrieben werden, um z.B. als Schlüssel für hashbasierte Strukturen zu dienen. Das kommt sehr regelmäßig vor.


In Java verwendet man die für Vergleiche und da braucht man keine Bitoperationen und zum Erstellen von HashCodes ist in Java AFAIK kein bestimmter Hashalgorithmus vorgeschrieben, ist das bei .Net anders?
Nein, die Implementierung ist natürlich nicht vorgeschrieben. Aber der Sinn des HashCodes ist ja nunmal, dass er für beliebige Objekte möglichst gleichmäßig zufällig verteilt sein sollte. Das ist nicht ganz einfach - vorallem weil man auch Effekte wie z.B. einen Zahlenüberlauf vermeiden will. Einfach die HashCodes von unterlagerten Elementen zu addieren, ist deshalb keine gute Idee. Da bietet sich z.B. ein XOR an, weil eine exklusive Veroderung von zwei chaotischen Bitmustern danach immer noch genauso chaotisch ist.

Mal ein Beispiel aus VB.NET:

Public Class Dummy
Private Vorname As String
Private Nachname As String

Public Overrides Function GetHashCode() As Integer
Return Vorname.GetHashCode XOR Nachname.GetHashCode
End Function
End Class

[Der_Donnervogel]

es gab zeiten, da wussten leute noch, was ne hash-funktion ist, und wie man die schreibt :wink:Ja, früher war alles besser. ;)
ich nehm das zeug nichmal wenn es angeboten wird
wer weiß was da alles passiert, man weiß ja nie :freak:Ich nehme, sofern es keinen triftigen Grund gibt der dagegen spricht, immer die Funktionen der Sprache, bzw. deren Bibliotheken. Es ist nicht effizient grundlegende Dinge selbst zu implementieren, wenn sie bereits existieren. Falls es wichtig ist, kann man in den allermeisten Fällen nachschauen wie das implementiert ist, bzw. zumindest in Erfahrung bringen welche Algorithmen und Datenstrukturen für die Implementierung verwendet wurden. Bei Java basiert beispielsweise der Default-Hash AFAIK auf der Speicheradresse des Objekts und damit kann ich gut leben.Wenn man sich selber ein Enum festlegt, und mehrere Flags gleichzeitig erlauben will, sollte man aber zumindest mal verstehen, warum man Zahlen im 2^n Raum dafür festlegen sollte! ;)Das stimmt. Es ist generell wichtig, dass man als Programmierer versteht was man tut. Diese ganzen Grundlagen sollte man können, auch wenn man sie selbst selten oder nie selbst benutzen muss. Das ist zugegebenermaßen kein besonders häufiges Szenario, aber ich wollte ja auch nur demonstrieren, dass Bit Operationen selbst in Hochsprachen noch ihre Berechtigung haben.Das haben sie durchaus. Es kommt natürlich auch auf die Sprache drauf an. Ein Grund warum ich Bitoperationen sehr selten verwende ist sicher auch, dass ich viel mit Java arbeite und das Bitoperationen nur schlecht unterstützt. Man kann dort z.B. nur mit int-Variablen Bitoperationen durchführen und da auch die nicht als Boolean-Wert interpretiert werden können muss man z.B. in einer Bedingung immer "if ((var & flag) != 0)" schreiben, falls man Flags nutzen will. Enums wiederum sind Klassen und keine Typen. Man kann die also nicht einfach mit | und & bearbeiten. Unterm Strich kann man zwar damit arbeiten, es ist aber etwas umständlich.Genauso wie in Java sollte auch in .NET der HashCode immer zusammen mit Equals überschrieben werden, um z.B. als Schlüssel für hashbasierte Strukturen zu dienen. Das kommt sehr regelmäßig vor.Das stimmt, es kommt vor. Meistens war es dann aber so, dass nur ein Attribut (z.B. eine id) des Objekts entscheidend für den Vergleich war. In diesen Fällen habe ich dann oft eine Map und als Schlüssel eine Referenz auf das entsprechende Attribut des Objekts verwendet und equals erst gar nicht überschrieben. Dass wirklich mehrere Attribute eines Objekts wichtig waren, hatte ich nur sehr selten.Nein, die Implementierung ist natürlich nicht vorgeschrieben. Aber der Sinn des HashCodes ist ja nunmal, dass er für beliebige Objekte möglichst gleichmäßig zufällig verteilt sein sollte. Das ist nicht ganz einfach - vorallem weil man auch Effekte wie z.B. einen Zahlenüberlauf vermeiden will. Einfach die HashCodes von unterlagerten Elementen zu addieren, ist deshalb keine gute Idee. Da bietet sich z.B. ein XOR an, weil eine exklusive Veroderung von zwei chaotischen Bitmustern danach immer noch genauso chaotisch ist.An die Variante hat XOR habe ich bei Hashes nicht gedacht. Ich habe in den seltenen Fällen wo ich einen Hash aus mehreren Attributen erzeugen musste, nicht die einzelnen Hashes kombiniert, sondern einen neuen Hash aus den Daten der Attribute abgeleitet. Allerdings ist die Version mit XOR sicher performanter.

[Coda]

Also für den Fall reichts aus zu wissen das char signed sein kann und somit ein Wert von -128 bis +127 gespeichert werden kann und es somit zum overflow kommt.
Na und? Das ändert nix an der Interpretation des resultierenden Zeichens.

Addition bzw. Subtraktion für signed und unsigned unterscheidet ein Prozessor erst gar nicht. Das ist ja der Sinn vom Zweierkomplement.

Overflows lösen (leider) keine Exception aus bei gängigen Programmiersprachen, deshalb ist es schnurzegal ob char signed oder unsigned ist in diesem Zusammenhang.

[Der_Donnervogel]

Overflows lösen (leider) keine Exception aus bei gängigen ProgrammiersprachenHabe zwar schon länger nichts mehr auf dem Niveau gemacht, aber ist es nicht so, dass die CPU bei einem Overflow (im Gegensatz z.B zur Division durch 0) keinen Interrupt auslöst und nur ein Overflow-Flag setzt? d.h. um da eine Exception auszulösen müsste nach jeder Rechenoperation die einen Overflow auslösen kann durch die Sprache ein Check auf das Flag eingefügt werden. Ich vermute mal deshalb wurde das überall weg gelassen (würde vermutlich ordentlich Performance kosten), oder gibts da einen anderen Grund?