Größte darstellbare Zahl

xxyy

Hi Leute,

ich bin dabei ein Programm zu schreiben, das mir Fibonacci Zahlen berechnet.
Das "Hauptprogramm" habe ich geschafft.
Jedoch soll ich bei dem Programm die größte darstellbare Zahl bei dem verwendeten Datentyp beachten und es soll eine Fehlermeldung ausgegeben werden, wenn diese "zu groß" ist.

Das hat etwas mit dem sizeof Operator zu tun, oder? Habe mit ihm noch nie so gearbeitet bzw. so einen Aufgabentyp.

Mein Fibonacci Programm sieht so aus:

C

#include <stdio.h>
#include <limits.h>






int main(void) {
    unsigned int zahl;


    printf("Bitte eine positive ganze Zahl eingeben: ");
    scanf("%d", &zahl);
    printf("Die %d. Fibonaccizahl ist %ld\n",
       zahl, fibonacci(zahl));
    return 0;
}

Alles anzeigen

Wie mache ich das mit der "größten darstellbaren" Zahl?

Vielen Dank!!

hal

Bei unsigned ist die groesste Zahl 2^(anzahl der Bits), also zB bei 64bit-Werten 2^64. Bei signed muss man ein Bit abziehen, weil das für das sign verwendet wird.

sizeof() liefert dir die Größe in Bytes, d.h. du musst nur noch mit 8 multiplizieren, um die Größe in Bits zu bekommen.

Irrlicht

oder du machst es einfach so wie das C++ vorgesehen hat und nimmst

Code

numeric_limits<deinDatenTyp>::max()

MaxAuthority

Zitat von hal

Bei unsigned ist die groesste Zahl 2^(anzahl der Bits), also zB bei 64bit-Werten 2^64. Bei signed muss man ein Bit abziehen, weil das für das sign verwendet wird.

<nitpick_mode>
Und bei unsigned muss man -1 anbziehen, also 2^64 -1, da man ja bei 0 anfaengt zu zaehlen
</nitpick_mode>

Irrlicht: leider halt nicht portable (auf C), aber sehr cool zu wissen, wieder was dazugelernt, danke.

xxyy

Danke euch für die Antworten.

Ein unsigned int hat ja 2 Bytes, 16 Bits. Also von 0...65535.
Was mich grad verwirrt ist, dass wenn ich mein Programm laufen lasse und eingebe, dass mir die 30. angezeigt werden soll, dann kommt 832040.
Wo liegt mein Denkfehler??

Und die Abfrage kann ich dann so machen?

Code

if (sizeof(zahl)>16)
{
printf("Nicht darstellbar");
}

Paulchen

Zitat von xxyy
Und die Abfrage kann ich dann so machen?
Code
if (sizeof(zahl)>16)
{
printf("Nicht darstellbar");
}

sizeof(zahl) ist, solange du auf derselben Architektur bei demselben Compiler bleibst, eine Konstante und gibt immer an, wie viele Bytes notwendig sind, um einen beliebigen Wert des Typs von zahl zu speichern.

jeuneS2

Zitat von xxyy

Ein unsigned int hat ja 2 Bytes, 16 Bits. Also von 0...65535.

Kommt auf den Prozessor an; auf neueren x86-Systemen ist int, also auch unsigned int 32 bit breit. Die Breite in Bits eines bestimmten Typs bekommt man mittels "sizeof(typ)*BITS_PER_BYTE".

xxyy

Ich habe mal ausgeben lassen:

Code

printf("%d",sizeof(zahl));

Und da kommt immer 4 raus, d.h. dass unsigned int 4 Bytes hat? Hab gedacht 2 (laut meiner Tabelle).

Wie kann man dann die Bits bzw. Bytes des Ergebnisses bestimmen um zu "sagen" es werden mehr benötigt ?

hal

Interessante Tabelle, das ist nämlich überhaupt nicht standardisiert. Das einzige was fix ist ist, dass "int" der Bitbreite des Prozessors entspricht (also 8bit bei einem 8bit-Prozessor, 16bit auf einem 16bit-Prozessor, 32bit bei einem 32bit-Prozessor und 64bit bei einem 64bit-Prozessor), und dass char die kleinste addressierbare Einheit (üblicherweise 1 Byte) ist.
Die Tabelle kann also nur für genau einen Compiler auf genau einer Plattform sein, was vermutlich nicht deiner Plattform entspricht.

Das höchste Bit einer Zahl kannst du bestimmen, indem du eine Schleife machst:

Code

for(unsigned int i = sizeof(zahl)*8; i; i--)
  if(zahl & (1 << i)) {
    printf("Höhstes Bit ist %u\n",i);
    break;
  }

