C Dezimal in Hexadezimal umwandeln... die schönste lösung wäre jetzt was? :)

ReVo · 1. Juni 2009

Hiho,

vor kurzem haben ich zufällig in der Schule gehört, dass eine Gruppe die Aufgabe bekommen hätte in C ein Code zu zaubern, was eine Dezimal-Zahl in Hexadezimal umwandelt. Das sollte, dann nur wenige Zeilen Code sein...

Habe überlegt und zu mir gemeint, dass ich das eigentlich locker könnte. Was braucht man devor ich loslege? Schön wäre es zu wissen wie man am besten von Dezi auf Hexa im Kopf rechnet, oder zumindest aufm blatt Papier

Also mir fällt immer diese Methode am leichtesten

Nehmen wir die Dezizahl 20 , dann wandeln wir das in Binär um = 10100 (glaube das muss ich nicht erklären

) => JETZT werden von hinten immer 4 schrittweise zahlen gebildet: 1|0100 => 0100 = 4 und danach bleibt nur eine 1 = 1 => Ergebnis: 14

So jetzt zum Code, ich lege los. Erstmal ein Abschnitt was Dual in Binär umwandelt. Dann ein Abschnitt was die wie in mein Beispiel die Binwerte aufteilt. Dann müssen die zusammengerechnet werden und dann...ahja muss ja noch beachtet werden, denn als Ergebnis könnte auch: A,B,C,D... sein (also case oder sowas einbauen) und dann merkte ich, dass das keine paar zeilen Code ist, sondern übergroß. Es ist halbwegs am funktionieren, aber wie immer alles von mir => unnötig übergroß

Also hier muss mir niemand fertige Codes posten, sondern einfach nur erklären wie es leichter wäre. Sollte ich mit der bitverschiebung arbeiten? Das würde doch einiges erleichtern, brauche das umwandeln nicht mehr zu coden - oder so irgendwie war das, glaube C kann das. Habe einige Beispiele im net gesehen, aber irgendwie entsprechen die nicht meine Vorstellungen bzw. ist das meiste in C++ oder verstehe nichts ^^

Jemand paar informative Sätze?

Danke und Gruß

Stefan_Sch · 1. Juni 2009

Normalerweise stellt C die Funktion sprintf zur Verfügung.

PHP:

#include <stdio.h>

int main()
{
    char hex[256];
    unsigned int dec = 345243;

    sprintf(hex, "%x", dec);
    printf("Hexadecimal value of the decimal value %d is %s.\n", dec, hex);

    return 0;
}

Falls du die Berechnung selbst ohne Hilfsfunktion durchführen musst, wirst du das natürlich Schritt für Schritt machen müssen. Dein Ansatz ist richtig.

Nutze Bitshifts und Bitmaskierungen, dann kannst du die Dezimalzahl in Quartetts teilen und in Hex umwandeln.

ReVo · 1. Juni 2009

Hi,

Was dein Code da betrifft, von sowas habe ich auch mal was gehört - ABER DAS DARF MAN NICHT!!

Schade eigentlich :/

Gruß ^^

Stefan_Sch · 1. Juni 2009

Wenn man keine Hilfsfunktion verwenden darf, damit ihr es selbst lernt, dann halte dich an meinen zweiten Ratschlag.

Müsst ihr positive Dezimalzahlen in Hex konvertieren oder soll das auch für negative Zahlen möglich sein?

Ergänzung (1. Juni 2009)

Hier die Lösung.

PHP:

#include <stdio.h>

typedef unsigned __int32  uint32_t;

char hexchars[] = "0123456789ABCDEF";   // Hexadezimaler Zeichensatz
char output[] = "00000000";                       // 4-Byte entsprechen 0x00000000

