Stellenwertsystem

Grundprinzip und Aufbau

Ein Stellenwertsystem, Positionssystem oder polyadisches Zahlensystem stellt Zahlen durch Ziffern dar, deren Beitrag zum Gesamtwert von ihrer Position abhängt. Im Dezimalsystem bedeutet 127 daher 1·100 + 2·10 + 7·1. Der Ziffernwert ist der einer Ziffer zugeordnete Wert; der Stellenwert ist das Gewicht ihrer Position.

Die Basis oder Grundzahl b bestimmt, um welchen Faktor der Stellenwert von einer Stelle zur nächsten wächst. Ein System zur Basis b heißt b-adisches Zahlensystem und besitzt gewöhnlich genau b Ziffern mit den Werten 0,1,…,b−1. Jede ganze Zahl b≥2 eignet sich als Basis; b=1 widerspräche dem Stellenwertprinzip, weil dann alle Stellen dasselbe Gewicht hätten. Die Stelle ganz rechts besitzt den Stellenwert b^0=1, die nächste b^1, danach folgen b^2, b^3 usw. Allgemein hat die mit i nummerierte Stelle den Stellenwert b^i.

Für eine dreistellige natürliche Zahl gilt Z=a₂·b²+a₁·b¹+a₀·b⁰. Beim Überschreiten der höchsten Ziffer entsteht ein Übertrag zur nächsten Stelle. Führt dieser auf eine noch unbesetzte Stelle, wird sie zunächst mit 0 besetzt. So kann mit endlich vielen Ziffernsymbolen unbegrenzt weitergezählt werden. Die benötigte Stellenzahl wächst logarithmisch mit der Größe der Zahl.

Wichtige Systeme sind das Dual- oder Binärsystem mit b=2 und den Ziffern 0,1, das Dezimalsystem mit b=10 und 0 bis 9 sowie das Hexadezimalsystem mit b=16 und 0 bis 9, A bis F. Im Hexadezimalsystem besitzen A bis F die Werte 10 bis 15. Das Dualsystem ist grundlegend für die Digitaltechnik; eine Hexadezimalstelle entspricht genau vier Binärstellen. Das Oktalsystem mit b=8 fasst jeweils drei Binärstellen zusammen. Weitere verwendete Basen sind 12 beim Duodezimalsystem, 20 beim Vigesimalsystem, 60 beim Sexagesimalsystem sowie 32 und 64 bei Base32 und Base64.

Darstellung verschiedener Zahlenarten

Eine natürliche Zahl wird durch eine endliche Ziffernfolge aₙ…a₂a₁a₀ dargestellt. Ihr Wert ist Z=∑ᵢ₌₀ⁿ aᵢ·bⁱ=a₀·b⁰+a₁·b¹+…+aₙ·bⁿ. Ohne führende Nullen besitzt jede natürliche Zahl genau eine solche Darstellung. Die Null wird nicht als leere Folge, sondern durch eine einzelne Ziffer 0 geschrieben. Die Stellenzahl einer natürlichen Zahl Z ist m=1 für Z=0 und m=⌊log_b Z⌋+1 für Z≥1.

Bei positiver Basis und ausschließlich nichtnegativen Ziffernwerten benötigen negative ganze Zahlen ein vorangestelltes Minuszeichen. Dadurch kann die Null als +0, −0 oder ±0 erscheinen. Ein Pluszeichen kann positive Zahlen ausdrücklich kennzeichnen.

Rationale Zahlen erhalten Stellen mit negativen Exponenten rechts eines Trennzeichens. Im deutschsprachigen Raum außer der Schweiz wird meist das Komma verwendet. Die i-te Nachkommastelle hat das Gewicht b^(−i). So gilt im Dualsystem 1,011₂=1·2⁰+0·2⁻¹+1·2⁻²+1·2⁻³=1+1/4+1/8=1+3/8=1,375₁₀.

