Zum Hauptinhalt springen

Ganze Zahlen

Autor:in

Karsten Brodmann

Veröffentlichungsdatum

23. September 2026

Ganze Zahlen kennen Sie aus der Schule. Sie werden dort mit dem Mengensymbol \mathbb{Z} bezeichnet. Wir meinen damit die Zahlen \dots, -3, -2, -1, 0, 1, 2, 3, \dots. In der Mathematik betrachten wir sie als eine unendliche Menge ganzer Zahlen. Auf dem Computer haben wir auch ganze Zahlen, die dortige Menge ganzer Zahlen ist jedoch eingeschränkt. Je nach Programmiersprache stehen uns eventuell verschiedene Datentypen für ganze Zahlen zur Verfügung, die dann jeweils einen bestimmten Wertebereich umfassen. Bei Java sind das beispielsweise die folgenden Datentypen.

Primitive ganzzahlige Datentypen in Java
Datentyp Bits Wertbereich
byte 8 (-2)^7 bis 2^7-1
short 16 (-2)^{15} bis 2^{15}-1
int 32 (-2)^{31} bis 2^{31}-1
long 64 (-2)^{63} bis 2^{63}-1

Bereits beim Betrachten der obigen Tabelle stellen wir fest, dass der Wertebereich, je nach Datentyp, deutlich eingeschränkt ist und ganze Zahlen offensichtlich asymmetrisch um die Null verteilt sind. Im negativen Bereich haben wir jeweils eine Zahl mehr zur Verfügung als im positiven Bereich.

Stolperstein

Neben den offensichtlich unterschiedlichen Wertebereichen der verschiedenen ganzzahligen Datentypen in Java, gibt es einen weiteren Unterschied, den wir uns direkt erarbeiten wollen. Dazu schauen wir uns das folgende Programm faculty.java an.

public class Faculty {
    
    public static int faculty(int x) {
        int f = 1;
        while (x > 0) {
            f = f * x;
            x--;
        }
        return f;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.printf("%2d! = %d%n", n,  faculty(n));
    }
}

Zum Vergleich implementieren wir das gleiche Programm in Python (Faculty.py)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

def faculty(x: int) -> int:
    f: int = 1

    while x > 0:
        f = f * x
        x -= 1
    return f

n = int(sys.argv[1])
print(f"{n:2d}! = {faculty(n)}")

Nun lassen wir beide Programm in einer Shell-Schleife, bei mir unter macOS, ausführen. Wir fangen die Ausgaben ab und geben die Resultate als Tabelle formatiert aus.

#!/bin/bash

# Überschrift für die Tabelle
echo "JAVA AUSGABE                   | PYTHON AUSGABE"
echo "-------------------------------+-------------------------------"

# Schleife von 1 bis 20
for i in {1..20}; do
    # Fängt die jeweilige Single-Line-Ausgabe in Variablen ab
    output_java=$(java Faculty "$i")
    output_python=$(python3 Faculty.py "$i")

    # Formatiert nebeneinander ausgeben
    printf "%-30s | %-30s\n" "$output_java" "$output_python"
done

Hier sehen Sie das Ergebnis:

$ ./faculty.sh 
JAVA AUSGABE                   | PYTHON AUSGABE
-------------------------------+-------------------------------
 1! = 1                        |  1! = 1                       
 2! = 2                        |  2! = 2                       
 3! = 6                        |  3! = 6                       
 4! = 24                       |  4! = 24                      
 5! = 120                      |  5! = 120                     
 6! = 720                      |  6! = 720                     
 7! = 5040                     |  7! = 5040                    
 8! = 40320                    |  8! = 40320                   
 9! = 362880                   |  9! = 362880                  
10! = 3628800                  | 10! = 3628800                 
11! = 39916800                 | 11! = 39916800                
12! = 479001600                | 12! = 479001600               
13! = 1932053504               | 13! = 6227020800              
14! = 1278945280               | 14! = 87178291200             
15! = 2004310016               | 15! = 1307674368000           
16! = 2004189184               | 16! = 20922789888000          
17! = -288522240               | 17! = 355687428096000         
18! = -898433024               | 18! = 6402373705728000        
19! = 109641728                | 19! = 121645100408832000      
20! = -2102132736              | 20! = 2432902008176640000    
$ _

