Negative Zahlen im Binärsystem
Bisher haben wir über positive ganze Zahlen und deren Darstellung in unseren Computern gesprochen. Manchmal müssen wir jedoch auch mit negativen Zahlen arbeiten. Wie werden also negative Zahlen in Computern abgespeichert?
Wir haben gesehen, dass die Zahl 1 als
0001 im Binärsystem dargestellt wird, die Zahl 6 als 0110 usw. Die Zahl 0 wird als lauter Nullen 0000 repräsentiert. Eine einfache Möglichkeit, negative Zahlen darzustellen, besteht darin, ein „spezielles“ Bit vorzusehen, das anzeigt, ob eine Zahl negativ ist. Dieses Bit ist 1, wenn die Zahl negativ ist, und 0, wenn sie positiv ist. Genau so arbeiten die meisten Rechner: Das ganz linke Bit dient als Vorzeichenbit; es ist 1 bei negativen Zahlen und 0 bei positiven.Allerdings steckt mehr dahinter, als bloß das linke Bit auf 1 zu setzen. Im Dezimalsystem gleichen sich positive und negative Zahlen gegenseitig aus: Addiert man 6 und -6, erhält man 0. Diese Eigenschaft soll auch im Binärsystem erhalten bleiben. Addiert man 6 und -6 in binärer Form, soll ebenfalls 0 resultieren.
Stellen wir uns vor, wir hätten 4 Bits zur Darstellung einer Zahl und zusätzlich 1 Bit für das Vorzeichen, also insgesamt 5 Bits. Dann würde 6 als
00110 dargestellt, während 0 als 00000 erscheint. Die Binärdarstellung von -6 muss dann das genaue Gegenstück zu 6 sein, damit die Summe 0 ergibt. Vorweggenommen: Die Darstellung von -6 lautet 11010. Addiert man 00110 und 11010, erhält man 00000.Um eine binäre Zahl von positiv zu negativ (oder andersherum) umzuwandeln, gibt es einen simplen Trick: Alle Bits umdrehen (d. h. alle 0 zu 1 und alle 1 zu 0) und anschließend 1 addieren.
x = 6 # 00110
x = ~x + 1 # Alle Bits umdrehen und 1 addieren => -6
x = ~x + 1 # Alle Bits umdrehen und 1 addieren => 6
z = 0 # 00000
z = ~z + 1 # Bits umdrehen und +1 => 0
z = ~z + 1 # Bits umdrehen und +1 => 0
z = ~z # -1 (alle 1s in der Binärdarstellung)
z = ~z # 0 (alle 0s in der Binärdarstellung)Beachte, dass das Addieren im Binärsystem ähnlich funktioniert wie im Dezimalsystem: Man addiert von der am wenigsten signifikanten Stelle zur höchsten und behält dabei einen eventuellen Übertrag im Blick.
Je nach Programmiersprache und Implementierung werden Zahlen unterschiedlich gespeichert. Sprachen wie C++ und Java haben unterschiedliche Datentypen für verschiedene Zahlenbereiche. Der Typ
int speichert ganze Zahlen beispielsweise auf 32 Bits: 31 Bits für den Zahlenwert und 1 Bit für das Vorzeichen ⇒ Wertebereich von -2,147,483,648 () bis 2,147,483,647 (). Man beachte, dass die positiven Zahlen um 1 weniger umfassen. Das liegt daran, dass die positiven Zahlen mit einer 0 beginnen und auch 0 (alle Bits auf 0) bereits dazu zählt.Herausforderung
Im magischen Land der Siebenen ist alles darauf ausgerichtet, etwas mit der Zahl 7 zu tun zu haben. Dort haben die Informatiker ein System entwickelt, in dem Binärzahlen (positive und negative) jeweils 77 Bits umfassen.
Gegeben ist ein Bit-String
b. Deine Aufgabe ist es, den negativen Wert dieser Zahl zu berechnen und ihn in 77 Bits darzustellen.Eingabe
Die Eingabe enthält eine einzelne Zeile mit dem Bit-String
b (1 ≤ |b| ≤ 77). Dieser kann sowohl eine positive als auch eine negative Zahl repräsentieren.Ausgabe
Die Ausgabe soll eine einzige Zeile enthalten, die
-b in 77 Bits darstellt.Beispiele
Eingabe | Ausgabe |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB