Dualsystem

Grundidee und Darstellung

Das Dualsystem, auch Zweiersystem oder Binärsystem genannt, ist ein Stellenwertsystem zur Basis 2. Es verwendet nur die beiden Ziffern 0 und 1. Wegen dieser einfachen Darstellung ist es neben dem Dezimalsystem besonders wichtig und bildet eine Grundlage der Digitaltechnik.

Wie im Dezimalsystem hängt der Wert einer Ziffer von ihrer Position ab. Im Dualsystem entsprechen die Stellen jedoch Zweierpotenzen. Von rechts nach links haben die Stellen vor dem Komma die Werte 2⁰, 2¹, 2², 2³ usw.; nach dem Komma folgen 2⁻¹, 2⁻² usw. Für eine abbrechende Darstellung gilt

Z = Σ von i = −n bis m über zᵢ · 2ⁱ, wobei zᵢ ∈ {0,1}.

Die höchstwertige Stelle steht links. Negative Zahlen erhalten wie im Dezimalsystem ein vorangestelltes Minuszeichen. Zur eindeutigen Kennzeichnung der Basis schreibt man beispielsweise [1101]₂ oder 1101₂. Weitere Schreibweisen sind 1101_(2), 0b1101 oder %1101. Der Buchstabe B kann ebenfalls nachgestellt werden, ist aber wegen möglicher Verwechslungen mit Hexadezimalzahlen nicht empfehlenswert.

Ein Beispiel: [1101]₂ bedeutet 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 8 + 4 + 0 + 1 = [13]₁₀. Die Ziffernfolge hat also je nach Basis einen anderen Wert.

Statt 0 und 1 können technische Zustände verwendet werden, etwa Low und High. Bei positiver Logik steht Low meist für 0 und High für 1; bei negativer Logik ist die Zuordnung umgekehrt. Binär codierte Wahrheitswerte werden häufig als falsch = 0 und wahr = 1 dargestellt.

Umrechnen zwischen Zahlensystemen

Eine Dualzahl wird ins Dezimalsystem umgerechnet, indem jede Ziffer mit der zugehörigen Zweierpotenz multipliziert und alles addiert wird:

1010₂ = 1·2³ + 0·2² + 1·2¹ + 0·2⁰ = 8 + 2 = 10₁₀.

Ebenso gilt 101001₂ = 1 + 8 + 32 = 41₁₀. Bei einer positiven ganzen Dualzahl zeigt die letzte Ziffer sofort die Geradheit: Endet sie auf 1, ist die Zahl ungerade; endet sie auf 0, ist sie gerade.

Für die Umrechnung einer Dezimalzahl ins Dualsystem gibt es mehrere Verfahren. Bei der Divisions- oder Modulo-Methode wird wiederholt durch 2 geteilt. Die Reste werden anschließend von unten nach oben gelesen. Für 41 entstehen nacheinander die Reste 1, 0, 0, 1, 0, 1; rückwärts gelesen ergibt das 101001₂.

Bei der Subtraktionsmethode wird jeweils die größtmögliche passende Zweierpotenz abgezogen. Passt eine Zweierpotenz, erhält die betreffende Stelle eine 1; ist sie größer als der verbleibende Rest, erhält die Stelle eine 0. Für 41 gilt 41 − 2⁵ = 9, 2⁴ passt nicht, 9 − 2³ = 1, 2² und 2¹ passen nicht und 1 − 2⁰ = 0. Daraus folgt ebenfalls 101001₂.

Dualzahlen können lang und schwer zu überblicken sein. Deshalb wird häufig das Hexadezimalsystem zur Basis 16 benutzt. Da 16 = 2⁴ ist, lassen sich jeweils vier Dualstellen direkt durch eine Hexadezimalstelle ersetzen. Die Hexadezimalziffern 0 bis 15 werden als 0–9 und A–F geschrieben. So entsprechen beispielsweise 1110₂ und E₁₆ einander. Durch die Gruppierung wird eine Darstellung auf ein Viertel ihrer Dualstellen verkürzt.

Rechnen mit Dualzahlen

Addition, Subtraktion, Multiplikation und Division funktionieren grundsätzlich wie im Dezimalsystem, sind wegen der Ziffern 0 und 1 aber einfacher.