Feststellung: Die Fakultät ist eine stetig wachsende Funktion. Spätestens bei 17! werden wir stutzig. Das Java-Programm gibt einen negativen Wert aus. Aufmerksame Betrachter werden bereits bei 13! aufmerksam. Da wir zwischenzeitig mit 10 multipliziert haben, muss zwingend eine Null am Ende der Zahl stehen. 14! ist kleiner als 13! und, wie gesagt, irgendwann gibt es sogar negative Resultate. - Irgendetwas kann da nicht stimmen.

Hinweis: Glauben Sie nicht, Java wäre, vor dem Hintergrund des obigen Experiments, eine schlechte Programmiersprache. Das hier gezeigte Phänomen können Sie bei fast allen Programmiersprachen in eben dieser Form beobachten. - Wir werden dem auf den Grund gehen und eine Erklärung finden.

Zwecks Nachvollziehbarkeit der Analyse, beginnen wir ganz am Anfang!

Zahlen sind ein abstraktes Konzept - Stellenwertsysteme

Im Gegensatz zu Hunden, Katzen, Bäumen oder Eiern kann man Zahlen weder sehen noch sie berühren. Zahlen existieren nur in unseren Köpfen. Was wir sehen, ist beispielsweise das Symbol „3“. Das ist aber nicht dasselbe. So ist das Foto einer Pfeife auch keine Pfeife. Neben dem Symbol gibt es weitere Arten und Weisen, dieselbe Zahl zu repräsentieren. Da haben wir das Wort „drei“, die römischen Ziffern „III“ oder gerne auch das englische Wort „three“. Sie können sich, ohne viel Fantasie, weitere Repräsentationsformen denken.

Dezimalzahlen

Die weltweit häufigste Darstellung von Zahlen ist das indisch-arabische Dezimalsystem. Es gab und gibt andere Systeme. Das indisch-arabische Dezimalsystem hat sich aber in unseren Köpfen durchgesetzt. Der Grund dafür ist leicht nachvollziehbar: Es ist einfach zu verstehen und effizient anzuwenden. Im Gegensatz zu anderen Systemen, erleichtert es uns Menschen Berechnungen jeglicher Art.

Die meisten Menschen rechnen nicht mehr im Kopf. Sie verwenden Taschenrechner oder die entsprechende App auf ihrem Smartphone. Dennoch sollten Ihnen die Regeln der schriftlichen Addition und Multiplikation aus der Schule geläufig sein.

Das Schöne an diesen Verfahren ist, dass wir nur mit kleinen Zahlen im Kopf rechnen müssen. Es reicht aus, das kleine Einmaleins zu beherrschen, um letztlich mit beliebig großen Zahlen rechnen zu können. Und das ist es, was das indisch-arabische Dezimalsystem zum Durchbruch verholfen hat. Es ist nämlich ein Stellenwertsystem.

Jede Ziffer einer Zahl hat in einem Stellenwertsystem einen Wert, der sich aus der Stelle ihrer Notation innerhalb der Zahl ergibt. Bei dezimalen Zahlen ist die Basis des Stellenwertes 10.

Beispiel:

\begin{array}{rcrcrcrrcrcrrcrcrrcrcr} 9336 & = & & & 9000 & + & & & 300 & + & & & 30 & + & 6 & & \\ & = & 9 & \cdot & 1000 & + & 3 & \cdot & 100 & + & 3 & \cdot & 10 & + & 6 & \cdot & 1 \\ & = & 9 & \cdot & 10^3 & + & 3 & \cdot & 10^2 & + & 3 & \cdot & 10^1 & + & 6 & \cdot & 10^0 \\ \end{array}

Das bedeutet insbesondere, dass die linke 3 etwas anderes bedeutet als die folgende 3. Die erste steht für 300, die zweite für 30. Wir kommen daher mit lediglich 10 Symbolen aus, um beliebige Zahlen damit auszudrücken.

Das Schema der Wertermittlung nennt sich auch Horner-Schema.

Binärzahlen

Positive Binärzahlen

Während das Dezimalsystem die Basis 10 hat, basiert das Binärsystem auf der Basis 2. Da es sich ebenfalls um ein Stellenwertsystem handelt, können wir den Wert einer binär notierten Zahl auf dem gleichen Wege bestimmen, wie wir es mit einer Dezimalzahl tun. Wir haben lediglich die Basis auszutauschen. Hierbei betrachten wir vorerst nur positive Binärzahlen.

