4. schnell int nach binär-string und umgekehrt konvertieren

schnell int nach binär-string und umgekehrt konvertieren

  • ?

    hi,
    ich muss einen string(gefüllt mit '0' und '1') in eine dezimalzahl(0..255)
    umwandeln und umgekehrt.
    hab das ganze auch in c++ umgesetzt (s.u.).
    allerdings wird der code ein paar millionen mal durchlaufen und ist somit sehr
    zeitkritisch.
    da die umwandlung IN eine dezimalzahl 6-7 mal schneller ist als die rückumwandlung
    vermute ich, dass in meinem einen code eine "bremse" versteckt ist,
    die ich nicht finde...
    daher hab ich mir gedacht, dass ihr mir helfen könnt einen assemblercode zu
    basteln, der die aufgabe SCHNELL erledigen kann.

    hier min c++ code:

    //CODE ANFANG
//--------Zahl(0..255) in einen Binär-String
char *inttobin(unsigned int Zahl)
{
	static char BinStr[8];
	unsigned int i=7;
	unsigned int j=0;
	while (i+1>=j+1)
	{
		BinStr[i]=48+(Zahl&(1<<j))/(1<<j);
		BinStr[j]=48+(Zahl&(1<<i))/(1<<i);
		j++;
		i--;
	}
	return BinStr;
}

//--------Binär-String in eine Zahl(0..255)
unsigned int bintoint(char *BinStr)
{
	static unsigned int Zahl;
	unsigned int i=7;
	unsigned int j=0;
	while (i+1>=j+1)
	{
		Zahl|=(BinStr[i]&1)<<j;
		Zahl|=(BinStr[j]&1)<<i;
		j++;
		i--;
	}
	return Zahl;
}
//CODE ENDE

    Falls ihr tipps und vorschläge habt um den code besser (vor allem schneller) zu machen wäre ich dankbar.
    ein guter assemblercode wäre am besten, da der die schnellste variante darstellt. 🙄

    mfg
    Alex

    0
  • V

    Hier, diese Rekursion habe ich mal mit Turbo Pascal geschrieben. Kann eine Dzimalzahl in ein beliebiges Zahlensystem mit der Basis 2-32 Umwandeln:

    function zazi(r:longint):char; 
begin 
  if r<10 then zazi:=chr(r+ord('0')) 
  else zazi:=chr(r-10+ord('A')) 
end;

    function dez2zsys(x,y:longint):string; 
begin 
  if x=0 then dez2zsys:='0' 
  else if x>0 then dez2zsys:=dez2zsys(x div y,y) + zazi(x mod y) 
end;

    Ich hatte auch mal eine Prozedur die Binär nach Dezimal umwandeln konnte aber die muss ich erst suchen. Wozu das Rad neu erfinden (oder so). Ich denke mal das oben kannst du selbst umwandeln in C++-Code. Und das Ergebnis der Ausgabe ist String.

    Code-Hacker

    0
  • ?

    hmm, an eine rekursion hab ich überhaupt noch nicht gedacht...
    allerdings vermute ich, dass dein code nicht schneller ist,da er für
    seine "flexible" einsatzweise viele IF's und so durchlaufen muss.
    ausserden siehts mit strings in c++ ja eh schwach aus und andauernd
    ein strcat (aus 2 mach 1) machen bremst auch nur...
    und "x MOD 2" (x%2) hatte ich auch schon ausprobiert, war auch langsamer...

    Wozu das Rad neu erfinden (oder so).

    weil das rad zu langsam ist oder ich es nicht finde 🙄

    mfg
    Alex

    0
  • M

    Hmm ... das Modulo 2 ist wirklich langsamer? Wie wäre es mit dieser Variante (kA, ob die irgendwie schneller ist):

    char *inttobin2(unsigned int zahl)
{
	static char binstr2[8];

	for(int i=7;i>=0;i--)
	{
		if(zahl & 1)
			binstr2[i]='1';
		else
			binstr2[i]='0';
		zahl>>=1;
	}
	return binstr2;
}

    Du könntest auf jeden Fall if(i+1 >= j+1) zu if(i>=j) verkürzen. Wenn dein Code wirklich so extrem oft aufgerufen wird, dann solltest du dir überlegen die Funktion als inline zu deklarieren.

    0
  • ?

    also

    Modulo 2 ist wirklich langsamer

    ...zumindest auf meinem alten arbeitsrechner (MSVisualStudio 6.0).
    auf meinem anderen rechner (Borland 5.0) ist kein/kaum ein unterschied...

    inline ist ne gute idee, jedoch inlined der nicht,
    wenn for,while oder ne static variable in der funktion ist
    und ich bin zu blöd den wert zu übergeben, wenn ich static nicht verwende.
    (globale variable will ich nicht benutzen)
    vielleicht könnt ihr mir da ja nen tipp geben 😉

    also hier erstmal meine schnellste version die ich habe:

    //CODE ANFANG 