Rationale Zahlen besitzen entweder eine endliche oder eine unendliche periodische b-adische Darstellung. Ein vollständig gekürzter Bruch hat genau dann eine endliche Darstellung, wenn alle Primfaktoren seines Nenners auch Primfaktoren der Basis b sind. Im Dezimalsystem darf der gekürzte Nenner daher nur die Primfaktoren 2 und 5 enthalten. Beispielsweise ist 1/5=0,2₁₀ endlich, im Dualsystem aber periodisch: 0,00110011…₂. Darstellungen sind nicht immer eindeutig: Im Dezimalsystem bezeichnen etwa 1, 1,0 und 1,000 dieselbe Zahl; außerdem gilt 0,999…=1.

Bei reellen Zahlen liefert die b-adische Entwicklung für rationale Zahlen abbrechende oder periodische Folgen. Irrationale Zahlen wie π oder √2 ergeben stets unendliche, nichtperiodische Ziffernfolgen. Durch zusätzliche Nachkommastellen kann man sie beliebig genau annähern. Jede reelle Zahl ist als gegebenenfalls unendlicher b-adischer Bruch darstellbar, aber mit einem endlichen Zeichenvorrat können nicht alle reellen Zahlen durch endliche Zeichenfolgen dargestellt werden.

Berechnung und Umwandlung

Die letzte Ziffer einer natürlichen Zahl Z zur Basis b ist der Rest bei der Division durch b: a₀=Z−b⌊Z/b⌋. Allgemein berechnet sich die Ziffer an Stelle i durch aᵢ=⌊Z/bⁱ⌋−b⌊Z/bⁱ⁺¹⌋. Diese Gleichung gilt bei positiv reellen Zahlen auch für negative i und damit für Nachkommastellen.

Zur Umwandlung einer natürlichen Zahl in eine neue Basis verwendet man die wiederholte euklidische Division durch diese Basis. Die Reste ergeben vom ersten bis zum letzten die Ziffern von der niedrigsten zur höchsten Stelle. Umgekehrt wertet man eine vorhandene Ziffernfolge als Ziffernpolynom aus; effizient geschieht dies nach dem Horner-Schema von der höchstwertigen Stelle aus.

Beim Anhängen einer Ziffer a rechts an eine natürliche Zahl Z entsteht Z·b+a. Wird a als erste Nachkommastelle angefügt, entsteht Z+a·b⁻¹. Wird a links vor eine Zahl mit höchster Stelle n gesetzt, ergibt sich a·bⁿ⁺¹+Z.

Für einen rationalen Wert 0<p/q<1 werden die Nachkommastellen erzeugt, indem der aktuelle Rest p wiederholt mit b multipliziert wird. Die nächste Ziffer ist z=⌊bp/q⌋, der neue Rest ist p′=bp−zq mit 0≤p′<q. Ein Rest 0 beendet die Darstellung. Da nur q verschiedene nichtnegative Reste kleiner als q möglich sind, muss sich andernfalls ein Rest wiederholen; damit beginnt eine Periode. Ziffern- und Restperiode haben dieselbe Länge.

Typische Beispiele

Die Zahl 694 zeigt, wie verschiedene Darstellungen denselben Wert besitzen:

• 694₁₀=4·10⁰+9·10¹+6·10². • 2B6₁₆=6+11·16+2·16²=6+176+512=694. • 1010110110₂=2+4+16+32+128+512=694.

Für die Umwandlung von 4711₁₀ in das Zwölfersystem wird wiederholt durch 12 dividiert. Die Divisionen liefern nacheinander die Reste 7, 8, 8 und 2. Von der höchsten zur niedrigsten Stelle gelesen ergibt das 2887₁₂.

Bei AFFE₁₆ werden die Ziffern mit ihren Stellenwerten multipliziert: 10·16³+15·16²+15·16¹+14·16⁰=40 960+3840+240+14=45 054. Dasselbe Ergebnis liefert das Horner-Schema: 10; danach 10·16+15=175; 175·16+15=2815; schließlich 2815·16+14=45 054.

Für Nachkommastellen wird der Nachkommaanteil wiederholt mit der Zielbasis multipliziert. Bei 0,1₁₀ und Zielbasis 2 entstehen aus 0,1·2=0,2, 0,2·2=0,4, 0,4·2=0,8, 0,8·2=1,6 und 0,6·2=1,2 die Ziffern 00011; danach wiederholt sich ein bereits aufgetretener Rest. Daher gilt 0,1₁₀=0,0001100110011…₂.

Besondere Systeme und gemischte Basen