Beispiel:

\begin{array}{rcrcrcrrcrcrrcrcrrcrcrcr} 1001_2 & = & & & 8 & + & & & 0 & + & & & 0 & + & & & 1 & = & 9\\ & = & 1 & \cdot & 8 & + & 0 & \cdot & 4 & + & 0 & \cdot & 2 & + & 1 & \cdot & 1 & = & 9\\ & = & 1 & \cdot & 2^3 & + & 0 & \cdot & 2^2 & + & 0 & \cdot & 2^1 & + & 1 & \cdot & 2^0 & = & 9\\ \end{array}

Hinweis: Zur Kennzeichnung der Binärzahl ist sie mit einem Subskript 2 versehen.

Wir können hinsichtlich der binären Zahlen nicht nur deren Wert auf bekannte Art und Weise ermitteln, die uns bekannten Regeln zum Addieren und Multiplizieren gelten ebenso.

Beispiel für die Addition binärer Zahlen:

\begin{array}{rcccccr} & & 1 & 0 & 1 & 1 & (11_{10})\\ + & & & 1 & 0 & 1 & (5_{10}) \\ \hline \text{Übertrag} & & 1 & 1 & 1 & & \\ \hline & 1 & 0 & 0 & 0 & 0 & (16_{10})\\ \hline \hline \end{array}

So, wie hier dargestellt, bilden unsere Computer positive Binärzahlen (ohne Vorzeichenbehaftung) ab. Jedes Digit, 0 oder 1, belegt dabei ein Bit.

Negative Binärzahlen und 2er-Komplement

Wenn wir einen geeigneten Taschenrechner besitzen, können wir mit dem auch mit binären Zahlen rechnen. In der Regel verwenden diese Rechner die oben vorgestellte Darstellung binärer Zahlen. Negative Binärzahlen werden mit einem vorangestellten Minuszeichen im Display angezeigt. Diese Darstellung ist bezüglich der internen Kodierung, wie ganze Zahlen im Computer abgebildet werden nicht geeignet.

In einem Byte, welches 8 Bit besitzt, lassen sich nach dem oben vorgestellten Prinzip die Zahlen 0 bis 255 kodieren. Bei einigen Programmiersprachen kann man ganzzahlige Datentypen so deklarieren, kein Vorzeichen zu haben. Z.B. ist das in der Programmiersprache C der Datentyp uint8_t, der in <stdint.h> definiert ist. In klassischem C, wo der Datentyp char für kleine ganze Zahlen verwendet wird, drückt man die Vorzeichenlosigkeit mit unsigned char aus.

In Java sind dagegen alle ganzen Zahlen vorzeichenbehaftet. Das gilt auch für Python und einige andere Programmiersprachen.

So oder so, stellt sich die Frage, wie das Vorzeichen darzustellen, zu kodieren, ist. Viele Möglichkeiten dazu existieren nicht. Eine naheliegende Idee wäre, ein Bit zur Kennzeichnung des Vorzeichens zu verwenden. Hierbei bietet sich das ganz links stehende Bit, das bislang höchstwertigste Bit, an. Wir nennen es in diesem Zusammenhang Vorzeichenbit.

Das Vorzeichenbit reduziert die darzustellende Zahl um ein Bit, welches nun zur Kodierung des Zahlenwertes nicht mehr verfügbar ist. Bei einer 1-Byte-Zahl haben wir dann ein Bit für das Vorzeichen und sieben Bits für den Zahlenwert.

Betrachten wir zuerst den nicht-negativen Wertebereich. Dann sind offensichtlich die folgenden Kodierungen möglich.

   0 1 1 1 1 1 1 1       (+127)
   0 1 1 1 1 1 1 0       (+126)
   0 1 1 1 1 1 0 1       (+125)
   ...
   0 0 1 0 1 0 1 0       (+ 42)
   ...
   0 0 0 0 0 0 1 0       (+  2)
   0 0 0 0 0 0 0 1       (+  1)
   0 0 0 0 0 0 0 0       (   0)

