[A]Ring des int

Ben04

Moin,

Ich hab mal wieder ein bischen fürs Magazin geschrieben. Vor langer Zeit hatte ich bereits einmal einen ähnlichen Artikel gepostet, allerdings wesentlich reißerischer formuliert. Zielgruppe sind nach wie vor die Leute welche sich mit algebraischen Grundlagen gar nicht auskennen (was jetzt aber nicht heißt, dass ich die Kommentare anderer Leute nicht schätzen würde). Ziel ist es nicht die Leute darin einzuführen sondern es geht nur darum die grundlegende Theorie auf ints im Rechner anzuwenden, um ein besseres Verständniss für das Verhalten in Grenzfällen zu bekommen.

Ich glaube, dieser Artikel wird kürzer werden als die letzten aber ich glaube, das ist eine gute Sache.

Kommentar sind wie immer willkommen. :xmas1:

Ring des int

In diesem Artikel möchte ich mich mit dem Rechnen mit ints befassen. Es gibt kaum ein Programm welches ohne ints auskommt. Diese Tatsache legt den Verdacht nahe, dass es sich um eines der am besten Verstanden Gebilde in einem Rechner handeln dürfte. Erstaunlicherweise ist dem bei vielen Programmieren aber nicht so.

Viele Leute betrachten ints als Ganzzahlen. Für Werte nahe 0 ist dies auch der Fall, wenn die Werte aber sehr groß oder klein werden dann gibt es sehr deutliche Unterschiede in der Verhaltesweise. Viele Leute betrachten Overflows als Fehler. In meinen Augen handelt es sich eher um ein meistens unerwünschtes und schlecht verstandenes Verhalten.

Obwohl folgendes Programm einen Overflow produziert wird das Ergebniss zu mindest auf geläufigen Rechnern immer 0 sein.

short a = 0;
a += 100000;
a *= 1000;
a -= 100000000;
cout<<a;

Dies liegt daran, dass hier eigentlich kein Fehler vorliegt. Rechnen mit Overflows ist in der Mathematik sehr gut erforscht und verstanden. Von diesem Standpunkt aus ist es kaum erstaunlich, dass man das Ergebniss vorhersagen kann.

Der C++ Standard spezifiziert nicht was bei Overflows passiert, jedoch herrscht bei Mainstreamrechnern einen Quasistandard. Bei n-Bit unsigned-Typen werden nur die n niederwertigsten Bits betrachtet. Alle höheren werden abgeschnitten. Bei signed-Typen werden negative Wert in der Zweierkomplementdarstellung gespeichert.

Wer weiß was das Zweierkomplement ist, der wird sich bestimmt schon mal gefragt haben, warum man eine derart eigenartige und komplizierte Darstellung wählt. Der Grund sind ihre mathematischen Eigenschaften, wie in diesem Aritkel erläutert werden wird.

Wer diese Darstellung bis jetzt nur verwendet hat ohne zu wissen dass man dies so nennt, der sei beruhigt. Man braucht diese Kodierung nicht zu kennen um diesen Artikel zu verstehen. Am Ende des Artikels kennt und versteht man sie eh. Naja, zu mindest fast; Wahrscheinlich wird nicht klar sein wieso die so komisch heißt.

Ehe ich jetzt mit dem eigentlich Stoff beginne möchte ich noch ein kleines Rätzel angeben. Wie viele x gibt es so dass die Bedingung x*4 == 24 erfüllt ist? x ist natürlich ein int und die Zahlen sind int-Literale wie das unter C++-Programmiern üblich ist.

Vom Bitarray zum int

An sich sind ints nichts weiteres als Bitarrays fester Länge. Bei 3 Bits ergeben sich 8 Möglichkeiten: 000, 001, 010, 011, 100, 101, 110 und 111. Vergessen wir mal, dass das auch ints sind und versuchen damit nun Ganzzahlen zu basteln. Dadurch kann man meiner Meinung nach am besten Nachvollziehen warum die Dinge so sind wie sie sind.

Ganzzahlen haben die Eigenschaft, dass man sie alle berechnen kann indem man die 0 nur oft genug inkrementiert oder dekrementiert. Dies klingt erst mal trivial, allerdings reichen diese beide Operationen um das Verhalten der Addition und der Multiplikation fest zu legen und es ist ja nicht Ziel dieses Artikels diese schnell zu machen.

Versuchen wir also ähnliche Operationen auf unseren Bitarrays zu definieren. Zu erst brauchen wir ein Element welches die Rolle der 0 übernimmt. Hier kann man an sich jedes der 8 Elemente wählen jedoch bietet sich die 000 geradezu an. Bei der Wahl der Inkrementierung bin ich auch sehr konservativ obwohl dies an sich nicht notwendig ist. Wichtig ist nur, dass man alle 8 Bitarrays in irgendeiner Reihenfolge erwischt.

Die Inkrementierung wird über folgenden Algorithmus definiert:

bit_array inkrement(bit_array n){
	for(int i=0; i<size(n); ++i){
		if(n[i] == 0){
			n[i] = 1;
			break;
		}else
			n[i] = 0;
	}
	return n;
}

Oder um es bildlich darzustellen:

Bild

Ähnlich lässt sich auch eine Funktion zum Dekrementieren definieren. Diese machte genau das umgekehrte.

Haben wir unser Ziel erreicht eine Struktur auf unseren Bitarrays zu definieren, welche Ganzzahlen ordentlich modeliert? Eigentlich nicht. Wenn wir die "000" 8 mal inkrementieren dann erhalten wir wieder die "000". Wenn man die "0" 8 mal inkrementiert dann kriegt man die "8" und 8 != 0. Haufenweise Zahlen müssen sich ein und das selbe Bitarray teilen.

Unsere Bitarrays representieren also keine Zahl sondern eine ganze Klasse von Zahlen.

Folgendes Bild verdeutlicht welche Zahlen zusammen fallen:

Bildchen

Man könnte nun natürlich versuchen eine bessere Inkrementationsfunktion zu finden welche dieses Problem nicht hat. Dies ist aber nicht möglich, da es nur 8 verschiedene Bitarrays gibt aber unendlich viele Ganzzahlen.

Im folgenden werde ich die Klasse in welche eine Ganzzahl fällt mit [] notieren. Es gilt also zum Beispiel: [3] = [11] = [-5] = {..., -13, -5, 3, 11, 19, ...}. Das Bitarray 101 würde die Klasse [5] representieren.

Repräsentanten oder wie entstehen negative ints

Viele Leser dürften an diesem Punkt zu recht verwundert sein warum folgendes Programm 3 ausgibt.

int x = 3;
cout << x;

Ein int ist ja eine Klasse von Zahlen. Dieses x speichert nicht 3 sondern [3]. Ziel ist es den Benutzer in die Irre zu führen und ihm vor zu gauckeln, dass man in der Tat mit ganzen Zahlen rechnen könnte.

Ein Element einer Klasse nennt man Repräsentanten.

Per Konvention legt man für jede Klasse einen Repräsentanten fest, welcher für diese Klasse steht und bei der Ein- und Ausgabe als Darstellung verwendet wird. Man legt also fest, dass bei [3] die 3 ausgegeben wird und nicht etwa die 11, obwohl bei 3 Bit gilt, dass [3] = [11].

Im Allgemeinen nimmt man für einen unsigned-n-Bit-int die Repräsentanten x für die gilt 0 <= x < 2^n. Man könnte aber genau so gut definieren, dass man die x wählt so dass 42 <= x < 42 + 2^n gilt. Das Rechnen wird dadurch nicht richtiger oder falscher denn die Klassen selbst juckt die Wahl nicht.

Es dürfte nun auch klar werden, wie man negative Zahlen darstellt. Man legt für die einfach eine andere Konvention fest welche auch negative Repräsentanten benutzt. Im Allgemeinen wählt man -2^(n-1) <= x < 2^(n-1). Welchen Repräsentanten man für [2^(n-1)] wählt ist an sich egal. Normallerwese wählt man den negativen, damit man durch das anschauen des höchstwertigen Bits herrausfinden kann ob eine Zahl negativ ist.

Dadurch, dass man die negativen Zahlen auf diese Weise definiert erspart man dem Prozessor sehr viel Arbeit da er nicht mehr auf Vorzeichen aufpassen muss. Er braucht gar nicht mal zu wissen ob es sich bei zwei Bitarrays um signed oder unsigned ints handelt, er rechnet eh gleich. Die Unterscheidung zwischen int und unsigned findet fast vollständig im Compiler und in den Ein- und Ausgabefunktionen statt.

Diese sich durch diese Wahl der Repräsentanten ergebende Kodierung für ints nennt man Zweierkomplementdarstellung.