Oder so in der Art (könnte wieder einen off by one-Fehler enthalten, um sowas zu kontrollieren bin ich nimmer nüchtern genug ;)).

xxyy

Zitat von hal
Interessante Tabelle, das ist nämlich überhaupt nicht standardisiert. Das einzige was fix ist ist, dass "int" der Bitbreite des Prozessors entspricht (also 8bit bei einem 8bit-Prozessor, 16bit auf einem 16bit-Prozessor, 32bit bei einem 32bit-Prozessor und 64bit bei einem 64bit-Prozessor), und dass char die kleinste addressierbare Einheit (üblicherweise 1 Byte) ist.
Die Tabelle kann also nur für genau einen Compiler auf genau einer Plattform sein, was vermutlich nicht deiner Plattform entspricht.

Das höchste Bit einer Zahl kannst du bestimmen, indem du eine Schleife machst:
Code
for(unsigned int i = sizeof(zahl)*8; i; i--)
  if(zahl & (1 << i)) {
    printf("Höhstes Bit ist %u\n",i);
    break;
  }
Oder so in der Art (könnte wieder einen off by one-Fehler enthalten, um sowas zu kontrollieren bin ich nimmer nüchtern genug ;)).

Danke, dass du dich da noch gequält hast *g*

Die Tabelle bzw. Info habe ich aus dem Pronix C Tutorial.

Ich habe die for-Schleife vor das return 0 eingebaut und es kamen folgende Meldungen.

Code

\fibo.c(15) : warning C4996: 'scanf' wurde als veraltet deklariert
        c:\programme\microsoft visual studio 8\vc\include\stdio.h(295): Siehe Deklaration von 'scanf'
        Meldung: "This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_DEPRECATE. See online help for details."
\fibo.c(19) : error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
\fibo.c(19) : error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
\fibo.c(19) : error C2143: Syntaxfehler: Es fehlt ')' vor 'Typ'
\fibo.c(19) : error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
\fibo.c(19) : error C2065: 'i': nichtdeklarierter Bezeichner
\fibo.c(19) : error C2143: Syntaxfehler: Es fehlt ';' vor ')'
\fibo.c(22) : error C2043: Schlüsselwort 'break' ungültig
\fibo.c(24) : error C2059: Syntaxfehler: 'return'
fibo.c(25) : error C2059: Syntaxfehler: '}'

Alles anzeigen

Kann man die Bedingung "i" einfach alleine stehen lassen?

Paulchen

Zitat von hal

Interessante Tabelle, das ist nämlich überhaupt nicht standardisiert. Das einzige was fix ist ist, dass "int" der Bitbreite des Prozessors entspricht (also 8bit bei einem 8bit-Prozessor, 16bit auf einem 16bit-Prozessor, 32bit bei einem 32bit-Prozessor und 64bit bei einem 64bit-Prozessor), und dass char die kleinste addressierbare Einheit (üblicherweise 1 Byte) ist.

Hm, auf meinem Pentium 4 (bekanntlich ein 32-Bit-Prozessor) stimmt das, da ist int vier Bytes lang, genauso wie long (laut sizeof).

Interessanterweise ist auf b1.complang.tuwien.ac.at (ein DEC Alpha, wenn ich nicht ganz blöd bin ein 64-Bit-Prozessor) ein int ebenfalls vier Bytes lang und nur ein long hat acht Bytes.

jeuneS2

Zitat von hal

Interessante Tabelle, das ist nämlich überhaupt nicht standardisiert. Das einzige was fix ist ist, dass "int" der Bitbreite des Prozessors entspricht (also 8bit bei einem 8bit-Prozessor, 16bit auf einem 16bit-Prozessor, 32bit bei einem 32bit-Prozessor und 64bit bei einem 64bit-Prozessor), und dass char die kleinste addressierbare Einheit (üblicherweise 1 Byte) ist.

"int" ist zumindest 16 Bit breit, auch bei einem 8-Bit Prozessor, und wie bereits erwähnt ist es bei 64-Bit Prozessoren zumeist auch nur 32 Bit breit. Aber vom Prinzip her hast du recht (im Standard steht iirc so etwas schwammiges wie die "natürliche Breite von Operationen").
Achtung: ein Byte hat nicht notwendigerweise 8 Bit; wenn die kleinste adressierbare Einheit z.B. 16 Bit ist, dann hat auch ein "Byte" für diese Architektur 16 Bit (cf. BITS_PER_BYTE).

Zitat von hal
Die Tabelle kann also nur für genau einen Compiler auf genau einer Plattform sein, was vermutlich nicht deiner Plattform entspricht.

