Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
13.04.2007, 16:35 Uhr
Matthias Fischer

hallo leute!

hab ein riesen-problem!!! ich hab die letzten tage damit verbracht ein programm zu schreiben, welches bits einer 64-bit zahl vertauscht! es gibt ein array mit 64 elementen (=Permutationstabelle), die indexe geben das quell-bit an und die inhalte der indexe geben an, wo sich das jeweilige bit dann befinden soll...d.h. perm_tabelle[5] = 10 würde heißen, dass das 5.bit der originalzahl an die 10 position der ergebniszahl wandern soll.
ich muss das demnächst abgeben und bin absolut ratlos und verzweifelt!
es funktioniert eigentlich nichts...hat jemand schon mal sowas gemacht und könnts mir erklären? das problem ist auch, dass wir es mit dem "<<" - Operator lösen sollen!

danke schon mal und hoffentlich ist jemand dabei der sich mit sowas auskennt...

lg
Matthias

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
13.04.2007, 18:24 Uhr
0xdeadbeef
Gott
(Operator)

Ich würd das vielleicht nicht direkt Permutation nennen, aber egal - die Aufgabenstellung ist simpel genug. Zeig mal deinen Ansatz her und wos damit Probleme gibt - nen Hausaufgabenservice betreiben wir hier nämlich nicht.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
13.04.2007, 19:14 Uhr
~Matthias Fischer
Gast

Das ist mir natürlich klar, sorry! ...was ich bis jetzt habe ist, dass ich das bit der originalzahl sowie das bit der ergebniszahl rausfiltere. Nun muss ich das bit der originalzahl durch das bit der ergebniszahl ersetzen und das ist mein Problem, wie könnt ich das machen? das bit der originalzahl sollt dann noch auf 0 gesetzt werden...
obwohl ich eigentlich net schlecht programmieren kann, habe ich irgendwie das mit dem bit-shiften überhaupt nicht drauf...

Ok, hier also mein Lösungsansatz:

C++:

#include <iostream>

#define BUFFER 64

using std:: cout;
using std:: endl;

class Permutator
{
   public:
                int perm_[BUFFER];

        Permutator (int perm[]);
        ~Permutator (void);

        long long permute (long long orig_num);
};

Permutator::Permutator (int perm[])
{
    for (int n = 0; n < BUFFER; n++)
      perm_[n] = perm[n];
}

Permutator::~Permutator (void){
}

long long Permutator::permute (long long orig_num)
{
    long long result = 0;
    bool bit_orig;

    result = orig_num;

    for (int n = 0; n < BUFFER; n++)
    {
    bit_orig = result & (bit << n);

        result = result & (result << perm_[n]);
    }

    return (result);
}

int main (int argc, char *argv[])
{
   int perm[BUFFER];
   long long orig_num = 255;
   long long erg_num;

   /* Füllen des Arrays mit Werten (Permutationstabelle) */
   for (int n = 0; n < BUFFER; n++)
      perm[n] = (BUFFER - 1) - n;

   Permutator permut = Permutator (perm);

   erg_num = permut.permute (orig_num);

   cout << "Original-Number: " << orig_num << endl;
   cout << "Ergebnis-Number: " << erg_num << endl;

   return (0);
}

hoffe, ihr versteht was ich da mache, jeder hat halt seinen eigenen programmierstiel

danke!

Bearbeitung von 0xdeadbeef:

cpp-tags eingefügt. Nächstes mal selbst machen.

Dieser Post wurde am 13.04.2007 um 19:29 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
13.04.2007, 19:38 Uhr
0xdeadbeef
Gott
(Operator)

Hmm. Ja, ich seh schon, wo das schiefgeht. Hier:

C++:

for (int n = 0; n < BUFFER; n++)
{
bit_orig = result & (bit << n);

result = result & (result << perm_[n]);
}

Warum bit_orig was zuweisen, wenns dann nachher garnicht benutzt wird? Außerdem - das in-place zu machen ist wahrscheinlich etwas ungünstig, und ich glaube, dir ist nicht ganz klar, was der bitshift-Operator macht. Nimm an, du hast einen 8-bit-Integer x, indem das Bitmuster

Code:

0001000

steht. Dann ist

Code:

0001010 = x
0010100 = x << 1
0101000 = x << 2
0000101 = x >> 1
0000010 = x >> 2

Dementsprechend halte ich etwa so einen Ansatz für sinnvoll:

C++:

result = 0;

for(int n = 0; n < BUFFER; ++n) {
bit_orig = (orig_number >> n) & 1;
result |= bit_orig << perm_[n];
}

...wobei bit_orig hier wahrscheinlich (code ungetestet) ein long long sein muss, weil ein bool nicht breit genug für die Verschiebung ist. Oder halt gleich in einer Zeile

C++:

result |= ((orig_number >> n) & 1) << perm_[n];

Und ja, einige der Klammern sind überflüssig.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
13.04.2007, 20:01 Uhr
~Matthias Fischer
Gast

Danke für deine Hilfe! Werd mir deine Lösung mal anschaun und probiern!!

