schnellerer Algorithmus

Hey,
ich bin gerade dabei, ein Programm zu schreiben, das Zahlen aus dem Dezimalsystem in Zahlen des 7er Systems umwandeln soll. Ich habe bereits folgendens:

int Class::dec_sep(int dec){
    std::string sep="";
    while(dec!=0){
        std::stringstream out;
        out<<dec%7;
        sep=out.str()+sep;
        dec/=7;
    }
    return atoi(sep.c_str());
}

Nun will ich aber sehr viele Zahlen hintereinander umwandeln und mit dieser Funktion dauert das ewig. Gibt es eine Möglichkeit, das effizienter zu programmieren?
Grüße

volkard

Vielleicht solltest Du nicht vom 10-er-System ins 7-er-System wandeln, sondern vom 1000-er-System ins 2401-er-System.
Die Zahl im 7-er System gibst Du in einem int zurück, komisch, hätte mir kaum was anderes als char[13] denken können. Oder meinetwegen string.

cooky451

Ok, das ist die sinnloseste Funktion die ich je gesehen hab

Zsar

Mmh... da die Zahlen ja doch dual gespeichert werden, frage ich mich:
Warum überhaupt irgendetwas umwandeln?

Wäre es nicht einfacher, eine Funktion zu schreiben, die aus deinen Ganzzahlen bei Bedarf (d.h. string-Ausgaben - und nur dort) 7-adige ASCII-Symbolketten bilden?

So habe ich es zumindest gemacht, als ich char-Werte als Bitfolgen ausgeben wollte:

char * bits(const char wert)
{
  char * bitfolge = new char[sizeof(char) * 8 + 1];

  for(unsigned char z = 0; z < sizeof(char) * 8; z++)
  {
    wert = wert << z;
    wert = wert >> (sizeof(char) * 8 - 1);
    wert ? bitfolge[z] = '1' : bitfolge[z] = '0';
  }
  bitfolge[sizeof(char) * 8] = 0;

  return bitfolge;
}

Das Beispiel ermöglicht derlei:

cout << bits(4);

-> 00000100 auf der Konsole
Ist natürlich die einfachst mögliche Umwandlung, geht aber auch mit deinem Funktionskörper und angepasster Ausgabe.

Wenn du tatsächlich int-Werte ausgeben möchtest, macht das doch nur Umstände, weil du bei jeder Rechnung neu mappen musst (6₇ + 1₇ ergibt ja trotzdem nicht 10₇, so du die Operatoren nicht angreifst).
Lieber nur einmal am Ende umrechnen, und dann kann's doch eigentlich nur zu Ausgabezwecken dienen, oder?
Es wäre für Rat hier schon relevant, was du denn mit den 7-adischen Werten anfangen möchtest, bzw. wo und wie sie zum Einsatz kommen sollen.

volkard

char * bits(const char wert)//const unnötig
{
  char * bitfolge = new char[sizeof(char) * 8 + 1];//sizeof(char) ist immer 1

  for(unsigned char z = 0; z < sizeof(char) * 8; z++)//zum zählen int nehmen
  {
    wert = wert << z;//seltsame 
    wert = wert >> (sizeof(char) * 8 - 1);//bitextraktion
    wert ? bitfolge[z] = '1' : bitfolge[z] = '0';
  }
  bitfolge[sizeof(char) * 8] = 0;

  return bitfolge;
}

Zsar

Na nun, dass es sehr elegant wäre, habe ich nicht behauptet.
Wollte nur bitweises Auslesen zum Zwecke einer unüblichen Formatierung demonstrieren, bzw. bei der Erstellung des Codes die Aufgabe an sich gelöst haben.

... Nun ist allerdings meine Neugier geweckt, was an der Bitextration so seltsam sein soll - ist eine von nur zwei Möglichkeiten, die mir spontan in den Sinn kommen,
die andere wäre bitweises und-Verknüpfen mit 2^z und Wahrheitswert prüfen.
Sollte das etwa weit besser sein, als zweimaliges Verschieben?

for(unsigned char z = 1, i = 0; z != 0; z = z << 1, i++)
{
  (wert & z) ? bitfolge[i] = '1' : bitfolge[i] = '0';
}