Eine Idee zur Abbildung der negativen Zahlen könnte nun sein, dieselbe Kodierung der positiven Zahlen zu nutzen und lediglich das Vorzeichenbit zu setzen. Das ergäbe dann (ausschnittsweise) das folgende Bild.

  0 1 1 1 1 1 1 1       (+127)
  0 1 1 1 1 1 1 0       (+126)
  0 1 1 1 1 1 0 1       (+125)
  ...
  0 0 0 0 0 0 1 1       (+  3)
  0 0 0 0 0 0 1 0       (+  2)
  0 0 0 0 0 0 0 1       (+  1)
  0 0 0 0 0 0 0 0       (   0)
  1 0 0 0 0 0 0 0       (   0)
  1 0 0 0 0 0 0 1       (-  1)
  1 0 0 0 0 0 1 0       (-  2)
  1 0 0 0 0 0 1 1       (-  3)
  ...
  1 1 1 1 1 1 1 1       (-127)

Eines fällt sofort ins Auge. Die Null hat zwei Repräsentationen. Das ist nicht gut. Zum Anderen können wir unsere erlernten Rechenregeln nicht mehr anwenden. So sollte 1 + (-2) = -1 ergeben. Prüfen wir das nach.

  0 0 0 0 0 0 0 1       (+  1)
+ 1 0 0 0 0 0 1 0       (-  2)
------------------------------
  1 0 0 0 0 0 1 1       (-  3)

Das Ergebnis ist, wenn wir die gezeigte Kodierung und die bekannten Rechenregeln anwenden, offensichtlich falsch.

Wir haben uns mit unserer naiven Kodierung zwei Probleme geschaffen:

  1. Wir haben eine doppelte Null.
  2. Unsere Rechenregeln funktionieren nicht mehr.

2er-Komplement

Findige Köpfe haben sich etwas deutlich besseres ausgedacht. Das ist das sogenannte 2er-Komplement. Rein visuell nimmt man dazu den Block der positiven Zahlen und „klebt“ ihn unter die Null, dabei wird das höchstwertige Bit gesetzt.

  0 1 1 1 1 1 1 1       (+127)
  0 1 1 1 1 1 1 0       (+126)
  0 1 1 1 1 1 0 1       (+125)
  ...
  0 0 0 0 0 0 1 1       (+  3)
  0 0 0 0 0 0 1 0       (+  2)
  0 0 0 0 0 0 0 1       (+  1)
  0 0 0 0 0 0 0 0       (   0)
  1 1 1 1 1 1 1 1       (-  1)
  1 1 1 1 1 1 1 0       (-  2)
  1 1 1 1 1 1 0 1       (-  3)
  ...
  1 0 0 0 0 0 0 0       (-128)

Diese Kodierung löst zudem alle unsere Probleme, die wir mit unserer naiven Kodierung hatten. Wir haben nur noch eine Null und die Rechenregeln funktionieren im 2er-Komplement wieder.

  0 0 0 0 0 0 0 1       (+  1)
+ 1 1 1 1 1 1 1 0       (-  2)
------------------------------
  1 1 1 1 1 1 1 1       (-  1)

Bei einer Zahl mit n Bits hat das Vorzeichenbit im 2er-Komplement den Wert

(-2)^{n-1}

Bei einem 8-Bit-Wert ergibt sich so auch dessen Wertebereich: [-128, 127]. Die obige Darstellung macht auch einsichtig, weshalb ganze Zahlen asymmetrisch um die Null verteilt sind.

Auf die Kodierung einer negativen Zahl kommen wir ganz einfach. Der folgende Algorithmus beschreibt, wie wir vorzugehen haben.

  1. Ermittle das Bitmuster des positiven Wertes der Zahl.
  2. Invertiere die Bits.
  3. Addiere 1.

Beispiel:

Wir wollen das Bitmuster für eine 1-Byte-Ganzzahl mit Vorzeichen von -3 bestimmen.

  1. Bitmuster von 3: 0 0 0 0 0 0 1 1
  2. Invertiere die Bits: 1 1 1 1 1 1 0 0
  3. Addiere 1: 1 1 1 1 1 1 0 1

Das Bitmuster von -3 ist also: 1 1 1 1 1 1 0 1

Nützliche Werkzeuge: Dec2Bin- und Bin2Dec-Konverter

Will man in der Praxis Bit-Operationen ausführen, so ist es von Vorteil, sich die Bits, die man zu manipulieren gedenkt, vorstellen zu können. Es ist daher hilfreich, eine Anwendung zu haben, die uns die Bitmuster ganzer Zahlen, ohne und mit Vorzeichen, anzeigen kann.