Naja, eigentlich weiß ich schon was der Bit-Operator macht und zwar Bits nach rechts oder links verschieben um eine gewisse anzahl an bits, nur in dem Beispiel tu ich mich irgendwie schwer anzuwenden....

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
13.04.2007, 20:29 Uhr
~Matthias Fischer
Gast

Ok, das programm funzt!!! danke dir erstmal!!!!!!! ich hab noch ein paar fragen morgen, hoffe ich darf deine hilfe nochmal in anspruch nehmen?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
13.04.2007, 21:31 Uhr
0xdeadbeef
Gott
(Operator)

Wenn ich dann Zeit und Bock hab, klar.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
14.04.2007, 13:47 Uhr
~Matthias Fischer
Gast

Hallo!

Ich hoff du hast nochmal Zeit und Bock

Zwei Sachen wären noch:

1) Wenn ein Wert im Array -1 ist, dann soll das bit weggelassen und nicht in in die ergebniszahl übernommen werden...das hab ich mal gemacht...könntest dir das bitte anschaun ob du es auch so gemacht hättest?

C++:

for (int n = 0; n < BUFFER; n++)
    {
            if(perm_[i] == -1)
                perm_[i] = i;

            else
                perm_[i] = perm_[i];

        src = (orig_num >> n) & 1;
             dest =    src << perm_[n];
           result = result | dest;
    }

2) Wir sollen sicherstellen dass long long auch wirklich 64Bit lang ist...wie mach ich denn bitteschön dass??? ja mit sizeof() die länge ermitteln und wie gehts dann weiter???

Bearbeitung von 0xdeadbeef:

Strike 2. cpp-tags in Zukunft selbst einfügen. Da gibts auf der linken Seite so hübsche Shortcuts, die man verwenden kann, das ist wirklich nicht so schwer.

Dieser Post wurde am 14.04.2007 um 17:27 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
14.04.2007, 17:32 Uhr
0xdeadbeef
Gott
(Operator)

Wenns einfach um weglassen geht,

C++:

if(perm_[n] == -1)
continue;

Sicherstellen, dass long long 64 bit lang ist...in C wärs einfach,

C++:

#include <stdint.h>

// ...

int64_t x;

aber C++ kennt die Typen vom Standard her noch nicht. Auf der anderen Seite kennt C++ technisch gesehen auch long long nicht, von daher dürfte sich das aufheben. (Merke: In C++0x wird der header cstdint und der Typ std::int64_t sein, wie bei C-compat-headern üblich)

Wenns nur darum geht, die Länge festzustellen und ggf. drauf zu reagierren - 64 bit = 8 byte, also

C++:

int main() {
  if(sizeof(long long) != 8) {
    std::cout << "long long ist nicht 64 bit breit" << std::endl;
    return -1;
  }

  // ...
}

...oder, man könnte klug rangehen und

C++:

#define BUFFER (sizeof(long long) * 8)

schreiben, dann passt alles zusammen, aber es kann u.U. auch mal mehr als 64 bit sein.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 14.04.2007 um 17:33 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
14.04.2007, 18:59 Uhr
Matthias Fischer

DANKE für deinen Beistand!!

Das mit den cpp-tags werd ich selbstverständlich in zukunft berücksichtigen!

C++:

#define BUFFER (sizeof(long long) * 8)

die zeile ist mir nicht ganz klar...was ist, wenn long long 4 byte groß ist, dann wär der Buffer grade mal 32 groß -> 32 elemente im array statt 64!

anscheinend ist mir das mit dem bit-shiften doch noch nicht ganz klar...hab wiest schon gesehen hast deinen einzeiler auf 3 zeilen aufgeteilt und mir überlegt was jede zeile macht, aber ich hab da irgendwie noch probleme das zu verstehen...
btw: funktioniert dein einzeiler auch mit zufälligen werten im array?

C++:

src = (orig_num >> n) & 1;

hier schiebst du die bits um die position n nach rechts und machst ne &-verknüpfung mit 1...hm, wieso eigentlich von links anfangen, das LSB-Bit steht doch rechts? und für was brauch ich die &-verknüpfung da genau? nehemn wir an wir haben die zahl 128 = 1000 0000 und n ist 2, dann würde das heißen der 1er würde um 2 stellen nach rechts geschoben werden, also befindet sich der 1er auf

0010 0000
0000 0001 mit 1 UND-verknüpft würder das ergeben
-----------
0000 0000 -> wieso dieser schritt und steht dann in src 0 drinnen?

C++:

dest = src << perm_[n];

und hier schiebst du das bit von src um den inhalt von perm_[n] nach links (wieso auf einmal nach links?)...in dest müsste sich dann das src-bit befinden oder?

C++:

result = result | dest;

diese OR-verknüpfung ist mir auch net ganz klar...

ach ja, wenn ich BUFFER auf 64 setz und ich die zahl 255 hab, dann kommt irgendwie ein blödsinn raus beim shiften...irgendwas mit -934783274342384...

ich weiß ich nerv, aber es wär wirkli super wennst ma des BITTE nochmal in ruhe erklären könntest

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: