Arithmetischer Überlauf

Der Arithmetische Überlauf (engl. arithmetic overflow) oder Zählerüberlauf (engl. counter overflow), ist ein Begriff aus der Informatik. Solch ein Überlauf tritt auf, wenn das Ergebnis einer Berechnung für den gültigen Zahlenbereich zu groß ist, um noch richtig interpretiert werden zu können.

Zumeist wird man dem Überlauf beim Rechnen mit Zweierkomplementzahlen begegnen. So kann es passieren, dass bei der Addition zweier Zahlen mit gleichem Vorzeichen eine Zahl mit anderem Vorzeichen entsteht. In diesem Fall setzt der Prozessor das Überlaufbit. Mit einigen Prozessoren und Programmiersprachen kann ein Überlauf durch einen Laufzeitfehler oder eine Ausnahmebehandlung (Exception) aufgefangen werden.

Der Überlauf hängt immer von der verwendeten Zahlendarstellung ab. Er ist keinesfalls mit dem Übertrag (engl. Carry) zu verwechseln.

Beispiele

32 Bit Integer

Der auf 32-Bit-Prozessoren häufigst verwendete Ganzzahl-Datentyp Integer kann im Zweierkomplement die Werte –2³¹ = –2.147.483.648 bis +(2³¹)–1 = +2.147.483.647 darstellen. Wird nun zu +2.147.483.647 (Binär 01111111 11111111 11111111 11111111) eins dazugezählt, erhält man nicht wie erwartet +2.147.483.648, sondern –2.147.483.648, da der Binärwert 10000000 00000000 00000000 00000000 als negative Zahl interpretiert wird. Ein solcher Überlauf ist auch die Ursache für das Jahr-2038-Problem.

4 Bit im Zweierkomplement

Im Zweierkomplement sind positive und negative Zahlen darstellbar, sodass die Subtraktion auf die Addition zurückgeführt werden kann. Es sind 3 Fälle zu betrachten:

Addition zweier positiver Zahlen	Addition negativer Zahlen mit Überlauf	Addition negativer Zahlen ohne Überlauf
${\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}}$	${\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}}$	${\begin{matrix} \ &{\ }_{\ } &1_{\ } & 1_{\ } & 1_{\ } &1 &&& -1_{10} \\ + &{\ }_{\color{Red}1} & 1_{\color{Red}1} & 1_{\ } & 0_{\color{Red}1} & 1 &&& -3_{10} \end{matrix}\over \begin{matrix} \quad &{(1)}_{\ } & 1_{\ } & 1_{\ } & 0_{\ } & 0_{\ } &&& -4_{10} \end{matrix}}$

Alle in 4Bit darstellbaren Zahlen als Kreis; addiert man z. B. 5 und 5 sucht man sich die dargestellte 5 und geht im Uhrzeigersinn 5 Einheiten weiter, es kommt zum "Überlaufen" des Kreises und man landet bei der -6.

• Verallgemeinerung ^[1]

Operation	richtiges Ergebnis	Überlauf
A + B	cn = 0,cn − 1 = 0	cn = 0,cn − 1 = 1
A - B	cn = cn − 1	nicht möglich
-A - B	cn = 1,cn − 1 = 1	cn = 1,cn − 1 = 0

Man muss sich stets die letzten beiden Überträge anschauen, hier c_n und 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.

• Folgerung

In einer 4-Bit-Architektur, die mit dem Zweierkomplement arbeitet, ist z. B. die Dezimalzahl 10 nicht dual abbildbar.

Manche Prozessoren können einen Überlauf durch ein Überlaufbit registrieren.

Siehe auch

Arithmetischer Unterlauf

Einzelnachweise

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