Bei der Addition gelten 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 und 1 + 1 = 0 mit Übertrag 1. Man rechnet schriftlich von rechts nach links. Ein Übertrag wird bei der nächsten Stelle mitgerechnet. Beim Beispiel 10011010₂ + 00110110₂ entsteht 11010000₂, also 154 + 54 = 208.

Bei der Subtraktion gelten 0 − 0 = 0, 1 − 0 = 1, 1 − 1 = 0 und 0 − 1 = 1 mit Entleihen beziehungsweise Übertrag 1. Aus 0 − 1 wird dabei gedanklich 10₂ − 1₂. Ist der Minuend kleiner als der Subtrahend, kann die Subtraktion durch Addition des Zweierkomplements ausgeführt werden. So lässt sich 118 − 153 als Addition von 118 und der Zweierkomplementdarstellung von −153 berechnen; das Ergebnis ist −35.

Bei der Multiplikation gelten nur die Produkte 0·0 = 0, 0·1 = 0, 1·0 = 0 und 1·1 = 1. Für jede 1 im zweiten Faktor wird der erste Faktor passend verschoben notiert; für jede 0 entsteht eine Nullzeile. Danach werden die Teilprodukte addiert. Das Beispiel 1100₂ · 1101₂ ergibt 10011100₂, also 12·13 = 156. Eine Multiplikation einer positiven Dualzahl mit 10₂ entspricht dem Anhängen einer Null: 1101₂·10₂ = 11010₂. Für zwei Zahlen im Zweierkomplement wird der Booth-Algorithmus verwendet.

Die schriftliche Division folgt ebenfalls dem bekannten Verfahren. Beispielsweise ist 1000010₂ : 11₂ = 010110₂ mit Rest 0, entsprechend 66 : 3 = 22. Bei der Division einer positiven Dualzahl durch 10₂ wird die letzte Ziffer gestrichen; sie bildet den Rest. Daher ist 1101₂ : 10₂ = 110₂ mit Rest 1. Entsprechend liefert der Modulo-Ausdruck mit 10₂ genau die letzte Ziffer: 1101₂ mod 10₂ = 1 und 1100₂ mod 10₂ = 0. Division durch 0 ist nicht definiert.

Speicherung und Stellenzahl

In der elektronischen Datenverarbeitung können 0 und 1 durch zwei gut unterscheidbare elektrische Zustände dargestellt werden, etwa Strom an und Strom aus oder Spannung und Masse. Damit lassen sich einfache und fehlerresistente Schaltungen bauen. Die Algorithmen der Dualarithmetik können effizient durch logische Schaltungen ausgeführt werden.

Dualzahlen dienen unter anderem zur Darstellung ganzer Zahlen und von Festkommazahlen. Negative Zahlen werden meist im Zweierkomplement gespeichert. Seltener wird das Einerkomplement verwendet; dessen Nachteil sind zwei Darstellungen der Null, eine positive und eine negative. Eine weitere Möglichkeit ist der Exzesscode, der auf einer Verschiebung des Wertebereichs beruht. Rationale oder reelle Zahlen mit nicht abbrechender Dualdarstellung werden näherungsweise als Gleitkommazahlen gespeichert. Dabei wird die normalisierte Zahl in Mantisse und Exponent zerlegt, die beide binär gespeichert werden.

Mit n Stellen lassen sich ohne Vorzeichen höchstens 2ⁿ − 1 darstellen. Vier Stellen reichen daher von 0 bis 15. Mit zehn Fingern kann man bei binärer Verwendung bis 2¹⁰ − 1 = 1023 zählen. Werden n Bit für eine Zahl im Zweierkomplement verwendet, reicht der Bereich von −2^(n−1) bis 2^(n−1) − 1. Insgesamt gibt es weiterhin 2ⁿ verschiedene Werte.

Für eine positive Dezimalzahl n beträgt die benötigte Anzahl an Dualstellen ⌊lb n⌋ + 1. Dabei ist lb der Logarithmus zur Basis 2 und ⌊·⌋ die Abrundungsfunktion. Als Obergrenze kann außerdem die Anzahl der Dezimalstellen mit 3,322 multipliziert und das Ergebnis aufgerundet werden, weil lb(10) ≈ 3,322.