Dezimal-Binär-Konvertierung

Zuerst betrachten wir das Werkzeug Dec2Bin. Wir wollen es in Java implementieren. Es soll uns helfen, eine dezimale Ganzzahl in das korrespondierende Bitmuster der entsprechenden Binärzahl umzurechnen. Genauer gesagt, wird unser Werkzeug das Bitmuster lediglich anzeigen. Java gestattet es uns nämlich, im „Speicher zu spicken“ und uns einfach das Bitmuster ausgeben zu lassen, welches Java für seine Berechnungen verwendet.

Wir schreiben das Programm für den Datentyp int. Das ist der in Java am häufigsten gebrauchte Ganzzahl-Datentyp.

/**
 * Die Klasse ermittelt für <code>int</code>-Werte aus deren
 * Dezimaldarstellung die binäre Codierung.
 * 
 * @author Karsten Brodmann (kb@punkt-akademie.de)
 */
public class Dec2Bin {
    /** 
     * Hauptprogramm.
   * 
     * @param args umzurechnende Zahl
     */
    public static void main(String[] args) {
        int dec = Integer.parseInt(args[0]);
        String mask = "00000000000000000000000000000000";
        String bits = Integer.toBinaryString(dec);
        System.out.println((mask+bits).substring(bits.length()));
    }
}

Probieren wir das Programm anhand der Wertgrenzen von int aus.

$ java Dec2Bin 2147483647
01111111111111111111111111111111
$ $java Dec2Bin -2147483648 
10000000000000000000000000000000
$ _

Wir sehen die Kodierungen im besprochenen 2er-Komplement, hier jedoch für 32-Bit-Werte.

Binär-Dezimal-Konvertierung

Auch der umgekehrte Weg, aus einem Binärmuster den dezimalen Wert zu ermitteln, ist einfach. Wir brauchen nicht erst das Horner-Schema (siehe oben), wie ich es für positive Binär-Ganzzahlen im Seminar „Programmieren lernen mit Java” gezeigt habe, implementieren und dabei noch das 2er-Komplement berücksichtigen. Die Methode Integer.parseUnsignedInt() liefert uns das gewünschte Resultat direkt. Wir müssen lediglich als Basis 2 spezifizieren.

/**
 * Die Klasse ermittelt für Bitmuster den korrespondierenden
 * <code>int</code>-Wert.
 *  
 * @author Karsten Brodmann
 */
public class Bin2Dec {

    /**
     * Hauptprogramm.
     * 
     * Achtung: Für negative Binärzahlen muss das Bitmuster
     *          32 Digits umfassen. Führende Nullen bei 
     *          positiven Zahlen können entfallen.
     * @param args Bitmuster
     */
    public static void main(String[] args) {
        int dec = Integer.parseUnsignedInt(args[0], 2);
        System.out.println(dec);
    }
}

Probe:

$ java Bin2Dec 01111111111111111111111111111111
2147483647
$ java Bin2Dec 10000000000000000000000000000000
-2147483648
$ _

Auf Unix-Systemen, also insbesondere auch macOS und Gnu/Linux, bietet sich eine weitere Testmöglichkeit an. Dort können wir als Kommandozeilenargument das Ergebnis eines ausgeführten Programms verwenden.

$ java Bin2Dec `java Dec2Bin 2147483647`
2147483647
$ java Bin2Dec `java Dec2Bin -2147483648`
-2147483648
$ _

Da unsere Programme komplementär sind, muss die Ausgabe des einen Programms, als Eingabe des Komplementärprogramms, wieder die originäre Eingabe ergeben.

Über- und Unterläufe

Wenn Sie bis hierhin aufmerksam den Ausführungen gefolgt sind und sich die Programmcode gewissenhaft angesehen haben, wird Ihnen aufgefallen sein, in Bin2Dec.java die binäre Zeichenkette mit Integer.parseUnsignedInt() eingelesen zu haben. Wie der Name der Methode leicht verrät, wird der übergebene Binärstring als vorzeichenlos interpretiert. Wie kann es dann sein, dass wir eine negative Dezimalzahl als Ergebnis erhalten? - Wenn wir dieses Geheimnis gelüftet haben, können wir auch das seltsame Verhalten der eingangs gezeigten Fakultätsberechnungen erklären.

