Set aller Indices der gesetzten Bits in einem int



  • Ich benötige ein Set aller Indices der gesetzten Bits in einem int.

    Beispiel:

    0100 1001 => 1, 4, 7 (oder gern auch 0, 3, 6)

    Gibt es da effiziente Implementierungen?

    Edit: Hintergrund ist collision detection. Stellt euch vielleicht das Snake-Spiel mit vielen Schlangen vor und nun will ich erkennen welche Schlangen gerade kollidieren. Da ich nicht pro Feld ein List-Objekt anlegen möchte, kodiere ich die "Schlangen" in einen long und möchte nun quasi aus meiner List<Schlange> diejenigen die kollidieren beziehen - Index in der Liste == Bit-Index.

    MfG SideWinder



  • Du könntest ein switch auf jedes byte machen. Aber ob das wirklich effizienter ist als einfach jedes bit durchzugehen? Ansonsten poste doch mal ein paar Zeilen Code die man dann beschleunigen soll.



  • Spontan fällt mir keine andere Methode ein als:

    std::list<Schlange> kollidierendeSchlangen; // ggf. Pointer auf Schlange
    for (std::list<Schlange>::iterator sIt = schlangenListe.begin(); sIt != schlangenListe.end(); ++sIt)
        if ((*sIt)&bitMaske)
            kollidierendeSchlangen.push_back(*sIt);
    


  • Bereiche (Bytes, Nibbles, was auch immer) rausmaskieren und dann in einem LUT nachgucken ist wohl die naheliegendste Lösung.

    Ansonsten könnte man noch inline Assembler verwenden - die meisten CPUs haben Befehle ala "gib mir die Nummer des höchsten gesetzten Bits".


Log in to reply