Zahl mit einer Liste von Bit-Masken abgleichen



  • Hallo zusammen,

    ich suche eine Möglichkeit, den folgenden Code besser darzustellen (Laufzeit-Optimierung). Es wird geprüft, ob eine Bit-Maske der Liste in der Zahl x enthalten ist. Hat jemand da vllt. eine Idee??

    bool contains(int x, int* list) {
    	for(i=0;i<LISTSIZE;i++)
    		if( (x & list[x]) == list[x])
    			return true;
    	return false;
    }
    

    Für Anregungen bin ich sehr dankbar!

    Liebe Grüße

    Hendrik



  • Hallo nochmal,

    der obere Code ist natürlich falsch, ich meinte:

    bool contains(int x, int* list) {
    	for(i=0;i<LISTSIZE;i++)
    		if( (x & list[i]) == list[i])
    			return true;
    	return false;
    }
    

    Liebe Grüße

    Hendrik



  • Je nach Datenlage. Du würdest nicht fragen, wenn die Listen weniger als 1000 Elemente hätten.
    Also: Die Listen anders darstellen. Wo haben wir eine relle Chance, eine Vorauswahl hinzukriegen? popcount, hashen, bitweiser Binärbaum? Ich denke an einen bitweisen Baum, der so gebaut ist, daß anhand des ersten gesetzten Bits getrennt wird. LISTSIZE klingt danach, als könne man sich viel Vorverarbeitung leisten.

    bool contains(int x, Node* n) {
        if(n==nullptr) return false;
        if((x&n->mask)==x) return true;
        int fb=getFirstBitSet(x);
        return contains(x,n->childs[fb]);
    }
    

    Oder vielleicht doch nur nach gesetzten Bits trennen.

    bool contains(int x, int bitpos, Node* n) {
        if(n==nullptr) return false;
        if((x&n->mask)==x) return true;
        if((x>>bitpos)==1)
           return contains(x,bitpos+1,n->child1);
        else
           return contains(x,bitpos+1,n->child1);
    
    }
    


  • Oder die Standardbibliothek nutzen und alle Bitmasken in eine std::set werfen.


Log in to reply