Der Arithmetische Überlauf (englisch arithmetic overflow) oder Zählerüberlauf (engl. counter overflow) tritt beim Rechnen in einem begrenzten Zahlenbereich immer dann auf, wenn das Ergebnis den Zahlenbereich nach oben oder unten überschreitet.

Begrenzte Zahlenbereiche kommen hauptsächlich in Computern vor, aber auch in Taschenrechnern und Kilometerzählern. Die Auswirkungen eines Überlaufs sind situationsabhängig.

Ganze Zahlen ohne Vorzeichen

Die einfachsten Datentypen in Computern sind Ganzzahlen ohne Vorzeichen. Der Datentyp Byte kann 256 unterschiedliche Werte darstellen, und diese Werte können als Zahlen im Bereich von 0 bis 255 interpretiert werden. Wenn in diesem Zahlenbereich beispielsweise die Zahlen 200 und 100 addiert werden, ist das Ergebnis 300 und damit größer als der Maximalwert 255. Bei dieser Addition passiert ein arithmetischer Überlauf, das Ergebnis und das weitere Verhalten sind situationsabhängig.

Bereits vor einer Addition ${\displaystyle a+b}$ lässt sich erkennen, ob ein Überlauf passieren wird. Ein Überlauf passiert dann, wenn die Ungleichung ${\displaystyle a+b>{\textit {max}}}$ erfüllt ist. Formt man diese Ungleichung so um, dass es in keinem der Rechenschritte zu einem Überlauf kommen kann, ergibt sich die Ungleichung ${\displaystyle a>{\textit {max}}-b}$. Beim Beispiel der Addition ${\displaystyle 200+100}$ im Zahlenbereich von 0 bis 255 ergibt sich die Ungleichung ${\displaystyle 200>255-100}$, umgeformt ${\displaystyle 200>155}$, die Gleichung ist erfüllt, daher passiert ein Überlauf.

Für die Rechenarten Subtraktion, Multiplikation und Division ergeben sich die Prüfbedingungen durch analoge Überlegungen.

Überlauf bei ganzen Zahlen ohne Vorzeichen

Rechnung	Bedingung für Überlauf
${\displaystyle a+b}$	${\displaystyle a>{\textit {max}}-b}$
${\displaystyle a-b}$	${\displaystyle a<b}$
${\displaystyle a\cdot b}$	${\displaystyle a>{\textit {max}}/b}$
${\displaystyle a/b}$	${\displaystyle b=0}$

Bei der Addition und der Multiplikation muss nur die obere Grenze des Zahlenbereichs geprüft werden, da die untere Grenze rein mathematisch schon nicht unterschritten werden kann. Es ist zum Beispiel nicht möglich, zwei positive Zahlen zu addieren und als Ergebnis eine negative Zahl zu erhalten.

Ganze Zahlen mit Vorzeichen

Bei ganzen Zahlen mit Vorzeichen gelten analoge Überlegungen wie bei ganzen Zahlen ohne Vorzeichen. In Computern werden ganze Zahlen mit Vorzeichen im Zweierkomplement dargestellt. Dadurch liegt die Hälfte der darstellbaren Zahlen im negativen Bereich, und die 0 teilt sich mit den positiven Zahlen die andere Hälfte. Dadurch gibt es eine negative Zahl mehr als positive Zahlen.

Die Prüfbedingungen für den Überlauf müssen so ergänzt werden, dass sie beide Bereichsgrenzen abdecken. Dadurch, dass bei den Prüfbedingungen kein Überlauf passieren darf, benötigen die Ungleichungen Fallunterscheidungen und werden etwas aufwendiger als bei den Zahlen ohne Vorzeichen.

Überlauf bei ganzen Zahlen mit Vorzeichen

Rechnung	Bedingungen für Überlauf
${\displaystyle a+b}$	${\displaystyle a>0\land b>0\land a>{\textit {max}}-b}$ ${\displaystyle a<0\land b<0\land a<{\textit {min}}-b}$
${\displaystyle a-b}$	${\displaystyle a>0\land b<0\land a>{\textit {max}}+b}$ ${\displaystyle a<0\land b>0\land a<{\textit {min}}+b}$
${\displaystyle a\cdot b}$	${\displaystyle a>0\land b>0\land |a|>|{\textit {max}}|/|b|}$ ${\displaystyle a>0\land b<0\land |a|>|{\textit {min}}|/|b|}$ ${\displaystyle a<0\land b>0\land |a|>|{\textit {min}}|/|b|}$ ${\displaystyle a<0\land b<0\land |a|>|{\textit {max}}|/|b|}$
${\displaystyle a/b}$	${\displaystyle b=0}$ ${\displaystyle a={\textit {min}}\land b=-1}$

