Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Bits zählen


BenBE - Mi 08.04.09 15:00
Titel: Bits zählen
Bei der Arbeit mit Mikrocontrollern hat man öfters mal die Aufgabe Bits in einer Zahl zu zählen, die ungleich 0 sind. Zu beachten ist hierbei, dass viele Controller Bitshifts immer nur um eine Stelle können, also man nicht beliebig Bitmasken umherschieben sollte.

Der einfachste Algorithmus hierfür ist sicherlich, um die Anzahl der Bits nach Rechts zu verschieben und bei jedem Schleifendurchlauf auf Gerade\Ungerade zu prüfen und ggf. zu addieren.

Kennt jemand einen effizienteren Algorithmus, der mit möglichst wenigen Shifts auskommt? RAM-Verbrauch sollte auch minimal sein (jedes Byte ist eines zu viel). Es darf angenommen werden, dass die zu untersuchende Zahl "kostenlos" als Einzelbytes betrachtet werden darf. Schleifen und Rekursion sollte vermieden werden.

Der Prozessor: Registergröße egal, 4 Register der Standard-Größe der CPU seien vorausgesetzt
Die Zahl: 32 bzw. 64 Bit. Allgemeine Lösungen bekommen Pluspunkte ;-)


der organist - Mi 08.04.09 15:04

du bekommst also eine Zahl (als Integer?) und sollst in der Binärform die gesetzten Bits zählen?


Horst_H - Mi 08.04.09 15:12

Hallo,

multiplizieren mit z.B 16 ist auch shiften. (ATmega hat ja Mul-Befehl in 2 Takten)
Was kann die CPU?

Gruß Horst


Gammatester - Mi 08.04.09 16:11

