Große Hexzahl als Dezimalzahl ausgeben.

plexplask

Hallo, was gibt es für Möglichkeiten eine grosse Zahl in Hex Form ( > 32Bit) als Integer auszugeben?

Beispiel:
Ich habe im Speicher 2 32-Bit-Wörter
(Hex: 0x462D5 3C9875C2)
(Bin:
0000 0000 0000 0100 0110 0010 1101 0101
0011 1100 1001 1000 0111 0101 1100 0010)
Ich möchte nun die Dezimalzahl, die folgenderweise berechnet wird ausgeben:
0x462d5 * 2^32 + 0x3C9875C2 = 1234567891023298

Welche Methode, die mir nicht einfällt gibt es ?

Wutz

Wenn dein Compiler uint64_t oder unsigned long long als Dezimaldatentyp kennt, kannst du diesen als Zieltyp verwenden, sonst geht es strikt ANSI konform nicht ohne Zusatzbibliotheken bzw. nicht ANSI konforme, compilerabhängige mind. 64bit Ganzzahltypen.

plexplask

Ich muss es für beliebig lange Wörter machen für ein Projekt in der Uni.
Brauche deshalb eine Idee, die mir momentan nicht einfällt.

SeppJ

Wenn das als Universitätsprojekt geplant ist, dann ist das sicher so gemeint, dass du selber so etwas wie eine Großzahlbibliothek schreiben sollst. Für die Umrechnung von Zahlensystemen brauchst du Division mit Rest und Potenzen. Das Vorgehen um dies mit beliebig langen Zahlen zu machen ist wie beim schriftlichen Rechnen in der Schule.

Mit diesen Tipps solltest du das hinbekommen, bei Unklarheiten frag nochmal nach.

plexplask

Genau, wir sollen hier mit BigInt arbeiten.
Diese haben folgende Form:

typedef unsigned int uint32;
typedef struct
{
uint32 n;
uint32 *words;
} BigInt;

Der BigInt ist also eine Zahl zur Basis 2^32.

Wir lesen hierbei aus einer Textdatei 2 lange Zahlen aus und müssen diese zum Beispiel addieren.

Ich habe bereits folgendes implementiert:
Ich kann eine beliebige Dezimalzahl aus einer Textdatei einlesen und diese in einem BigInt darstellen.
Ich kann auch auch 2 BigInt miteinander addieren.

Mein Problem ist nun aus einem solchen BigInt wieder eine Dezimalzahl zu erstellen.
Du hast mir ja geschrieben, man bräuchte Potenzen dazu.
Wenn ich beispielsweise die HexZahl 2D nach Dez umwandeln will,
dann mache ich folgendes: 2D = 2*16^1 + D = 32+13=45
Aber bei meinem BigInt gilt
462D5 3C9875C2 = 462d5 * 2^32 + 0x3C9875C2
Allerdings passt 462d5 * 2^32 bereits nicht mehr in einen int.
Wie kann ich das bewerkstelligen?

nachtfeuer

schreib eine asm routine, die macht das für dich.

plexplask

würde ich gern machen, wir sollen aber ausschließlich C benutzen.

nachtfeuer

asm unterprogramme gehören auch zu C, also alles legitim

SeppJ

Geh zeichenweise vor. Die Dezimaldarstellung brauchst du schließlich nur bei der Ausgabe. Es gibt keinen Grund das Zwischenergebnis in einem int zu speichern.

plexplask

Kannst du das näher erläutern?

Wenn ich 462D5 3C9875C2 zeichenweise interpretiere,
dann fange ich beispielweise hier mit 4 an: 4 * 16^12
Dabei kann ich ja 16^12 bereits nicht mehr berechnen, da das schon größer als 32 Bit ist.

SeppJ

plexplask schrieb:

Dabei kann ich ja 16^12 bereits nicht mehr berechnen, da das schon größer als 32 Bit ist.

Ich habe gehört, jemand hat kürzlich eine Bibliothek geschrieben die mit großen Zahlen rechnen kann...

plexplask

Ja natürlich, aber dann bin ich doch wieder beim Ausgangsproblem.
Meine BigInt Zahl sind in der Basis 2^32, wenn ich also 16^12 berechne, habe ich das Ergebnis wieder als BigInt Zahl, ich möchte aber am Ende eine Dezimale Zahl ausgeben.

SeppJ

plexplask schrieb:

Ja natürlich, aber dann bin ich doch wieder beim Ausgangsproblem.
Meine BigInt Zahl sind in der Basis 2^32, wenn ich also 16^12 berechne, habe ich das Ergebnis wieder als BigInt Zahl, ich möchte aber am Ende eine Dezimale Zahl ausgeben.

Ich sehe da irgendwie dein Problem nicht. Jede einzelne Ziffer die du berechnen wirst wird naturgemäß zwischen 0 und 9 sein.

mngbd

plexplask schrieb:

typedef unsigned int uint32;
typedef struct
{
uint32 n;
uint32 *words;
} BigInt;

Frag mal nach, warum nicht

typedef struct
{
        uint32 n;
        uint32 words[1];
} BigInt;

mit nur halb so vielen malloc()'s.

plexplask

Wenn ich mich nicht irre, dann kann "uint32 words[1];" ja nur 2 32Bit Wörter enthalten, unsere Struktur soll aber dynamisch beliebig viele Wörter aufnehmen können.

Wutz

Also langsam dämmert es mir, was du willst

Für sowas sollte es wohl Bibliotheken geben, http://gmplib.org/ fällt mir da spontan ein.
Ansonsten würde ich mal eine Multiplikation+Addition mit Strings implementieren, welche mit unbegrenzt langen Zahlen=Strings klarkommt, also z.B.

char *addiere(const char *s1,const char *s2,char *erg)
{}

sowie

char *mult(const char *f1,const char *f2,char *erg)
{}

und damit dann über deine words laufen. Sollte wohl nicht zu aufwändig sein für Studenten, die haben eh zuviel Zeit

Hier mal ein Testfall für dich, welcher ein Einzeiler in der Programmiersprache meiner Wahl ist:
160 Bit:
hex: 'FFABCDEFFFABCDEFFFABCDEFFFABCDEFFFABCDEF'
dez: '1459624013674974718788098591257521174742471265775'
okt: '177653633677775274675777725715737776536336777752746757'
bin: '1111111110101011110011011110111111111111101010111100110111101111111111111010101111001101111011111111111110101011110011011110111111111111101010111100110111101111'

Habe gerade im C++ Forum was gefunden: http://www.c-plusplus.net/forum/viewtopic-var-t-is-265048-and-start-is-20-and-postdays-is-0-and-postorder-is-asc-and-highlight-is-.html
scheint nicht viel C++ zu sein, es empfiehlt sich aber, bis zum Ende zu lesen.

mngbd

plexplask schrieb:

Wenn ich mich nicht irre, dann kann "uint32 words[1];" ja nur 2 32Bit Wörter enthalten, unsere Struktur soll aber dynamisch beliebig viele Wörter aufnehmen können.

In das Array passt nur ein Wort. Macht aber nichts, wenn man dahinter genügend Platz freihält und über die Array-Grenzen hinausschreibt. Im Standard findet man sogar die Forderung, dass solche Konstruktionen keine Probleme mit der Ausrichtung machen dürfen.

Mach es lieber so, wenn deine Struktur nicht vorgeschrieben ist, wäre schlauer.

Wutz schrieb:

Ansonsten würde ich mal eine Multiplikation+Addition mit Strings implementieren

Mit Strings? Strings??