char* dec2hex(uint32_t dec)
{
    output[7] = hexchars[dec       & 0xF];
    output[6] = hexchars[dec >>  4 & 0xF];
    output[5] = hexchars[dec >>  8 & 0xF];
    output[4] = hexchars[dec >> 12 & 0xF];
    output[3] = hexchars[dec >> 16 & 0xF];
    output[2] = hexchars[dec >> 20 & 0xF];
    output[1] = hexchars[dec >> 24 & 0xF];
    output[0] = hexchars[dec >> 28];

    return output;
}

int main()
{
    uint32_t n = 3612872341;

    printf("%s \n", dec2hex(n)); 

    return 0;
}

Woey · 1. Juni 2009

hi,

hier noch ne andere Variante:

Code:

void dw2hex(unsigned int num,char* buffer)
{
	for(unsigned int i=7,tmp;!(i&0x80000000);i--)
	{
		tmp = num&0xf;
		buffer[i]= (tmp<10)?(tmp+0x30):(tmp+0x37);
		num = num>>4;		
	}
	buffer[8]=0;
}

IceMatrix · 1. Juni 2009

bekommst du die zahl als hardcoded integer oder als string? generell sind konvertierungen von zahlensystemen ziemlich einfach. die oben genannten beispiele sind schon recht gut, das erste beispiel allerdings bissl lang

es geht kürzer.

bei hexadezimal empfielt es sich generell bitweise operatoren zu verwenden, da die interne zahlendarstellung im rechner binär ist, und hexadezimal zu der gleichen klasse gehört, also 4 bits eine hex-ziffer repräsentieren. bei zehnersystemen z.b. musst du auf arithmetik ausweichen.
p.s. bitweises shiften und ANDs sind im grunde auch artithmetik, allerdings implizit

X >> 1 => X /= 2
X & 1 => X %= 2

Müsst ihr positive Dezimalzahlen in Hex konvertieren oder soll das auch für negative Zahlen möglich sein?

beides wird gleich konvertiert. negative zahlen werden als zweierkomplement gespeichert.

Stefan_Sch · 1. Juni 2009

IceMatrix schrieb:
bekommst du die zahl als hardcoded integer oder als string? generell sind konvertierungen von zahlensystemen ziemlich einfach. die oben genannten beispiele sind schon recht gut, das erste beispiel allerdings bissl lang es geht kürzer.

Falsch! Das von mir dargestellte Beispiel ist auf optimale Geschwindigkeit getrimmt und deshalb etwas länger. Es greift direkt auf ein Tabellenmapping zurück.

Ich schätze das die von mir gepostete Funktion rund 400 % schneller arbeitet als die Lösung von Woey.

Ich kann die Funktion auch direkt in Assembler schreiben, dann ist sie noch länger und noch schneller!

Das von Woey ist derselbe Käse mit dem Unterschied das er bereits ein Array erwartet und dieses nicht erst in der Funktion allokiert und das er eine Schleife samt bedingter Abfrage über den ? Operator verwendet. Das dauert natürlich deutlich länger, weil hier aufwendigere CPU Instruktionen im Spiel sind.

Natürlich könnte ich den Kram auch direkt in einer Schleife abarbeiten und der Code wäre kürzer, dafür langsamer.

PHP:

void dec2hex(uint32_t dec, char* buffer)
{
    for(unsigned int i = 0; i != 8; i++) 
        buffer[7 - i] = hexchars[dec >> (i * 4) & 0xF];
}

IceMatrix schrieb:
beides wird gleich konvertiert. negative zahlen werden als zweierkomplement gespeichert.

Nein. Richtig ist das negative Zahlen als Zweierkompliment in modernen Rechner gespeichert werden. Das ist aber eine Zahleninterpretation, sonst nichts.

Es macht allerdings einen Unterschied ob ich -1 oder FFFFFFFF schreibe. Ich kann von meiner Funktion aber auch erwarten das sie -1 auch in Hexdarstellung als -1 ausgibt.

Es ist also sehr wohl ein Unterschied ob ich positive oder negative Zahlen bei der Konvertierung betrachte.

Woey · 2. Juni 2009