Bei Aggregate Magic Algorithms [http://aggregate.org/MAGIC/#Population%20Count%20(Ones%20Count)] oder Bit Twiddling Hacks [http://graphics.stanford.edu/~seander/bithacks.html] oder auf der Seite zum hervoragenden Buch http://www.hackersdelight.org/ findest Du jede Menge von 'Population count'-Algorithmen. Kommt auf die Resourcen an, ich selbst benutze zB Lookup-Tabellen für Bytes.

Gammatester


Muck - Mi 08.04.09 21:08

Hallo,

mag sein, dass dieser ansatz nicht wirklich hilft, da mehr zufaellig. Na ja, ich poste es mal trotzdem... Je kleiner die zahl desto weniger shifts


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure TForm2.Button1Click(Sender: TObject);
var X:Integer;
begin
x:=18;
asm
  mov eax,x;
  xor ecx,ecx;
  @Mehr:shr eax,1;
  jnc @Nee;
  Inc ecx;
  @Nee:cmp eax,0;
  jne @Mehr;
  mov x,ecx;
end;
Button1.Caption:=IntToStr(X);
end;


Markus

Moderiert von user profile iconNarses: Code- durch Delphi-Tags ersetzt


BenBE - Mi 08.04.09 22:11

user profile iconMuck hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

mag sein, dass dieser ansatz nicht wirklich hilft, da mehr zufaellig. Na ja, ich poste es mal trotzdem... Je kleiner die zahl desto weniger shifts


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
procedure TForm2.Button1Click(Sender: TObject);
var X:Integer;
begin
  x:=18;
  asm
    mov eax,x
    xor ecx,ecx

@Mehr:
    shr eax,1
    jnc @Nee

    Inc ecx
    test eax, eax
@Nee:
    jnz @Mehr

    mov x,ecx
  end;
  Button1.Caption:=IntToStr(X);
end;


Markus


Ich hab bei Dir zwar noch ein wenig was optimiert, aber der Verstoß gegen "Schleifen vermeiden" ist trotzdem da.

Da gefallen mir die Möglichkeiten mit den Bitmustern zu zählen schon besser (weil log(N) statt Worstcase linear.

Mikrocontroller sind meist 8 oder 16 Bit, müsste man also mal schauen, dass man die 32-Bit-Logik-Befehle runterbricht, das denk ich, sollte aber nicht weiter problematisch sein, ich poste morgen mal eine Implementation für 16 Bit, die den Akkumulations-Algorithmus nutzt.


Horst_H - Mi 08.04.09 23:15

Hallo,

Dein Code springt mehr zu sehr nach nee und mehr.


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
    asm
     CLC
     MOV  EAX,$AAAA5555//Testzahl 
     XOR  EDX,EDX        //Zaehler der gesetzten Bit

@Zaehle:
     ADC  EDX,0
     ADD  EAX,EAX  //EDIT schneller als shl EAX,1 auf Athlon64
     JNZ  @Zaehle  //Durchläufe = 32- Position des ersten gesetzen Bits von rechts (BSR)

     ADC  EDX,0

     MOV DWORD PTR [i],EDX
    end;

Das braucht 2 Befehle + 1 sprung
Die Variante-Kernighan [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan] v &= v-1 ist zwar interessant, aber braucht auch ein Register für v-1 und zwei Befehle innerhalb der Schleife mehr, aber kein shift.

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
     asm
     MOV  EAX,$AAAA5555//DWORD PTR [j]
     XOR  EDX,EDX
     TEST EAX,EAX
     JZ   @Fertig

@Zaehle0:
     INC  EDX
     MOV  EDI,EAX
     DEC  EDI
     AND  EAX,EDI
     JNZ  @Zaehle0 //Durchläufe = Anzahl gesetzter Bits
@Fertig:

     MOV DWORD PTR [i],EDX
    end;

Das braucht 4 Befehle + 1 Sprung, aber die Schleifendurchläufe im Mittel "gefühlt wahrscheinlich" ;-) geringer.

Mir ist trotzdem nicht klar ob multiplizieren erlaubt ist oder nicht.

Gruß Horst


pesi - Do 09.04.09 11:02

Hallöchen,
wie wär´s mal mit einem ganz anderen (vermutlich eher laienhaften) Ansatz!?
Ich habe mal folgende Funktion gegoogelt:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
function TForm1.IntToBin2(d: Longint): string;
var
  x, p: Integer;
  bin: string;
begin
  bin := '';
  for x := 1 to 8 * SizeOf(d) do
  begin
    if Odd(d) then bin := '1' + bin
    else
      bin := '0' + bin;
    d := d shr 1;
  end;
  Delete(bin, 18 * ((Pos('1', bin) - 1div 8));
  Result := bin;
end;


Zurückgegeben wird ein String wie z.B. "00101110001101".
In einem String die Einser zu zählen solltest Du dann vermutlich noch hinbekommen :-)

Gruß Peter

Moderiert von user profile iconKha: Delphi-Tags hinzugefügt


BenBE - Do 09.04.09 11:03

Ich muss doch hoffentlich auf diesen letzten Vorschlag nicht näher eingehen??? :mrgreen: Außerdem geht es hier um "effiziente" Algorithmen, da fallen Strings GANZ selten als Mittel zum Zweck rein :P


pesi - Do 09.04.09 11:33

Oh Gott oh gott oh gott.......
Was hab ich denn da von mir gegeben....
SORRY!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Das das in DIESEM Forum hier zu histerischen Lachanfällen führt ist mir JETZT auch klar.
Nix für ungut!


delfiphan - Do 09.04.09 17:44

Stichwort: Population Count / Hamming weight

Branchless O(log(n)) implementation
http://www.df.lth.se/~john_e/gems/gem002d.html

Soweit ich weiss gibt es i.A. keinen schnelleren bekannten Algorithmus (mit besserem worst-case Verhalten).

Weitere:
http://www.delphi-forum.de/viewtopic.php?t=74678
http://en.wikipedia.org/wiki/Hamming_weight


Reinhard Kern - Fr 10.04.09 10:30

user profile icondelfiphan hat folgendes geschrieben Zum zitierten Posting springen:
Stichwort: Population Count / Hamming weight

Branchless O(log(n)) implementation
http://www.df.lth.se/~john_e/gems/gem002d.html

Soweit ich weiss gibt es i.A. keinen schnelleren bekannten Algorithmus (mit besserem worst-case Verhalten).

Weitere:
http://www.delphi-forum.de/viewtopic.php?t=74678
http://en.wikipedia.org/wiki/Hamming_weight


Hi,

heutige CPUs haben zwar vielleicht wenig RAM, aber meistens mehr als genug ROM, ich würde daher für 1 Byte die 256 Byte lange Tabelle mit Anzahl der Einsen aufstellen (muss ich nicht selbst, geht auch mit Repeat und Macro), dann reduziert sich das "Programm" auf einen einzigen indizierten ROM-Zugriff. Und bei einem Doppelwort sind es halt 4 plus Addition.

Gruss Reinhard


delfiphan - Fr 10.04.09 21:35

Ich denke es ist genau umgekehrt: Lieber einen Memoryzugriff weniger und dafür einen Rechenschritt mehr. Aber bei BenBE geht es nicht um PC Prozessoren. Darum kann ich nichts dazu sagen, welche Implementation am besten ist.


BenBE - Fr 10.04.09 22:07

Naja, wie ich oben bereits schrieb, geht es darum, mit möglichst wenig Speicher auszukommen. eine 32-Bit-Zahl bekomm ich in 2 16-Bit-Register der CPU; das wäre also nicht das ding, da ich mit den anderen 2 die Lookups und Additionen machen könnte. Da aber der Memory möglichst gering gehalten werden soll fällt die Lösung mit der Lookup-Table in der größe flach.


Reinhard Kern - Sa 11.04.09 01:05

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Naja, wie ich oben bereits schrieb, geht es darum, mit möglichst wenig Speicher auszukommen. eine 32-Bit-Zahl bekomm ich in 2 16-Bit-Register der CPU; das wäre also nicht das ding, da ich mit den anderen 2 die Lookups und Additionen machen könnte. Da aber der Memory möglichst gering gehalten werden soll fällt die Lösung mit der Lookup-Table in der größe flach.


Hallo,

das ist zu einfach gedacht - 32 bit heisst 4 mal in einer 256-Byte Tabelle nachsehen und aufaddieren, selbstverständlich arbeitet man nicht mit einer 32bit-Tabelle mit 4 Milliarden Einträgen. Ist wohl kaum zu schlagen, ausserdem könnte man auch 8mal in einer 16Byte-Tabelle nachsehen. Aber es lohnt sich nicht hier wegen solcher Nebensächlichkeiten zu streiten, ich zwinge ja niemandem eine Lösung auf, ich verwende sie nur selber.

Gruss Reinhard


Horst_H - So 12.04.09 16:36

Hallo,

ist das Thema jetzt beantwortet?
Wieso sollen keine Schleifen verwendet werden, wenn es um das sparen von Speicherplatz geht, verstehe ich diese Vorgabe garnicht.

Gruß Hosrt


BenBE - So 12.04.09 17:06

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

ist das Thema jetzt beantwortet?

Ja, ist beantwortet, hab schon den Fragenstatus angepasst.

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Wieso sollen keine Schleifen verwendet werden, wenn es um das sparen von Speicherplatz geht, verstehe ich diese Vorgabe garnicht.

Gruß Hosrt

Warum keine Lookup-Tables: Auf einem Microcontroller sind Lookup-Tables zwar von der Performance meist eine bessere Wahl in Bezug auf die Anzahl der Befehle, jedoch wird damit unnötig viel RAM\ROM statisch verschwendet. Da aber diese beiden Ressourcen auf einem Controller meist sehr knapp bemessen sind, kann dies in manchen Fällen ein K.O.-Kriterium sein. Daher hier die Vermeidung.

Das Kriterium keine Schleifen kommt aus einem ähnlichen Grund zum Tragen: Jede Schleife kann als Komplexität N (oder zumindest aber logN aufgefasst werden. Zudem haben Schleifen auf Superskalaren CPUs den entscheidenden Nachteil, dass bei einem Fehlschlag der Branch Prediction man eine ganze Menge Performance verliert. Daher habe ich Schleifen auch ausgeklammert. Ausnahmen bilden hier Schleifen, bei denen ein manuelles Loop Unrolling überschaubar ist. Hier können die Sprünge vermieden und damit dieses Performance Penalty vermieden werden.

Gruß,
BenBE.


Horst_H - Mi 15.04.09 15:57

Hallo,

und jetzt willst Du uns dumm sterben lassen.....

Gruß Horst


BenBE - Mi 15.04.09 19:46

Eigentlich wollt ich das Controller-Unabhängig klären (steht auch immer noch im Vordergrund), aber wer's wirklich konkret wissen möchte: Zielplattformen sind MSP430-Mikrocontroller bzw. ARM9-Controller. Gern bin ich aber auch an Lösungen für x86\x64 offen. (Generische haben wir ja bereits geklärt).