Teilbarkeit und Zahlenkarten

An den Endstellen einer Dualzahl lassen sich Teilbarkeitseigenschaften erkennen. Eine Zahl ist so oft ohne Rest durch 2 teilbar, wie sie am Ende Nullen besitzt. Endet sie auf i Nullen, ist sie durch 2ⁱ teilbar. Beispielsweise endet 100101000₂ = 296₁₀ auf drei Nullen; daher gilt 296 = 2³·37.

Für die Teilbarkeit durch 3 wird die Anzahl der Einsen auf geraden Positionen mit der Anzahl der Einsen auf ungeraden Positionen verglichen. Eine Dualzahl ist genau dann durch 3 teilbar, wenn der Betrag der Differenz dieser beiden Anzahlen durch 3 teilbar ist. Diese Differenz heißt alternierende Quersumme. Beim Beispiel 744628179621₁₀ = 1010110101011111010011000101001010100101₂ stehen 9 Einsen auf geraden und 12 auf ungeraden Positionen. Der Betrag der Differenz ist |9 − 12| = 3 und 3 mod 3 = 0; tatsächlich gilt 744628179621 : 3 = 248209393207.

Ein Zahlentrick veranschaulicht die eindeutige Darstellung natürlicher Zahlen als Summen von Zweierpotenzen. Eine Person merkt sich eine Zahl von 1 bis 63 und gibt von sechs Zahlenkarten nur diejenigen zurück, auf denen diese Zahl steht. Die Anfangszahlen der zurückgegebenen Karten werden addiert; ihre Summe ist die gedachte Zahl. Die Zahl 23 liegt beispielsweise auf den Karten mit den Anfangszahlen 16, 4, 2 und 1, denn 23 = 16 + 4 + 2 + 1 = 10111₂.

Entwicklung und technische Bedeutung

Frühe Systeme mit zwei Zeichen sind aus verschiedenen Kulturen bekannt. Pingala beschrieb im 3. Jahrhundert v. Chr. ein solches Zahlensystem, allerdings ohne Null. Shao Yong ordnete im 11. Jahrhundert die 64 Hexagramme des I Ching systematisch an; es gibt jedoch keinen Hinweis darauf, dass er damit im Dualsystem rechnete oder das Stellenwertprinzip erkannt hatte. Polynesier nutzten schon vor der europäischen Entwicklung binäre Zusammenfassungen von Zahlen zur Vereinfachung von Rechnungen.

In Europa behandelten unter anderem Thomas Harriot, Blaise Pascal und Juan Caramuel y Lobkowitz Stellenwertsysteme mit anderen Basen. Caramuels Mathesis Biceps vetus et nova von 1670 gilt wahrscheinlich als erste europäische Veröffentlichung des Dualsystems. Gottfried Wilhelm Leibniz entwickelte die Dyadik Ende des 17. Jahrhunderts und dokumentierte sie vollständig in Explication de l’Arithmétique Binaire von 1703, veröffentlicht 1705. Seine Deutung der chinesischen Tri- und Hexagramme als vergessenes archaisches Binärsystem gilt heute als sehr unwahrscheinlich. George Booles Arbeit von 1854 zur später so genannten Booleschen Algebra bereitete den Weg für elektronische Schaltungen zur binären Arithmetik.

Wichtige frühe technische Realisierungen entstanden ab 1937: George Stibitz baute den relaisgestützten Rechner Modell K, Konrad Zuse die mechanische Z1 und Claude Shannon verband in seiner MIT-Abschlussarbeit Boolesche Algebra mit elektrischen Relais und Schaltern. John Atanasoff und Clifford Berry bauten von 1937 bis 1941 den elektronischen Atanasoff-Berry-Computer. Am 12. Mai 1941 führte Zuse die elektromechanische Z3 als weltweit ersten universell programmierbaren binären Digitalrechner vor. Am 19. März 1955 präsentierten die Bell-Forschungslaboratorien mit dem TRansistorized Airborne DIgital Computer den ersten ausschließlich aus Halbleiter-Elementen aufgebauten binären Digitalrechner.