3. Algorithmus fürs Bitweise "Zählen" gesucht

Algorithmus fürs Bitweise "Zählen" gesucht

  • ?

    Hi liebe Community,
    Zerbreche mir gerade den Kopf bei der suche nach einen Algorithmus, der elegant und constexpr ist:
    Er soll folgendermaßen N bits "abzählen" bzw. setzen, ich gebe ein bespiel an dadurch sollte es sofort klar werden :

    N=5

I => Result
0 => 0b00000
1 => 0b00001
2 => 0b00010
...
5 => 0b10000
6 => 0b00011
7 => 0b00101
...
10=> 0b00110
11=> 0b01010
...
16=> 0b00111
17=> 0b01011
...
31=> 0b11111

    Hat jemand eine Idee wie man dies berechnen könnte, außer durch stupides rekursives "abzählen"?
    Rekursives abzählen möchte ich nämlich um jeden Preis vermeiden, da sonst die Kompilierungszeit in die höhe schiest, brauche dies aber zur Implementierung von diversen Expression Templates zur Konstruktion einer bestimmten Algebra

    Gruß FuriousByte

    0
  • 3

    Nö sorry, deinen Algorithmus versteh ich nicht.

    0
  • ?

    Man beginnt mit einer "1", von rechts nach links zu wandern bis man das N-te Bit erreicht hat, anschliesend, lässt man die "1" beim 1.ten bit und lässt eine zweite "1" vom 2. bis zum N-ten bit Wandern, dann verschiebt man die erste "1" nach links und lässt die zweite "1" vom 3. bis zum N-ten Bit wandern...
    Dies tut man solange bis die erste und zweite "1" beim vor-letzten und letzten bit angelangt sind, dann nimmt man eine weitere eins hinzu...

    Jedes Bit könnte zb, einen Buchstaben representieren und man könnte nun eine Sortierung, einer speziellen Menge, der bis zu N Buchstabigen geordneten wörtern ohne Doppelte Buchstaben, vornehmen

    Beispiel :

0b11111
  EDCBA

0 => Kein Wort
Einbuchstabige wörter :
Index => Codierung => Representant 
1     =>   0b00001 =>      A
2     =>   0b00010 =>      B
3     =>   0b00100 =>      C
4     =>   0b01000 =>      D
5     =>   0b10000 =>      E
Zweibuchstabige wörter :
6     =>   0b00011 =>      BA
7     =>   0b00101 =>      CB
8     =>   0b01001 =>      DC
9     =>   0b10001 =>      ED

10    =>   0b00110 =>      CB
11    =>   0b01010 =>      DB
12    =>   0b10010 =>      EB

13    =>   0b01100 =>      DC
14    =>   0b10100 =>      EC

15    =>   0b11000 =>      ED

Drebuchstabige wörter :
16     =>   0b00111 =>      CBA
17     =>   0b01011 =>      DBA
18     =>   0b10011 =>      EBA

19     =>   0b01101 =>      DCA
20     =>   0b10101 =>      ECA

21     =>   0b11001 =>      EDA

23     =>   0b01110 =>      DCB
24     =>   0b10110 =>      ECB

25     =>   0b11100 =>      EDC

Vierbuchstabige wörter :
26     =>   0b01111 =>      DCBA
27     =>   0b10111 =>      ECBA
28     =>   0b11011 =>      EDBA
29     =>   0b11101 =>      EDCA
30     =>   0b11110 =>      EDCB
Funfbuchstabige wörter :
31     =>   0b11111 =>      EDCBA

    Hoffe mein zweiter Post ausdrucksstärker als der erste ist

    0
  • ?

    Da ist mir beim tippen ein kleiner fehler unterlaufen(ist ja schon spät/früh 😉 :

    6     =>   0b00011 =>      BA
7     =>   0b00101 =>      CA
8     =>   0b01001 =>      DA
9     =>   0b10001 =>      EA
    0
  • K

    Vielleicht kannst du erstmal nur die Zahl der gesetzten Bits zählen. Damit müsste sich wenigstens ein Interval für den gesuchten Index berechnen lassen. Die Intervallgröße ist ja auch bekannt: C(n,k), also "n über k" mit n=Gesamtzahl der Bits und k=Zahl der gesetzten Bits.

    Das müsste alles ohne brute force gehen, sagt mir mein Gefühl.

    0
  • ?

    krümelkacker schrieb:

    Vielleicht kannst du erstmal nur die Zahl der gesetzten Bits zählen. Damit müsste sich wenigstens ein Interval für den gesuchten Index berechnen lassen. Die Intervallgröße ist ja auch bekannt: C(n,k), also "n über k" mit n=Gesamtzahl der Bits und k=Zahl der gesetzten Bits.

    Das müsste alles ohne brute force gehen, sagt mir mein Gefühl.

    Danke, dass die Intervallgröße C(n,k) entspricht ist mir nicht aufgefallen;
    Ok daqs bedeutet ich muss festellen für welches x : I € [ f(x) , f(x+1) ] , gilt wobei f(x) := Sum from k= 1 to x C(n,k) ;

    ok, aber dann wird es schwierig, das Intervall weiter einzugrenzen...
    Aber selbst dann, wenn ich die genauen Intervallverschachtlung zum jeweiligen I kenne, sehe ich noch keine Möglichkeit das Bitmuster, zu ermitteln; welche Information habe ich den, dann genau?

    Nach längerem überlegen habe ich festgestellt, dass ich alternativ die inverse meiner gesuchten funktion auch ausreichen würde, das sieht für mich einfacher aus, da dies villeicht über bit-zählen zu berechnen wäre( also den Index aus dem Bitmuster), werde mich heute abend intensiver damit befassen.

    Aber je mehr ich nachdenke, desto mehr überlege ich ob Bruteforcen für mein spezielles Problem wirklich so schlecht ist, da ich sowieso 3/4 der berechneten Zuordnungen sowieso wahrscheinlich brauchen werde. Ich könnte also alles in ein Array verfrachten.
    Was denk ihr ?

    0
Anmelden zum Antworten