Sieht nicht unbedingt besser aus - gut, das i kann man noch herauskürzen (ich komme nur gerade nicht darauf), aber selbst dann...

Nachtrag:
Das i wird man per Logarithmus los: i = log₂z. Bäh!

volkard schrieb:

Vielleicht solltest Du nicht vom 10-er-System ins 7-er-System wandeln, sondern vom 1000-er-System ins 2401-er-System.

Stimmt, da gab's irgendeinen Trick. Wie kommst du auf 10^3 vs 7^4? Beliebig wirst du das ja nicht gewählt haben?

volkard

nicht Gaast schrieb:

Wie kommst du auf 10^3 vs 7^4? Beliebig wirst du das ja nicht gewählt haben?

Klein genug, daß man an eine Look-Up-Tabelle denken könnte. Aber eher geraten, hab's noch nie mit Tabelle ausprobiert.

volkard

LordZsar1 schrieb:

die andere wäre bitweises und-Verknüpfen mit 2^z und Wahrheitswert prüfen.

Ich denke, es gibt da sehr viele Möglichkeiten.
"seltsam" war Deine, weil ich gleich gesehen hatte, daß die so nicht klappt. Falsch, ich konnte nicht gleich sehen, daß es so klappt. Das kam mir spanisch vor.
Eine mögliche Reparatur ginge so

char * bits(const char owert)
{
    char * bitfolge = new char[sizeof(char) * 8 + 1];

    for(unsigned char z = 0; z < sizeof(char) * 8; z++)
    {
        char wert=owert;
        wert = wert << z;
        wert = wert >> (sizeof(char) * 8 - 1);
        wert ? bitfolge[z] = '1' : bitfolge[z] = '0';
    }
    bitfolge[sizeof(char) * 8] = 0;

    return bitfolge;
}

aber dann drängt sich sofort sowas

char * bits(const char owert)
{
    char * bitfolge = new char[sizeof(char) * 8 + 1];

    char wert=owert;
    for(unsigned char z = 0; z < sizeof(char) * 8; z++)
    {
        wert & 128 ? bitfolge[z] = '1' : bitfolge[z] = '0';
        wert = wert << 1;
    }
    bitfolge[sizeof(char) * 8] = 0;

    return bitfolge;
}

auf.

Aber spaßig wird's erst mit der 7 als Basis.

Werner Salomon

Bleibt noch zu erwähnen, wie man den Algorithmus in den ostream rein bekommt, damit die Zahlen auch ausgegeben werden. Da der 'num_put' lange nicht dran war - hier noch mal komplett:

#include <iostream>
#include <locale>
#include <cassert>

template< int Base, typename E, typename Out, typename I >
Out put_number( Out out, I x )
{
    assert( x >= 0 );
    const I digit = x % Base;
    if( (x /= Base) != I(0) )
        out = put_number< Base, E >( out, x );
    *out++ = E( (digit < 10? '0': 'a' - 10) + digit );
    return out;
}

template< int Base, typename E >
class UserBase : public std::num_put< E >
{
protected:
    virtual iter_type do_put( iter_type out, std::ios_base& str, char_type fill, long val ) const
    {
        if( str.flags() & std::ios_base::basefield )
            return std::num_put< E >::do_put( out, str, fill, val );
        if( val < 0 )
        {
            *out++ = '-';
            val = -val;
        }
        out = put_number< Base, E >( out, val );
        if( out.failed() )
            str.setstate( std::ios_base::failbit );
        return out;
    }
};
template< int Base, typename E, typename Traits >
void imbue_base( std::basic_ostream< E, Traits >& out )
{
    out.imbue( std::locale( out.getloc(), new UserBase< Base, E > ) );
}
template< typename E, typename Traits >
std::basic_ostream< E, Traits >& user_base( std::basic_ostream< E, Traits >& str )
{
    str.unsetf( std::ios_base::basefield );
    return str;
}

int main()
{
    using namespace std;
    imbue_base< 7 >( cout ); // ab jetzt können Zahlen auf cout zur Basis7 ausgegeben werden
    for( int i = 14; i < 36; ++i ) // Demo
        cout << dec << i << " = " << user_base << i << "_sieben" << endl;
    return 0;
}

Gruß
Werner