//--------Zahl(0..255) in einen Binär-String
char *inttobin(unsigned int zahl)
{
  static char binstr[8];
    binstr[7]=48+(zahl&1);zahl>>=1;
    binstr[6]=48+(zahl&1);zahl>>=1;
    binstr[5]=48+(zahl&1);zahl>>=1;
    binstr[4]=48+(zahl&1);zahl>>=1;
    binstr[3]=48+(zahl&1);zahl>>=1;
    binstr[2]=48+(zahl&1);zahl>>=1;
    binstr[1]=48+(zahl&1);zahl>>=1;
    binstr[0]=48+(zahl&1);
  return binstr2;
}

//--------Binär-String in eine Zahl(0..255)
inline unsigned int bintoint(char *binstr)
{
  unsigned int zahl=0;
    zahl|=(binstr[7]&1)<<(0);
    zahl|=(binstr[6]&1)<<(1);
    zahl|=(binstr[5]&1)<<(2);
    zahl|=(binstr[4]&1)<<(3);
    zahl|=(binstr[3]&1)<<(4);
    zahl|=(binstr[2]&1)<<(5);
    zahl|=(binstr[1]&1)<<(6);
    zahl|=(binstr[0]&1)<<(7);
  return zahl;
}

    ohne schleife,da es immer 8 stellen sind und sonst inline nicht klappt.
    ausserdem sind sie so noch n bissle schneller. 😃
    sind inzwischen beide in etwa gleich schnell.

    bin für weitere anregungen immer offen.
    ich warte eigentlich auch noch auf tipps von assembler leuten,
    sonst hätte ich gleich im c++ forum gepostet 🙄

    mfg
    Alex

    0
  • T

    hab keine ahnung obs schneller is als deins, hattes mal vor langer zeit geschrieben

    char binstr[8];

void SetzeBits(unsigned char n)
{
	char i;

	for (i=7; i >= 0 ;--i)
	  binstr[i]=((n>>i)&1)+'0';
}

int main(void)
{

SetzeBits(8);

puts(binstr);

return 0;
}

    das gibt dir das im little endian format aus 🙂 wenn du es in der "lesbaren" sprich big endian haben möchtest nimm folgendes, das dürfte aber langsamer sein

    void SetzeBits(unsigned char n)
{
	char i,r=0;

	for (i=7; i >= 0 ;--i,++r)
	  binstr[r]=((n>>i)&1)+'0';
}

    bye

    tt

    0
  • T

    so wie ich das grad sehe is das ums doppelte langsamer als dein vorhergehender code 😉

    void inttobin2(unsigned char zahl)
{
    binstr[7]=((zahl>>0)&1)+'0';
    binstr[6]=((zahl>>1)&1)+'0';
    binstr[5]=((zahl>>2)&1)+'0';
    binstr[4]=((zahl>>3)&1)+'0';
    binstr[3]=((zahl>>4)&1)+'0';
    binstr[2]=((zahl>>5)&1)+'0';
    binstr[1]=((zahl>>6)&1)+'0';
    binstr[0]=((zahl>>7)&1)+'0';
}

    so ist er aber noch etwas schneller da er weniger operationen macht...inline und so bringt nix zumindest nicht bei mir, ach ja falls du dich wunderst ich hab binstr[8] als globalen string, kannst ja wieder reinpacken 🙂

    tschööö

    tt

    0
  • T

    ich konnts nich lassen und hab mal rumprobiert was mein compiler son bringt 😉 hab den lccwin32 (only c compiler) und nachdem ich die optimierungen und noch das static inline davor gepackt hab...gings mal richtig ab 😉 bei 30 Mio. Durchläufen (mein sys. xp 1700 und 256mb ram) betrug die gesamtlaufzeit des programmes irgendwas bei 590 milisek. mein profiler hat die werte schon gar nich mehr angezeigt 😉 vielleicht wär das auch noch ne option für dich 🙂 kommt sicher auf dein compiler drauf an

    static inline void inttobin2(unsigned char zahl)
{
    binstr[7]=((zahl>>0)&1)+'0';
    binstr[6]=((zahl>>1)&1)+'0';
    binstr[5]=((zahl>>2)&1)+'0';
    binstr[4]=((zahl>>3)&1)+'0';
    binstr[3]=((zahl>>4)&1)+'0';
    binstr[2]=((zahl>>5)&1)+'0';
    binstr[1]=((zahl>>6)&1)+'0';
    binstr[0]=((zahl>>7)&1)+'0';
}

    bye

    tt

    PS: was ich noch erwähnen sollte ich hab mir nur das letzte ergebnis jeweils ausgeben lassen, siehst du ja oben...sich jedes ergebnis auf dem schirm ausgeben lassen zwingt das sys ganz schön in die knie 🙂

    0
  • ?

    static ändert nicht die geschwindigkeit.

    0
  • T

    frag mich nicht 🙂 "nur" mit inline gab es keine veränderung mit static schon *schulterzuck*

    bye

    tt

    0
  • ?

    soweit so gut, wenn man die funktion "inttobin" inlined und nen constanten
    wert übergibt(z.B. <const int i=101>) dann ist sie schön schnell...
    wenn man aber nur <int i=101> (ohne const) übergibt ist die funktion zu
    langsam. nen konstanten wert übergeben bringt mir aber wenig, weil da könnte
    ich ja gleich das ergebnis ins programm reinschreiben...
    die variable global zu deklarieren hat einiges gebracht, allerdings hatte ich
    versucht das zu vermeiden,da ich ein bestehendes, nicht von mir entwickeltes
    programm optimieren soll und ich eventuellen problemen gleich aus dem weg gehen wollte.
    (vllt. ne dumme idee 🙄 )
    ach ja, die funktionen müssen das ergebnis zurrückgeben.
    in eine variable schreiben und deren inhalt dann zu nehmen ist nicht akzeptabel!
    sonst dürfte ich ein paar zig MB quellcode abändern... 😮

    hier erstmal mein aktueller code:

    //-----------------------------------------------------------------------------
