Grenzen für int-Zahlen

Kevintosh

Hallo liebe Community,

ich habe bereits Programmiererfahrungen mit anderen Sprachen. Aber die Problematik der Ganzzahlgrenzen fand bisher wenig Beachtung in dem Lehrmaterial, was ich mir zum Erlernen dieser Sprachen zugelegt hatte, zumindest nicht so tiefgründig wie in dem C++-Buch. Und dabei waren es nicht einmal Wurstbrotbücher.

Ich hatte mich nach einiger Recherche für das Buch "Der C++ Programmierer" entschieden. Eine der ersten Aufgaben in diesem Buch war es, die Grenzen für int, long int, unsigned int & unsigned long int ohne Benutzung der limits.h zu finden. Da das Buch zwar Lösungen, aber keine Erklärung zu diesen hat, wollte ich hier mal meinen Erklärungsversuch für die Lösung posten und von euch wissen, ob dieser korrekt ist. Ich möchte es ja schließlich auch verstehen und nicht nur abschreiben.

Die mitgelieferte Lösung zur Aufgabe:

#include<iostream>
using namespace std;
int main() {
unsigned int ui {};
unsigned long int uli {};
cout << "max. unsigned int= " << ~ui << endl;
cout << "max. unsigned long int= " << ~uli << endl;
cout << "max. int = "<< (~ui>>1) << endl;
cout << "max. long int = "<< (~uli>>1) << endl;
}

Mein Erklärungsversuch:
Es wird je eine Variable vom entsprechenden Datentyp mit dem Wert 0 deklariert.
Und das jeweils in der unsigned Variante, da so die größtmögliche Anzahl an Bits für die Darstellung der Zahl zur Verfügung steht. Da den Variablen der Wert 0 zugewiesen wurde, sind alle Bits 0 (keine Ahnung ob man das so formulieren kann, aber ich denke ihr wisst, was ich meine). Durch die dann vorgenommene bitweise Negation sind alle Bits 1, was der größtmöglichen Zahl entspricht. Bei den unsigned Varianten wird ein Bitshift um 1 nach Rechts vorgenommen und von Rechts mit Nullen aufgefüllt. Das heißt, dass das Bit was zur Darstellung des Vorzeichens benötigt wird 0 ist und somit nicht zur Darstellung der Zahl beiträgt. Die restlich-verbleibenden Bits sind alle 1 und man erhält die maximal darstellbare Zahl bei der Beachtung von Vorzeichen.

So nun würde ich mich freuen, wenn ihr mich verbessert oder sagt, dass es so stimmt. Wäre super nett und hilfreich.

Ist im C++-Standard eigentlich garantiert dass die nativen Datentypen binär im Speicher liegen? Es ist ja eigentlich jede Permutation der Reihenfolge der Binärmuster möglich.

icarus2

Nehmen wir an, dass ein int aus 4 Bits besteht (ein int ist in C++ mindestens 16 Bits gross aber ich mag nicht so viele Zeichen tippen ;)).