Das höchste Bit einer Zahl kannst du bestimmen, indem du eine Schleife machst:
Code
for(unsigned int i = sizeof(zahl)*8; i; i--)
  if(zahl & (1 << i)) {
    printf("Höhstes Bit ist %u\n",i);
    break;
  }
Oder so in der Art (könnte wieder einen off by one-Fehler enthalten, um sowas zu kontrollieren bin ich nimmer nüchtern genug ;)).

"*8" ist böse, "*BITS_PER_BYTE" besser.

hal

Zitat von xxyy

Ich habe die for-Schleife vor das return 0 eingebaut und es kamen folgende Meldungen.

Ah, du verwendest Visual Studio... das ist nicht ganz auf der höhe der Zeit, das kann kein C99 (man beachte das Datum).

Code

unsigned int i;
for(i = sizeof(zahl)*8; i; i--)
  if(zahl & (1 << i)) {
    printf("Höhstes Bit ist %u\n",i);
    break;
  }

Zitat

Kann man die Bedingung "i" einfach alleine stehen lassen?

Klar, ist ja auch C, kein Java.

Zitat von Paulchen

Interessanterweise ist auf b1.complang.tuwien.ac.at (ein DEC Alpha, wenn ich nicht ganz blöd bin ein 64-Bit-Prozessor) ein int ebenfalls vier Bytes lang und nur ein long hat acht Bytes.

hmmm evtl war das auch für long statt int, kann den Standard nicht auswendig. Grundsätzlich gehts aber darum, dass das alles überhaupt nicht spezifiziert ist Theoretisch könnte ein short auch identisch zum char oder long sein.

Naja, genau aus diesen Gründen definiert eine verantwortungsvolle Library so Typen wie uint32_t, int8_t, etc. Die haben eine genau definiterte Bitanzahl.

jeuneS2

Für die, dies genau wissen wollen (alles aus dem letzten C99-Draft):

Zitat

p29: A ‘‘plain’’ int object has the natural size suggested by the architecture of the execution environment (large enough to contain any value in the range INT_MIN to INT_MAX as defined in the header <limits.h>).

Zitat

p442: The contents of the header <limits.h> are given below, in alphabetical order. Theminimum magnitudes shown shall be replaced by implementation-defined magnitudeswith the same sign. The values shall all be constant expressions suitable for use in #if preprocessing directives. The components are described further in 5.2.4.2.1.
#define CHAR_BIT 8
#define CHAR_MAX UCHAR_MAX or SCHAR_MAX
#define CHAR_MIN 0 or SCHAR_MIN
#define INT_MAX +32767
#define INT_MIN -32767
#define LONG_MAX +2147483647
#define LONG_MIN -2147483647
#define LLONG_MAX +9223372036854775807
#define LLONG_MIN -9223372036854775807
#define MB_LEN_MAX 1
#define SCHAR_MAX +127
#define SCHAR_MIN -127
#define SHRT_MAX +32767
#define SHRT_MIN -32767
#define UCHAR_MAX 255
#define USHRT_MAX 65535
#define UINT_MAX 65535
#define ULONG_MAX 4294967295
#define ULLONG_MAX 18446744073709551615

Alles anzeigen

also:
- char hat mindestens 8 Bit
- int hat mindestens 16 Bit
- long hat mindestens 32 Bit
- long long hat mindestens 64 Bit

Wenn z.B. aber alle 64 Bit haben wäre es auch ok.

xxyy

Ich habe mal die Funktion zur Berechnung iterativ geschrieben und mit einer Abfrage.

Code

unsigned int fibonacci(int n)
{ int x=1, y = 1, i, sum=0;
  for (i=2; i<=n; i++)
  {
      if (sum > INT_MAX-x)
      {
        printf("Fehler\n");
        return 0;
      }


    sum = x + y;
    x = y;
    y = sum; 
  }
  return y;
}

Alles anzeigen

Hab jetzt diesen Beitrag hier editiert, weil es etwas durcheinander wurde.

Ich glaube, dass es jetzt so richtig ist.
Zuerst hatte ich in der If-Abfrage UINT_MAX. Da hatte ich das Problem, dass bei der Eingabe 46 (also dass die 46. Fibonacci Zahl ausgegeben werden soll) eine negative Zahl ausgegeben wurde. Und erst ab der Eingabe 47 der "Fehler" ausgegeben wurde.
Die negative Ausgabe liegt wahrscheinlich daran, dass da schon der Überlauf stattgefunden hat und das Überlaufbit gesetzt wurde.

Nachdem ich jetzt INT_MAX genommen habe, bekomme ich schon ab der 46 die "Fehlermeldung".

Ich hoffe dass das jetzt so richtig ist...

Jetzt mitmachen!