Stefan_Sch schrieb:
Ich schätze das die von mir gepostete Funktion rund 400 % schneller arbeitet als die Lösung von Woey.

Ich kann die Funktion auch direkt in Assembler schreiben, dann ist sie noch länger und noch schneller!

du bist dir ja sehr Sicher...

Wenn es dir auf Geschwindigkeit ankommt, dann schau dir mal das Folgende an:

Code:

__declspec(align(16)); 
void sse_dw2hex(unsigned int num,char* buffer)
{

     __declspec(align(16)) struct mmx_data
	{
		long long d2h_bitmsk;//=0xf00ff00ff00ff00f
		long long d2h_cmpmsk;//=0x0909090909090909
		long long d2h_09_msk;//=0x3030303030303030
		long long d2h_AF_msk;//=0x0707070707070707
	};
	
	static mmx_data d2h={0xf00ff00ff00ff00f,0x0909090909090909,0x3030303030303030,0x0707070707070707};
	
	__asm{
		mov eax,num
		mov edx,buffer
		
		movd mm1,eax
		punpcklbw mm1,mm1
		pshufw mm1,mm1,27
	
		pand mm1,d2h.d2h_bitmsk
		movq mm0,mm1
		psrlw mm0,12
		psllw mm1,8
		
		por mm0,mm1
		movq mm2,mm0
		pcmpgtb mm2,d2h.d2h_cmpmsk
	
		pand mm2,d2h.d2h_AF_msk
		paddb mm2,d2h.d2h_09_msk
		paddb mm2,mm0
	
		movq QWORD ptr [edx],mm2
		mov BYTE ptr [edx+8],0
	}
}

Die Rahmenbedingungen dieser Funktion dürften dir ja klar sein

grüße Woey

Stefan_Sch · 2. Juni 2009

Woey schrieb:
du bist dir ja sehr Sicher...

Natürlich bin ich mir sicher, weil das nunmal der Fall ist.

Woey schrieb:
Wenn es dir auf Geschwindigkeit ankommt, dann schau dir mal das Folgende an:

Mir kommt es nicht auf die Geschwindigkeit an, ich habe lediglich versucht dem User IceMatrix zu erklären das es einen Unterschied zwischen Codelänge und Geschwindigkeit gibt.

Nur weil ein Codeabschnitt kürzer ist, ist er deshalb nicht zwangsläufig besser oder schlechter. Beide Lösungen sind technisch gesehen sehr gute C-Lösungen, setzen aber andere Prioritäten.

Woey schrieb:
Die Rahmenbedingungen dieser Funktion dürften dir ja klar sein :

Du hast dir die Mühe gemacht, wie von mir vorgeschlagen, die Funktion in ASM zu gießen und das auch noch unter Verwendung des MMX Befehlsatzes mit 16-byte boundaries? Sehr lobenswert! Das sieht man auch nicht alle Tage...

Schon einen Performancetest gemacht?

Die ASM Routine muss nicht zwangsläufig schneller sein als die von mir genannte C-Funktion. Die guten C-Compiler optimieren ganz erheblich beim Kompilieren...

ASM ist kein C mehr, so dass hier ein Vergleich ein wenig hinkt. Nichtsdestotrotz schaue ich mir mal die Performance an.

Woey · 2. Juni 2009

Stefan_Sch schrieb:
Schon einen Performancetest gemacht?

Ja, allerding hatte die Funktion hierbei keine Stackframe: 2-3 clocks (sequentiell,Core2Duo).Ich denke, dass es derzeit keinen Schnellern Algo dafür gibt. Das einzig was einen hieran noch stören könnte , ist die Verwendung von mmx-Registern (mmx<=>fpu).

Stefan_Sch schrieb:
Du hast dir die Mühe gemacht

ja, aber nicht Gestern (heut Früh)

Stefan_Sch schrieb:
unter Verwendung des MMX Befehlsatzes

mmx/sse1

ReVo · 2. Juni 2009

Hallo,

also danke ertmal für die zahlreichen Codes. Die sehen wirklich sehr gut aus! Es sollte natürlich auch nicht allzu hardcor3-1mba-haxx0r mäßig aussehen

, also welche jetzt wie schneller ist, ist wirklich nicht von bedeutung ^^ - Und ja es reicht einfach wenn die Ausgabe nach eine lösung aussieht (also das muss nirgendwo als string oder int gespeichert werden). Habe heute nicht direkt Zeit dazu aber ich bastel mal das (wie ich denke) passendste Code dazu.

Gruß

ryan_blackdrago · 2. Juni 2009

Geht es um die Umwandlung, oder einfach die Ausgabe?

Code:

#include <stdio.h> 
int main() 
{   
int zahl;
printf("Bitte eine Zahl eingeben:  ");
scanf("%i" ,&zahl);
printf("die Zahl %d HEX dargestellt:   %x \n",zahl ,zahl);
system("Pause");
}

Stefan_Sch · 2. Juni 2009

Woey schrieb:
ja, aber nicht Gestern (heut Früh)

Der Code erinnert mich aber stark an den folgenden. Um nicht zu sagen das er praktisch identisch ist.

Code:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;             
;                                                  ;             
;   sse1_dw2hex: converts a dword-value to an      ;             
;                ASC-hex-string                    ;             
;                                                  ;             
;       eax = dwValue                              ;             
;       edx = lpBuffer , should be aligned to 8    ;             
;                                                  ;             
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;             
align 16                                                         
sse1_dw2hex proc ;var:DWORD,buffer:DWORD                         
                                                                 
    .data                                                       
        align 16                                                 
        d2h_bitmsk  dw 4 dup (0f00fh)                           
        d2h_cmpmsk  db 8 dup (9)                                 
        d2h_09_msk  db 8 dup (030h)                             
        d2h_AF_msk  db 8 dup (7)                                 
    .code                                                       
                                                                 
    ;bswap eax                          ;<== insert for mmx only
    movq mm4,QWORD ptr [d2h_bitmsk]     ;       |               
    movq mm5,QWORD ptr [d2h_cmpmsk]     ;       |               
    movq mm6,QWORD ptr [d2h_09_msk]     ;       |               
    movq mm7,QWORD ptr [d2h_AF_msk]     ;       |               
                                        ;       |               
    movd mm1,eax                        ;       |               
    punpcklbw mm1,mm1                   ;       V               
    pshufw mm1,mm1,000011011y           ;<== delete for mmx only
                                                                 
    pand mm1,mm4                                                 
    movq mm0,mm1                                                 
    psrlw mm0,12                                                 
    psllw mm1,8                                                 
                                                                 
    por mm0,mm1                                                 
    movq mm2,mm0                                                 
    pcmpgtb mm2,mm5                                             
                                                                 
    pand mm2,mm7                                                 
    paddb mm2,mm6                                               
    paddb mm2,mm0                                               
                                                                 
    movq QWORD ptr [edx],mm2                                     
    mov BYTE ptr [edx+8],0                                       
                                                                 
    ret                                                         
sse1_dw2hex endp

Quelle: http://www.masm32.com/board/index.php?PHPSESSID=b96db6cd0dd9e23500fa21b6bb93457c&topic=9401.60

Die Lösung ist in der Tat schon arg optimiert. Durch die speziellen Bitmaskierungen erspart man sich die Shifts und weitere Operationen.

Dennoch ist der Code nur sehr unwesentlich schneller als die von mir genannte C-Variante, was durchaus beachtlich ist. Der Unterschied zwischen der Tablemapping C-Funktion und der Schleifen C-Funktion ist ganz erheblich größer.

Die MMX/SSE Instruktionen benötigen aber mehr Cycles als die Standard Shifts und Moves, was ein Grund ist.

PHP:

void asm_dec2hex(uint32_t dec, char* output)
{
    __asm {
        mov ecx,output
        mov	eax,dec
        mov	edx,eax
        and edx,0000000Fh
        mov dl,[edx+hexchars] 
        mov	[ecx+07h],dl 
        mov	edx,eax
        shr	edx,04h
        and	edx,0000000Fh
        mov dl,[edx+hexchars]
        mov	[ecx+06h],dl
        mov	edx,eax
        shr	edx,08h
        and	edx,0000000Fh
        mov dl,[edx+hexchars]
        mov	[ecx+05h],dl
        mov	edx,eax
        shr	edx,0Ch
        and	edx,0000000Fh
        mov dl,[edx+hexchars]
        mov	[ecx+04h],dl
        mov	edx,eax
        shr	edx,10h
        and	edx,0000000Fh
        mov dl,[edx+hexchars]
        mov	[ecx+03h],dl
        mov	edx,eax
        shr	edx,14h
        and	edx,0000000Fh
        mov dl,[edx+hexchars]
        mov	[ecx+02h],dl
        mov	edx,eax
        shr	edx,18h
        and	edx,0000000Fh
        mov dl,[edx+hexchars]
        shr	eax,1Ch
        mov	[ecx+01h],dl
        mov	al,[eax+hexchars]
        mov	[ecx],al
    }
}

Durch die MMX Befehle werden außerdem die FPU Register versperrt und das kann in der Applikation unangenehm sein.

Woey · 2. Juni 2009

Stefan_Sch schrieb:
Der Code erinnert mich aber stark an den folgenden. Um nicht zu sagen das er praktisch identisch ist.

Stefan_Sch schrieb:
Dennoch ist der Code nur sehr unwesentlich schneller als die von mir genannte C-Variante

Naja, bei mir sind es nur ~300% unterschied: Im Anhang findest du ein kleines Testbed

Stefan_Sch · 3. Juni 2009

Woey schrieb:
Naja, bei mir sind es nur ~300% unterschied: Im Anhang findest du ein kleines Testbed

Die Cycles sind hier aber nicht sehr relevant. Die machen bei einem Gigahertz Prozessor ein paar Nanosekunden aus. Benchmarked man alle drei Funktionen Realtime, z.B. indem man die Funktion 803206399x aufruft, den Hexwert berechnen und im Buffer abspeichern lässt, so liegt die C-Funktion dec2hex mit insgesamt 5 sec gerade einmal knapp 1 Sekunde über der optimierten ASM Funktion sse_dw2hex auf meinem Intel Quad Core.

Die C-Funktion dw2hex landet mit 22 sec weit abgeschlagen hinter den beiden Spitzenreitern.

Woey · 3. Juni 2009

Stefan_Sch schrieb:
Die Cycles sind hier aber nicht sehr relevant. Die machen bei einem Gigahertz Prozessor ein paar Nanosekunden aus.

Oo

Stefan_Sch schrieb:
Benchmarked man alle drei Funktionen Realtime, z.B. indem man die Funktion 803206399x aufruft...

genau das mach ich auch (100000000 mal), mit den Unterschied dass ich die clocks Messe (rtsc), anstatt direkt eine Zeit.

Stefan_Sch schrieb:
Die C-Funktion dw2hex landet mit 22 sec weit abgeschlagen ...

Ich hab ja auch nie behauptet, dass sie schneller ist.

Suche

C Dezimal in Hexadezimal umwandeln... die schönste lösung wäre jetzt was? :)

ReVo

Lieutenant

Stefan_Sch

Gast

ReVo

Lieutenant

Stefan_Sch

Gast

Woey

Ensign

IceMatrix

Lt. Commander

Stefan_Sch

Gast

Woey

Ensign

Stefan_Sch

Gast

Woey

Ensign

ReVo

Lieutenant

ryan_blackdrago

Captain

Stefan_Sch

Gast

Woey

Ensign

Anhänge

Stefan_Sch

Gast

Woey

Ensign