Als ich die Wahl des Repräsentanten von [2^(n-1)] gerechtfertigt haben dürften einige Leser stuzig geworden sein. Wenn die Wahl für das Rechnen keinen Unterschied macht, warum macht es dann bei der Frage ob ein int negativ ist? Das Problem liegt daran, dass "negativ" als kleiner als 0 definiert ist. "kleiner als" lässt sich allerdings im Gegensatz zu den meisten Operationen nur sehr schlecht auf diese Klassen übertragen. Aber dazu mehr in einem eigenen Abschnitt.

Addition/Substraktion/Multiplikation

Schauen wir uns mal die Klassen etwas genauer an. Zum Beispiel die Klasse [3] bei unserem 3-Bit-int Beispiel.

[3] = {..., -13, -5, 3, 11, 19, ...}

so kann man alle weiteren Elemente durch x+8*k berechnen indem man für k jede ganze Zahl einsetzt.

Diese Beobachtung kann man ausnutzen um die meisten Gleichungen zwischen Klassen auf Gleichungen zwischen Ganzzahlen zurück zu führen. Mit Ganzzahlen lässt sich im Allgemeinen für uns Menschen leichter rechnen. Zum Beispiel für welche x gilt:

= [42]

Direkt kann man da eigentlich keine Aussage machen. Wenn man allerdings ein bischen umformt erhält man:

3 + x = 42 + 8*k

wobei k eine beliebige ganze Zahl ist. Dadurch, dass man die 3 noch auf die andere Seite nimmt erhält man die Lösung.

x = 39 + 8*k

Für jedes k gibt es ein x. Es gibt also unendlich viele x welche die Gleichung erfüllen. Das klingt im ersten Moment als wenn das Ergebniss für eine Gleichung welche aus ints besteht gar nicht stimmen könnte. Es stellt sich aber herraus, dass die Menge aller möglichen x genau eine Klasse bilden. Die Lösung ist also [39] = [7].

+ [y] = [x+y] für alle x und y gilt. Im Klartext bedeutet das nur, dass es egal ist ob man die Ganzzahlen addiert oder die Klassen. Das Ergebniss ist eh das selbe. Ähnliches gilt auch für die Substraktion und die Multiplikation: [x] - [y] = [x-y] und [x] * [y] = [x*y].

Eine Konsequenz daraus ist, dass jede Gleichung zwischen Ganzzahlen welche nur aus +, - und * besteht auch für ints gilt. Als Beispiel nehme ich mal die Formel des kleinen Gaus:

2*(1 + 2 + 3 + 4 + ... + n) = n * (n+1)

Ich habe die Formel mit 2 durchmultipliziert da teilen bei ints ein wenig problematisch ist, aber dazu später mehr.

Es ist klar, dass daraus folgt, dass auch die Klassen gleich sind

[2*(1 + 2 + 3 + 4 + ... + n)] = [n * (n+1)]

* [y] = [x*y] gilt:

[2]*[1 + 2 + 3 + 4 + ... + n] = [n] * [n+1]

+ [y] = [x+y]:

[2]*([1] + [2] + [3] + [4] + ... + [n]) = [n] * ([n]+[1])

Ich will anhand des folgenden Programmschnippsels verdeutlichen was dies bedeutet.

unsigned doppelte_sum_der_n_ersten_zahlen(unsigned n){
	unsigned summe = 0;
	for(unsigned i=0; i<n; ++i)
		summe += i;
	return 2*summe;
}
//...
for(unsigned n=0; n!=(unsigned)-1; ++n)
	if(doppelte_sum_der_n_ersten_zahlen(n) != n * (n+1))
		cout<<"Mich sieht keiner :clown:"<<endl;

-1 und die größte als unsigned int darstellbare Zahl bilden eine Klasse. Deswegen funktioniert der Cast nach unsigned.

Wenn man ints als Ganzzahlen mit beschränkter Genauigkeit betrachtet, dann ist es sehr erstaunlich, dass diese Gleichung trotz Overflows hält. Sobald man allerdings daran denkt, dass hier ja eigentlich Klassen von Ganzzahlen im Spiel sind, dann wird das Verhalt vorhersehbar.

Genaue Division

In der Einleitung hatte ich gefragt für welche x die Bedingung x*4 == 24 erfüllt sei. Da ich die Frage da für normale ints gestellt habe und dies in der Regel 32 Bit ints bedeutet, werde ich sie jetzt auch für die beantworten. Zuerst schreibe ich es mal in halbwegs mathematisch korrekter Form hin:

* [4] = [24]