Die grösste unsigned Zahl mit 4 Bits ist 1111. Die grösste signed Zahl (in Two's Complement) ist 0111.

unsigned int ui {}; // ui == 0000
cout << "max. unsigned int= " << ~ui << endl; // ~ui == 1111
cout << "max. int = "<< (~ui>>1) << endl; // ~ui>>1 == 0111

Bei ~ui>>1 handelt es sich um einen Rechts-Shift. Ein Rechts-Shift schiebt um n (hier n = 1 ) Bits nach rechts. Dabei fallen auf der rechten Seite n Bits weg und links wird bei unsigned Zahlen mit n Nullen aufgefüllt.

Swordfish

icarus2 schrieb:

[...] (ein int ist in C++ mindestens 16 Bits gross [...]

Wo steht das?

icarus2

Swordfish schrieb:

icarus2 schrieb:

[...] (ein int ist in C++ mindestens 16 Bits gross [...]

Wo steht das?

Im C++ Stanadard, Seite 21 und 22.

Columbo

unsigned int ui {};

Bitte diesen Unsinn unterlassen. = 0 hätte es auch getan und wäre noch Zig mal schneller gelesen worden.

icarus schrieb:

Nehmen wir an, dass ein int aus 4 Bits besteht

... was im Übrigen natürlich laut Standard untersagt ist

Ist im C++-Standard eigentlich garantiert dass die nativen Datentypen binär im Speicher liegen?

Ja.

§3.9.1/7 schrieb:

The representations of integral types shall define values by use of a pure binary numeration system.
[Fußnote:]
A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position. (Adapted from the American National Dictionary for Information Processing Systems.)

this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types.

icarus2

Arcoth schrieb:

icarus schrieb:

Nehmen wir an, dass ein int aus 4 Bits besteht

... was im Übrigen natürlich laut Standard untersagt ist

Deswegen sollte man auch lesen was in Klammern geschrieben steht

SeppJ

Clown Heinz schrieb:

Ist im C++-Standard eigentlich garantiert dass die nativen Datentypen binär im Speicher liegen? Es ist ja eigentlich jede Permutation der Reihenfolge der Binärmuster möglich.

Jain, die abstrakte Maschine von C++ ist sehr, nun ja, abstrakt. Da wird so gut wie gar nichts vorgegeben. Konkrete Vorgabe ist hier zwar schon, dass die interne Darstellung sich so verhält wie eine bitweise Zifferndarstellung (wobei es der Implementierung freisteht, welche genau gewählt wird. Es gibt da nämlich mehrere Möglichkeiten. Stichworte: Einer-Komplement, Zweier-Komplement. Aber auch andere). Ein standardkonformes C++-Programm kann aber problemlos auf einem wassergetriebenen Analogrechner aus Bambusrohren laufen, es muss sich nur so verhalten wie die beschriebene abstrakte Maschine.

Zu den Fragen des Threaderstellers:

Es wird je eine Variable vom entsprechenden Datentyp mit dem Wert 0 deklariert.
Und das jeweils in der unsigned Variante, da so die größtmögliche Anzahl an Bits für die Darstellung der Zahl zur Verfügung steht.

Vermutlich eher, zumindest hoffe ich das, weil sonst nicht unbedingt das gewünscht Ergebnis heraus käme. Denn ~0 (0 ist ein signed int) kann auch -1 sein, wenn die Implementierung beispielsweise das Zweierkomplement benutzt (und das tun fast alle).

Da den Variablen der Wert 0 zugewiesen wurde, sind alle Bits 0 (keine Ahnung ob man das so formulieren kann, aber ich denke ihr wisst, was ich meine). Durch die dann vorgenommene bitweise Negation sind alle Bits 1, was der größtmöglichen Zahl entspricht.

Korrekt.

Bei den unsigned Varianten wird ein Bitshift um 1 nach Rechts vorgenommen und von Rechts mit Nullen aufgefüllt.

Von links wird aufgefüllt, da ja nach rechts geschoben wird, aber das ist sicher auch das, was du meinst.

Das heißt, dass das Bit was zur Darstellung des Vorzeichens benötigt wird 0 ist und somit nicht zur Darstellung der Zahl beiträgt. Die restlich-verbleibenden Bits sind alle 1 und man erhält die maximal darstellbare Zahl bei der Beachtung von Vorzeichen.

Ja. Wobei man hier quasi ein bisschen Glück hat, dass in allen üblichen und unüblichen Repräsentationen von vorzeichenbehafteten Zahlen die größte Zahl stets die Bitrepräsentation 011…11 hat.

Relevanter Link:
en.wikipedia.org/wiki/Signed_number_representation

Swordfish

icarus2 schrieb:

Swordfish schrieb:

icarus2 schrieb:

[...] (ein int ist in C++ mindestens 16 Bits gross [...]

Wo steht das?

Im C++ Stanadard, Seite 21 und 22.

Das kanns Wertemäßig nicht sein, denn das würde heißen, daß laut UINT_MAX ein unsigned genau 16 Bit breit sein muss ...

Kevintosh

Erstmal: vielen dank für die rasanten Antworten.

Arcoth schrieb:

unsigned int ui {};
Bitte diesen Unsinn unterlassen. = 0 hätte es auch getan und wäre noch Zig mal schneller gelesen worden.

Gut, danke für den Hinweiß, war aber nur aus dem Buch abgeschrieben :p

SeppJ schrieb:

Bei den unsigned Varianten wird ein Bitshift um 1 nach Rechts vorgenommen und von Rechts mit Nullen aufgefüllt.

Von links wird aufgefüllt, da ja nach rechts geschoben wird, aber das ist sicher auch das, was du meinst.

Ups, war wohl ein Kaffee zu viel :p Jap, meinte von links.

Gut, dann scheint mein Verständnis für Angelegenheit ja schon mal ganz ok gewesen zu sein.
Danke für die Hilfe. Echt super!

Schönen Abend noch, wünsch ich.

icarus2

Swordfish schrieb:

icarus2 schrieb:

Swordfish schrieb:

icarus2 schrieb:

[...] (ein int ist in C++ mindestens 16 Bits gross [...]

Wo steht das?

Im C++ Stanadard, Seite 21 und 22.

Das kanns Wertemäßig nicht sein, denn das würde heißen, daß laut UINT_MAX ein unsigned genau 16 Bit breit sein muss ...

Ein unsigned muss mindestens 16 Bits breit sein. Eine konkrete Implementierung darf auch mehr Bits verwenden (steht auf Seite 21 unter 5.2.4.2.1 Sizes f integer types <limits.h>)

Swordfish

Ah, ich hab' "equal or greater in magnitude" überlesen.

SeppJ schrieb:

Kevintosh schrieb:

Das heißt, dass das Bit was zur Darstellung des Vorzeichens benötigt wird 0 ist und somit nicht zur Darstellung der Zahl beiträgt. Die restlich-verbleibenden Bits sind alle 1 und man erhält die maximal darstellbare Zahl bei der Beachtung von Vorzeichen.

Ja. Wobei man hier quasi ein bisschen Glück hat, dass in allen üblichen und unüblichen Repräsentationen von vorzeichenbehafteten Zahlen die größte Zahl stets die Bitrepräsentation 011…11 hat.

Ist denn im Standard definiert, dass beim Rechtsshift eine 0 eingeschoben wird (logical shift).
Oder kann auch das Vorzeichen kopiert werden (arithmetic shift)

SG1

Bei unsigned Typen muss eine 0 reingeschoben werden, bei signed Typen ist implementation defined(?) welches von beiden passiert.

Columbo

bei signed Typen ist implementation defined(?) welches von beiden passiert.

Ja, wenn sie negativ sind:

The value of $E1 >> E2$ is $E1$ right-shifted $E2$ bit positions. If $E1$ has an unsigned type or if $E1$ has a signed type and a non-negative value, the value of the result is the integral part of the quotient of $E1/2^{E2}$ .
If $E1$ has a signed type and a negative value, the resulting value is implementation-defined.

SeriousITGuy

Ein elegante Lösung für ein uraltes Problem
Habe das ganze mal nachgestellt und auf short und long long erweitert. Komischerweise liefert mir die Ausgabe für unsigned short und short jeweils -1 als Maximalwert. Verwendeter Compiler: VS2013 Pro, Aufruf cl /EHsc its.cpp

// its.cpp - Integer types maximum numbers
// displays the maximum numbers for integer types
#include <iostream>
using std::cout;
using std::endl;

int main()
{
  unsigned short      us = 0;
  unsigned int        ui = 0;
  unsigned long       ul = 0;
  unsigned long long ull = 0;

  cout << "max unsigned short = " << ~us      << endl;
  cout << "max signed short   = " << (~us>>1) << endl;

  cout << "max unsigned int   = " << ~ui      << endl;
  cout << "max signed int     = " << (~ui>>1) << endl;

  cout << "max unsigned long  = " << ~ul      << endl;
  cout << "max signed long    = " << (~ul>>1) << endl;

  cout << "max unsigned llong = " << ~ull      << endl;
  cout << "max signed llong   = " << (~ull>>1) << endl;
}

Ausgabe:

max unsigned short = -1
max signed short   = -1
max unsigned int   = 4294967295
max signed int     = 2147483647
max unsigned long  = 4294967295
max signed long    = 2147483647
max unsigned llong = 18446744073709551615
max signed llong   = 9223372036854775807

Wie ist das zu erklären? Danke für die Hilfe im vorraus

oenone

Weil es für die Negation automatisch zum nächsthöheren Typ aufgewertet wird, also int. Das ist signed und erhält deshalb ein Minus. Bei char das gleiche. Du musst es also casten: (unsigned short)(~us)

Stichwort: integer promotion

Columbo

§13.6/10 schrieb:

For every promoted integral type T, there exist candidate operator functions of the form
T operator∼(T );

unsigned short gehört nicht zu den promoted integral types. Daher wird dein unsigned short erstmal nach int konvertiert. Der Rest ist selbsterklärend.

Edit: Zu spät :p

SeriousITGuy

oenone schrieb:

Stichwort: integer promotion

Macht Sinn, mit nem Cast hats jetzt geklappt.
Danke für die schnelle Hilfe!