Balancierte Stellenwertsysteme besitzen eine ungerade Basis b und verwenden die Ziffernwerte −(b−1)/2,…,−1,0,1,…,(b−1)/2. Im balancierten Ternärsystem sind dies −1, 0 und 1. Das Negative einer Zahl entsteht durch Austausch jeder Ziffer gegen ihr additives Gegenstück; die erste von 0 verschiedene Ziffer zeigt das Vorzeichen, sodass kein separates Vorzeichen nötig ist. Runden zur nächsten ganzen Zahl geschieht durch Abschneiden am Komma. Ganze Zahlen sind eindeutig, rationale Zahlen jedoch nicht immer darstellbar.

Bei Zahlensystemen mit gemischten Basen hängt die Basis von der Position ab. Beispiele sind alternierende Basen, die Fakultätsbasis mit den natürlichen Zahlen größer als 1 als aufeinanderfolgenden Basen und Systeme mit aufeinanderfolgenden Primzahlen. Datum und Uhrzeit bilden ein alltägliches Beispiel: Dort treten unter anderem die Basen 2, 10, 12, 28–31 und 60 auf; die Zahl möglicher Tage hängt zusätzlich vom Monat ab.

Auch negative Basen b≤−2 sind möglich. Systeme wie das negabinäre oder negadezimale System verwenden denselben Ziffernvorrat wie die entsprechende positive Basis und benötigen kein Vorzeichen. Bei minimalem Ziffernvorrat sind alle ganzen Zahlen eindeutig darstellbar, die Rechnung und der Größenvergleich sind jedoch aufwendiger. Beispielsweise gilt 999₁₀=19019₋₁₀.

Nichtganzzahlige und irrationale reelle Basen sind ebenfalls möglich. Bei Basis Φ=(1+√5)/2 und Ziffernvorrat {0,1} stellt eine endliche Folge eine ganze Zahl oder eine irrationale Zahl der Form s+t√5 mit rationalen s,t dar; nicht jede solche Zahl hat eine endliche Darstellung. Als komplexe Basis schlug D. Knuth 1955 das quater-imaginäre System mit Basis 2i und den Ziffern 0,1,2,3 vor. Dort gelten −1=103₂ᵢ und i=10,2₂ᵢ.

Ordnung und p-adische Zahlen

Bei positiver Basis hängt die Zahlenordnung eng mit der lexikographischen Ordnung zusammen, also dem Vergleich von Ziffernfolgen von links nach rechts. Die Auswertung beliebig langer Folgen ist ordnungserhaltend, aber nicht injektiv: Verschiedene Folgen können dieselbe reelle Zahl darstellen. Die Zahlen mit mehreren Darstellungen bilden eine abzählbare Teilmenge der rationalen Zahlen und liegen dicht im dargestellten Intervall. In üblichen Systemen mit kleinster Ziffer 0 sind dies gerade die Zahlen mit endlicher Darstellung, entsprechend dem bekannten Fall 0,999…=1.

Nicht zu verwechseln sind b-adische Stellenwertdarstellungen mit p-adischen Zahlen. Die gewöhnlichen Systeme verwenden den archimedischen Absolutbetrag; ihre unendlichen Reihen laufen rechts zu immer kleineren Potenzen. Bei p-adischen Zahlen beruhen Konvergenz und Abstand auf einer nichtarchimedischen Betragsfunktion. Dort laufen unendliche Entwicklungen nach links zu immer größeren Potenzen.

P-adische Darstellungen sind umkehrbar eindeutig und benötigen kein Vorzeichen; beispielsweise gilt −1=∑ᵢ₌₀∞(p−1)·pⁱ. Ein p-adischer Ring kann nicht angeordnet werden. Ist p keine Primzahl, enthält der Ring ℤ_p Nullteiler. Endliche Ausdrücke stimmen mit gleichlautenden endlichen Darstellungen zur Basis b=p überein, nicht abbrechende Reihen besitzen in beiden Systemarten jedoch grundverschiedene arithmetische Eigenschaften. Periodische Folgen stellen in beiden Fällen rationale Zahlen dar. Die Grundrechenarten beginnen rechts bei den kleinen Exponenten und führen Potenzen und Überträge nach links weiter.