Nun könnte man dazu neigen einfach durch 4 teilen zu wollen. Bei Ganzzahlen geht das auch und von daher ist das hier auch nicht falsch, wie ich bereits im Abschnitt vorher versucht habe klar zu machen. Man erhält aber nicht alle [n]. [n] = [6] ist nicht die einzige Lösung!.

Packen wir die Gleichung mal ein bischen anders an:

x * 4 = 24 + k*2^32

Nun teile ich durch 4 und zwar alle Terme und zwar auch den k*2^32 Term.

x = 6 + k*2^30

Für k = ...,-4, 0, 4,... erhält man für x sämtliche Zahlen der Klasse [6]. Da k aber nicht auf die Vielfache von 4 beschränkt ist gibt es noch weitere Lösungen.

Für k = ...,-3, 1, 5,... ergibt sich x aus [6 + 12^30] = [1073741830].
Für k = ...,-2, 2, 4,... ergibt sich x aus [6 + 22^30] = [2147483654] = [-2147483642].
Für k = ...,-1, 3, 5,... ergibt sich x aus [6 + 3*2^30] = [3221225478] = [-1073741818].

Eine Klasse ist eine Lösung wenn es für alle Elemente in ihr ein k gibt, so dass x dieses Element ist. Da wir offensichtlich alle möglichen k abdecken kann es auch keine weitere Lösungen geben.

Ich bin mir sicher, dass einigen Lesern nicht klar sein dürfte was dies bedeutet. Folgendes Programm dürfte diesen Leuten helfen.

#include <iostream>
using namespace std;

void cond(int x){
	cout<< x << " * 4 == 24 is ";
	if(x*4 == 24)
		cout << "true." << endl;
	else
		cout << "false." << endl;
}

int main(){
	// Folgendes ist klar
	cond(6);
	cond(5);

	// Ab hier dürften ein paar Leute staunen
	cond(1073741830);
	cond(-2147483642);
	cond(-1073741818);
}

Für die die zu faul sind das Programm auszuführen gebe ich hier mal die von mir erwartete Ausgabe an:

64 == 24 is true.
54 == 24 is false.
10737418304 == 24 is true.
-21474836424 == 24 is true.
-1073741818*4 == 24 is true.

Wenn man nun eine belibige Anzahl zulässt erhält man fast immer 4 Lösungen wovon 3 Stück von der Anzahl der Bits abhängen. Nur beim Fall wo es nur 1 Bit gibt, gibt es nur 2 Lösungen. In dem Fall gibt es nur 2 ints, nämlich [0] und [1]. Es ist klar, dass man dann keine 4 Lösungen finden kann.

Bemerckenswert ist auch der Fall von zwei Bits. Hier gilt [4] = [0]. Es handelt sich also um eine Multiplikation mit 0 also ist jedes x eine Lösung da x*0 = 0. Es gibt hier aber nur 4 Klassen und passt es doch.

- Bit Shifts
- Teilen

Vergleiche

- endliche Menge kann man nicht anordnen. n < n+1 hält nie für <1> endlich.
- x86 signed und unsigned Unterscheidung

bgdnoy

Ich finde, daß das ein guter Artikel werden wird. Es recht einfach, die Dinge so zu sagen, daß sie kein Mensch versteht, aber viel schwieriger, die Dinge so sagen, daß sie jeder Maurer verstehen muß (nichts gegen die Maurer -- bin selber irgendwie einer). Und das ist dir gut gelungen. Fertigmachen!

Weil nach einem halben Jahr keine Antworten gekommen sind, bin ich mal so frei, zu kritisieren:

inkrementiert oder dekrementiert

Wegen der Zielgruppe schlage ich vor, dazuzusagen, daß das "Erhöhen/Erniedrigen um 1" heißt.

0 <= x < 2^n

Aus dem gleichen Grund würde ich klarstellen, daß ^ für "hoch" steht.

Obwohl noch nicht [R], ein paar Tippfehler, die mir aufgefallen sind:

Rätzel -> Rätsel
am besten Nachvollziehen -> am besten nachvollziehen
stuzig -> stutzig
wird das Verhalt vorhersehbar -> Verhalten
Bemerckenswert -> Bemerkenswert

Hier und da würde ich noch über Beistriche nachdenken, aber dazu ist es noch zu früh.

So, ich war penibel, aber nicht weil ich dich ärgern will, sondern damit hier wieder ein bißchen Leben einkehrt. Vielleicht willst du ja später meine Artikel gegenlesen...