bitwise mirror

Lui

Hi,

ich möchte ID Values generieren, die dann einem Baum füttern, nur wenn ich da einfach raufzähl, kann ich den Baum auch gleich wieder weghaun.

Ah, da war doch was, aufsteigende zahl hernehmen und bitweise spiegeln ... tja, nur wie mach ich das. Da muss doch irgend einen Schmäh geben mit dem das einfach geht. Ansonst wird das ein echt grausliches Statement
Wie lernt man das in AlgoDat, da wird das doch erwähnt nehm ich an?

Hab jetzt auf die schnelle nichts dazu gefunden, weiß aber auch ned wie man das korrekt bezeichnet was ich such.

Evtl auch andere Vorschläge?

lg Lui

ThomasW

Jetzt mal so aus dem Bauch heraus und ohne zu testen würde ich das so machen:

PHP

unsigned int mirror (unsigned int v)
{
    unsigned int r = 0;
    int i;


    for (i = 0; i < 32; i++) {
        r = r | (((v>>i)&1)<<(31-i));
    }
    return r;
}

Alles anzeigen

Plantschkuh!

Zitat von Lui

Ah, da war doch was, aufsteigende zahl hernehmen und bitweise spiegeln ...

So kriegst du zwei ineinander verschachtelte, monoton steigende Folgen. Was soll das bringen außer Umständen?

Zitat

Wie lernt man das in AlgoDat, da wird das doch erwähnt nehm ich an?

Nö. Selber nicht AlgoDat besucht?

Zitat

Evtl auch andere Vorschläge?

Balancierter Baum, pseudozufällige IDs.

Lui

@Plantschkuh
Angeblich wenn man einen Baum damit befüllt ist der ausgewohgen, anderen Falls hat man ned mehr als ne List. Wenn das spiegeln auch nix bringt wär das blöd. Bin bin mir ziemlich sicher, dass ich das mal so gelernt hab.
Edit:AlgoDat nicht hier auf der Uni.

ThomasW
Einfach bit für bit aufsummieren, ja das ist das erste was man machen kann wenn mans mal irgendwie macht. Evtl is da aber wirklich schneller einfach zufällige IDs zu nehmen, hm.

Wie macht man das normalerweise, bei Datenbanken oder so?

Ich möchte eben ned std::string statt integer nehmen, obwohl so schlimm kann das ja ned sein.

Plantschkuh!

Zitat von Lui

Wenn das spiegeln auch nix bringt wär das blöd. Bin bin mir ziemlich sicher, dass ich das mal so gelernt hab.

Kann schon sein. Meine Aussage mit den beiden monoton steigenden Folgen ist uebrigens falsch, wie ich danach draufgekommen bin. Bin trotzdem skeptisch, aber wenn du das gelernt hast, wirds schon so sein. Kann man ja auch mit einem balancierten Baum kombinieren, wenn man moechte.

Zitat

Einfach bit für bit aufsummieren, ja das ist das erste was man machen kann wenn mans mal irgendwie macht.

Das koennte schneller sein: http://graphics.stanford.edu/~seander/bitha…ReverseParallel

Lui

Yeah! "Bit Twiddling Hacks" :bounce:
Das gfallt ma, genau sowas hab ich gsucht, thx

Heutzutage verwendet man aber wahrscheinlich sowieso nur noch AVL trees.

Ich hab das jetzt gestern aber schon irgendwie anders gmacht. Da ich die Objekte sowieso mit einem Namen registriere, verwende ich jetzt einfach strings. Intern wollte ich aber dann nur noch die generierten IDs verwenden, weils natürlich schneller is, die Abfragen sollten aber eh ned an performancekritischen Stellen sein.
Ich bild mir halt solche Sachen immer ein, kann sowas immer nur mit meinem Gewissen vereinbaren sofern das effizient oder elegant ist und mich hat das schon irgendwie gewundert das man die bits ned irgendwie gschwind umdrehn kann

Maximilian Rupp 27. Dezember 2024 um 12:04