//---------------------------IntToBin------------------------------------------

static char binstr2[9]={NULL};
static inline char* inttobin2(unsigned char zahl)
{
    binstr2[7]=(zahl&1)+48;
    binstr2[6]=((zahl>>1)&1)+48;
    binstr2[5]=((zahl>>2)&1)+48;
    binstr2[4]=((zahl>>3)&1)+48;
    binstr2[3]=((zahl>>4)&1)+48;
    binstr2[2]=((zahl>>5)&1)+48;
    binstr2[1]=((zahl>>6)&1)+48;
    binstr2[0]=((zahl>>7)&1)+48;
    return binstr2;
}

//-----------------------------------------------------------------------------
//---------------------------BinToInt------------------------------------------

static inline unsigned int bintoint(char *binstr)
{
  return ((binstr[0]&1)<<7)+
         ((binstr[1]&1)<<6)+
         ((binstr[2]&1)<<5)+
         ((binstr[3]&1)<<4)+
         ((binstr[4]&1)<<3)+
         ((binstr[5]&1)<<2)+
         ((binstr[6]&1)<<1)+
         ((binstr[7]&1));
}

    hoffe ihr habt noch n paar ideen, die mich auf den schnellsten weg bringen 😉

    mfg
    Alex

    0
  • T

    oke...also mir kam da was in denn sinn

    #include <stdio.h>
#include <string.h>
#include <stdlib.h>

int binstr[8];

typedef struct _binchar
{
	unsigned _0:1;
	unsigned _1:1;
	unsigned _2:1;
	unsigned _3:1;
	unsigned _4:1;
	unsigned _5:1;
	unsigned _6:1;
	unsigned _7:1;

}binchar;

typedef union _blubb
{
	binchar zahl_bin;
	unsigned char input;

}blubb;

void inttobin3(unsigned char zahl)
{
    static blubb test_input;
    test_input.input = zahl;

    binstr[7]=test_input.zahl_bin._0;
    binstr[6]=test_input.zahl_bin._1;
    binstr[5]=test_input.zahl_bin._2;
    binstr[4]=test_input.zahl_bin._3;
    binstr[3]=test_input.zahl_bin._4;
    binstr[2]=test_input.zahl_bin._5;
    binstr[1]=test_input.zahl_bin._6;
    binstr[0]=test_input.zahl_bin._7;
}

int main(void)
{
    int ctr;

    inttobin3(8);

    for(ctr = 0; ctr < 8; ++ctr)
	printf("%d", binstr[ctr]);
return 0;
}

    wenn ich das aufrufe 😉 ein paar mal...dann wird laut profiler eigentlich nur noch zeit in main() verbraucht 😉

    das einzige was nicht mehr wirklich geht ist das als char array zu speichern und auszugeben weil 1 und 0 dezimal im ascii satz was anderes sind... deswegen ist bei mir binchar nun halt mal ein int geworden 🙂 du kannst aber als alternativ möglichkeit das trotzdem in nem char array speichern das dann wenn die ausgabe benötigt wird nach 0 und 1 durchparsen und durch 48 und 49 ersetzen (sollten doch die "richtigen" zahlen codes sein oder?)

    bye

    tt

    PS: sorry für die z.t. blöden namen 😉

    0
  • D

    Also wenn du es richtig schnell haben willst, dann nimm halt ein array anstelle einer Funktion.

    const char inttobin[256][9]={
    "00000000",
    "00000001",
    "00000010",
    "00000011",
    "00000100",
    ...
    "11111111"
};

int main() {
    const char *bin;

    bin=inttobin[3];

    return 0;
}
    0
  • ?

    hab meinen rechner zerschossen (man sollte besser assembler können,bevor man versucht damit hardwaregeräte anzusprechen)
    , deshalb kann ichs im mom nicht testen,
    aber das mit dem array scheint mir eine sehr gute idee...
    werds testen sobald meine kiste wieder funzt...

    mfg
    Alex

    0
  • C

    Eine Frage an den ursprünglichen Fragesteller (AlexC++):
    Hast du mit einem Profiler festgestellt, dass diese Funktion der Flaschenhals ist oder vermutest du das nur?

    0
Anmelden zum Antworten