Alltägliche Über- und Unterläufe

Zuerst betrachten wir ein Beispiel aus dem Alltag. Es hat nichts mit Computern zu tun. Es folgt aber dem gleichen Prinzip, welches wir hier analysieren wollen.

Nehmen Sie an, ein Freund besucht Sie um 11:00 Uhr am Vormittag. Er verlässt Sie nach 3 Stunden um 14:00 Uhr. Umgangssprachlich sagen wir auch 02:00 Uhr (am Nachmittag) zu der Uhrzeit des Verlassens.

Visualisieren wir uns diesen Sachverhalt am Zifferblatt einer Uhr.

Überlauf anhand einer Uhr visualisiert

Überlauf anhand einer Uhr visualisiert
Abbildung 1

Mathematisch betrachtet führen wir, quasi instinktiv, eine Modulo-Operation durch. Das Zifferblatt einer Uhr hat 12 mögliche Ausprägungen. Wenn es überdreht, ist dies analog zu einer Modulo-Operation.

14 \text{ modulo } 12 = 2

Das bedeutet, 14 und 2 drücken für uns dasselbe aus. In der Mathematik sagt man dazu: „14 und 2 sind kongruent Modulo 12.“

Wir haben das Zifferblatt unserer Uhr „überdreht“.

Umgekehrt, wir können wir die Uhrzeit auch rückwärts rechnen. Wenn unser Bekannter um 02:00 Uhr gegangen ist, nachdem er 3 Stunden bei uns war, können wir zurückrechnen und kommen auf 11:00 Uhr.

Über- und Unterläufe ganzer Zahlen

Der Wertebereich unserer ganzzahligen Datentypen entspricht quasi dem Zifferblatt der obigen Uhr-Visualisierung. Je nach Datentyp ist dieses „Zifferblatt“ unterschiedlich groß. Für den Java-Datentyp int hat es beispielsweise 2^32 Einheiten, von (-2)^{31} bis (+2)^{31}. Was passiert nun, wenn wir dieses Zifferblatt überdrehen?

Betrachten wir zur Beantwortung dieser Frage die entsprechenden Bitmuster.

01111111111111111111111111111111  ( 2147483647)
00000000000000000000000000000001  (          1)
-----------------------------------------------
10000000000000000000000000000000  (-2147483648)

Wir können die Resultate leicht mit unseren soeben implementierten Werkzeugen überprüfen.

Wir stellen in jedem Fall fest, dass sich der untersuchte int-Datentyp beim „Überdrehen“ ganz analog zur Uhr verhält, die wir betrachtet haben. Das nennen wir einen Überlauf. Bei einem Überlauf wird die obere Grenze des Wertebereichs überschritten. Ein Unterlauf unterschreitet die untere Wertgrenze eines Wertebereichs.

Damit erklärt sich auch das Verhalten von Integer.parseUnsignedInt(). Die Methode parseUnsignedInt() interpretiert die Textdarstellung als vorzeichenlosen Wert im Bereich 0 bis 2^{32}-1, liefert aber ein int. Integer.MAX_VALUE beträgt 2147483647 und hat das Bit-Muster 01111111111111111111111111111111. Die Methode liefert dieses 32-Bit-Muster als int zurück. Nach der Zweierkomplement-Darstellung von int repräsentiert dasselbe Bitmuster einen negativen Wert. Damit ist das scheinbare Paradoxon von Integer.parseUnsignedInt() gelöst.

Nun können wir das Ganze dahingehend weiter denken, indem wir mehrfach „überdrehen“. Wie spät ist es beispielsweise, wenn wir an einem Ort um 10:00 Uhr ankommen und 40 Stunden verweilen. Dann rechnen wir:

(10 + 40) \text{ modulo } 12 = 50 \text{ modulo 12} = 2

Wir reisen dann um 02:00 Uhr (in der Nacht) des Abreisetages ab. 50 und 2 sind folglich kongruent zu Modulo 12, genau wie die 14. Es gibt also zu einer Zahl verschiedene andere Zahlen, die Modulo 12 kongruent zueinander sind. Das kann man sich am Beispiel visualisieren.

Kongruenzen zu Modulo 12

Kongruenzen zu Modulo 12
Abbildung 2