Die Betragsfunktion, die beim Prüfen der Multiplikation verwendet wird, muss einen Wertebereich haben, der groß genug ist, dass beim Berechnen von ${\displaystyle |{\textit {min}}|}$ kein Überlauf auftritt. Im Zweierkomplement erfüllt der entsprechende vorzeichenlose Datentyp diese Bedingung.

Gleitkommazahlen

Der Wertebereich von Gleitkommazahlen ist deutlich umfangreicher als der von Ganzzahlen, auf Kosten der Genauigkeit. Bei einem Überlauf wird in IEEE 754 mit ±∞ weitergerechnet.

Auswirkungen

Die Auswirkungen eines Überlaufs sind situationsabhängig und reichen von einem Weiterrechnen mit falschen Zahlen über Programmabstürze bis zu Sicherheitslücken in Computern.

Programmierschnittstelle

Beim Programmieren in Assemblersprachen hat der Programmierer direkten Zugriff auf den Prozessor, insbesondere die Arithmetisch-logische Einheit und deren Statusregister, in dem festgehalten wird, ob im letzten Rechenschritt ein Überlauf auftrat. In höheren Programmiersprachen ist dieser direkte Zugriff nicht möglich, dort muss eine Überlauferkennung entweder von der Laufzeitumgebung bereits abgefangen werden oder selbst programmiert werden.

Addition zweier positiver Zahlen	Addition negativer Zahlen mit Überlauf	Addition negativer Zahlen ohne Überlauf
${\displaystyle {{\begin{matrix}\ &{\ }_{\ }&0_{\ }&1_{\ }&0_{\ }&1&&&5_{10}\\+&{\ }_{\ }&0_{\color {Red}1}&1_{\ }&0_{\color {Red}1}&1&&&5_{10}\end{matrix}} \over {\begin{matrix}\quad &{(0)}_{\ }&1_{\ }&0_{\ }&1_{\ }&0_{\ }&&&-6_{10}\end{matrix}}}}$	${\displaystyle {{\begin{matrix}\ &{\ }_{\ }&1_{\ }&0_{\ }&1_{\ }&1&&&-5_{10}\\+&{\ }_{\color {Red}1}&1_{\ }&0_{\color {Red}1}&1_{\color {Red}1}&1&&&-5_{10}\end{matrix}} \over {\begin{matrix}\quad &{(1)}_{\ }&0_{\ }&1_{\ }&1_{\ }&0_{\ }&&&6_{10}\end{matrix}}}}$	${\displaystyle {{\begin{matrix}\ &{\ }_{\ }&1_{\ }&1_{\ }&1_{\ }&1&&&-1_{10}\\+&{\ }_{\color {Red}1}&1_{\color {Red}1}&1_{\color {Red}1}&0_{\color {Red}1}&1&&&-3_{10}\end{matrix}} \over {\begin{matrix}\quad &{(1)}_{\ }&1_{\ }&1_{\ }&0_{\ }&0_{\ }&&&-4_{10}\end{matrix}}}}$

Verallgemeinerung

Operation	richtiges Ergebnis	Überlauf
A + B	${\displaystyle c_{n}=0,c_{n-1}=0}$	${\displaystyle c_{n}=0,c_{n-1}=1}$
A - B	${\displaystyle c_{n}=c_{n-1}}$	nicht möglich
-A - B	${\displaystyle c_{n}=1,c_{n-1}=1}$	${\displaystyle c_{n}=1,c_{n-1}=0}$

Man muss sich stets die letzten beiden Überträge anschauen, hier ${\displaystyle c_{n}}$ und ${\displaystyle c_{n-1}}$ genannt. Sind diese ungleich, dann ist das Ergebnis falsch, als Resultat eines Überlaufes. Bei der Addition einer positiven und einer negativen Zahl kann dies nie der Fall sein.

Siehe auch

• Überlaufbit
• Der Übertrag (engl. carry) entsteht beim Rechnen mit einzelnen Ziffern, er zeigt keinen Fehlerzustand an.
• Der Unterlauf tritt auf, wenn das Ergebnis eines Rechenschritts zwar innerhalb des Gültigkeitsbereichs liegt, aber betragsmäßig so klein (nah bei 0) ist, dass er aufgrund zu geringer Genauigkeit des verwendeten Datentyps fälschlicherweise zu 0 wird.
• Langzahlarithmetik, um die Begrenzung auf eine feste Anzahl von Ziffern zu umgehen.
• Bei Computern, die vom Jahr-2038-Problem betroffen sind, springen Datum und Uhrzeit auf 1901 zurück.
• Arithmetischer Unterlauf
• Pufferüberlauf

Literatur

• Blexim: Basic Integer Overflows. In: Phrack-Magazin. 11, Nr. 60, Februar 2002

Einzelnachweise

1. ↑ Fricke, Klaus. Digitaltechnik: Lehr- und Übungsbuch für Elektrotechniker und Informatiker. 5. Aufl. Vieweg+Teubner, 2007. Print, Seite 9.