Alle grün gekennzeichneten Werte sind kongruent zueinander bezüglich 12. Den Zahlenstrahl können sie natürlich beliebig erweitern.

Für sehr große Zahlen ist es müßig, Kongruenzen per Hand bestimmen zu wollen. Schreiben wir also ein Programm, welches uns die Arbeit erleichtert. Dieses Mal verwenden wir Python als Programmiersprache. Python rechnet in Bezug auf ganze Zahlen mit einer sogenannten Langzahl-Arithmetik. Dadurch ist Python nicht an die Wertebereiche gebunden, die beispielsweise den Ganzzahltypen von Java obliegen. Insbesondere stellt auch die Bit-Breite des Prozessors keine Einschränkung dar. D.h., wir können unser Anliegen sehr viel einfacher mit Python als mit Java umsetzen. Bei Java müssten wir dazu die Klasse BigInteger bemühen, die ebenfalls Langzahl-Arithmetik implementiert, jedoch unbequemer zu nutzen ist.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Kongruenzprüfung zweier Zahlen a und b zum Modulo m.

Aufrufkonvention: Congruent.py a b m   
"""


import sys

def congruent(a: int, b: int, m: int) -> bool:
    """
    Prüft, ob die Zahlen a und b kongruent zu
    Modulo m sind. Wenn ja, wird True zurück
    geliefert, ansonsten False.

    :param a: erste Zahl
    :param b: zweite Zahl
    :param m: Modulo
    :return: True oder False
    """
    return a % m == b % m


a: int = int(sys.argv[1])
b: int = int(sys.argv[2])
m: int = int(sys.argv[3])

print(congruent(a, b, m))

Mit diesem Programm können wir nun die Ergebnisse der Fakultätsberechnungen von Java und Python vergleichen. Der Modulo für 32-Bit-Werte beträgt 2^{32} = 4294967296.

$ python3 Congruent.py -2102132736 2432902008176640000 4294967296   
$ _
True

Die Fakultät von 20, die Java berechnet ist also gar nicht mal so falsch. Bei jeder int-Operation bleiben nur die unteren 32 Bits des mathematischen Ergebnisses erhalten. Deshalb entspricht das von Java berechnete Ergebnis dem korrekten Fakultätswert modulo 2^{32}.

Anmerkungen zur Implementierung

  • Will man das Programm Congruent.py in Java implementieren ist die Klasse BigInteger für Langzahlarithmetik zu verwenden.
  • Die im Python-Code gezeigte Modulo-Operation weicht von der in Java implementierten Modulo-Arithmetik des %-Operators ab. In Java ist stattdessen Math.floorMod() zu verwenden (siehe auch Modulo.java).

Vermeidung von Über- und Unterläufen

Im Folgenden gehe ich lediglich auf die Programmiersprache Java ein. Pythons eingebauter Ganzzahltyp int kennt aufgrund seiner Langzahlarithmetik dieses Problem nicht. Bei anderen Programmiersprachen als Java gibt es in der Regel Analogien zu den hier vorgestellten Lösungsansätzen.

Java-Standardlösung

Wenn Ihnen die Nutzung von BigInteger zu aufwendig ist, Sie vor allem aber gar nicht über den Wertebereich von int oder long hinaus rechnen wollen, sind Sie vor einem Über- oder Unterlauf am sichersten, wenn Sie die Math.*Exact-Methodenfamilie nutzen, die seit Java 8 integriert ist. Das sind:

  • Math.addExact()
  • Math.subtractExact()
  • Math.multiplyExact()
  • Math.incrementExact()
  • Math.decrement()
  • Math.negateExact() und
  • Math.toIntExact()

Diese Methoden führen die mathematische Operation durch und werfen sofort eine ArithmeticException, wenn das Ergebnis den Wertebereich des Datentyps überschreitet.

int x = 2147483647 + 1;                // -> x = -2147483648
int x = Math.addExact(2147483647, 1);  // -> ArithmeticException

Der Ausweich-Trick: Nächsthöheren Datentyp nutzen

Wenn Sie int-Werte prüfen möchten, können Sie die Berechnung in den größeren Datentyp long umwandeln. Nach der Berechnung prüfen Sie, ob das Ergebnis noch in einen int passt.

int a = 2_000_000_000;
int b = 2_000_000_000;

long testResult = (long) a + b;

if (testResult > Integer.MAX_VALUE || testResult < Integer.MIN_VALUE) {
    System.out.println("Ergebnis außerhalb des int-Wertebereichs!");
} else {
    int result = (int) testResult;
}

Achtung: Beachten Sie die Codezeile long testResult = (long) a + b;. Ohne den Typecast (long) führt Java die Addition als int-Addition durch, was im konkreten Beispiel einen Überlauf bewirken würde, weil die Typ-Konvertierung dann zu spät kommt..

Diese Methode funktioniert logischerweise maximal für int, da es für long keinen standardmäßigen, noch größeren primitiven Ganzzahltyp in Java gibt.

Die unendliche Lösung: BigInteger

BigInteger besitzt keinen festen, durch den Datentyp vorgegebenen Wertebereich. Seine praktische Größe wird durch den verfügbaren Speicher begrenzt. Wenn Ihre Operanden die Grenzen von int oder long sprengen, ist dies der sicherste Weg. Damit realisieren Sie Langzahl-Arithmetik à la Python.

import java.math.BigInteger;

public class BigFaculty {

    public static BigInteger faculty(int x) {
        BigInteger f = new BigInteger("1");

        while (x > 0) {
            f = f.multiply(BigInteger.valueOf(x));
            x--;
        }
        return f;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.printf("%2d! = %d%n", n, faculty(n));
    }
}

Zum Vergleich mit Python:

$ ./faculty.sh
JAVA AUSGABE                             | PYTHON AUSGABE
-----------------------------------------+----------------------------------------
 1! = 1                                  |  1! = 1                                 
 2! = 2                                  |  2! = 2                                 
 3! = 6                                  |  3! = 6                                 
 4! = 24                                 |  4! = 24                                
 5! = 120                                |  5! = 120                               
 6! = 720                                |  6! = 720                               
 7! = 5040                               |  7! = 5040                              
 8! = 40320                              |  8! = 40320                             
 9! = 362880                             |  9! = 362880                            
10! = 3628800                            | 10! = 3628800                           
11! = 39916800                           | 11! = 39916800                          
12! = 479001600                          | 12! = 479001600                         
13! = 6227020800                         | 13! = 6227020800                        
14! = 87178291200                        | 14! = 87178291200                       
15! = 1307674368000                      | 15! = 1307674368000                     
16! = 20922789888000                     | 16! = 20922789888000                    
17! = 355687428096000                    | 17! = 355687428096000                   
18! = 6402373705728000                   | 18! = 6402373705728000                  
19! = 121645100408832000                 | 19! = 121645100408832000                
20! = 2432902008176640000                | 20! = 2432902008176640000               
21! = 51090942171709440000               | 21! = 51090942171709440000              
22! = 1124000727777607680000             | 22! = 1124000727777607680000            
23! = 25852016738884976640000            | 23! = 25852016738884976640000           
24! = 620448401733239439360000           | 24! = 620448401733239439360000          
25! = 15511210043330985984000000         | 25! = 15511210043330985984000000        
26! = 403291461126605635584000000        | 26! = 403291461126605635584000000       
27! = 10888869450418352160768000000      | 27! = 10888869450418352160768000000     
28! = 304888344611713860501504000000     | 28! = 304888344611713860501504000000    
29! = 8841761993739701954543616000000    | 29! = 8841761993739701954543616000000   
30! = 265252859812191058636308480000000  | 30! = 265252859812191058636308480000000 
$ _

Das Shell-Skript habe ich dahingehend geändert, nun die Java-Klasse BigFacultyzu verwenden und die Fakultätsberechnung auf 30! auszuweiten.

Fazit

Unsere Experimente haben uns etliches über die Abbildung von ganzen Zahlen im Computer gelehrt. Wir wissen jetzt, wie sie kodiert werden, und können vermeintliche Rechenfehler durch Über- oder Unterläufe erklären. Dank Modulo-Arithmetik sind wir auch in der Lage, diese Über- und Unterläufe zu verifizieren. Und last but not least haben wir Alternativen erarbeitet, mit denen wir uns vor unerwarteten Über-/Unterläufen schützen können.

Zudem haben wir für den alltäglichen Gebrauch einfache Werkzeuge implementiert, die zwar nur prototypisch entwickelt sind, für den Eigenbedarf aber ausreichen.