Autor |
Beitrag |
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mi 08.04.09 15:00
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 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
der organist
      
Beiträge: 467
Erhaltene Danke: 17
WIN 7
NQC, Basic, Delphi 2010
|
Verfasst: Mi 08.04.09 15:04
du bekommst also eine Zahl (als Integer?) und sollst in der Binärform die gesetzten Bits zählen?
_________________ »Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
      
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Mi 08.04.09 16:11
Bei Aggregate Magic Algorithms oder Bit Twiddling Hacks oder auf der Seite zum hervoragenden Buch 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
      
Beiträge: 98
Erhaltene Danke: 8
Win 8, Win 7, Vista, Win XP
Delphi XE3, Delphi 2009, Delphi 2007, Delphi 5
|
Verfasst: 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 Narses: Code- durch Delphi-Tags ersetzt
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mi 08.04.09 22:11
Muck hat folgendes geschrieben : | 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.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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; XOR EDX,EDX @Zaehle: ADC EDX,0 ADD EAX,EAX JNZ @Zaehle ADC EDX,0
MOV DWORD PTR [i],EDX end; |
Das braucht 2 Befehle + 1 sprung
Die Variante-Kernighan 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; XOR EDX,EDX TEST EAX,EAX JZ @Fertig
@Zaehle0: INC EDX MOV EDI,EAX DEC EDI AND EAX,EDI JNZ @Zaehle0 @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
      
Beiträge: 67
Erhaltene Danke: 1
|
Verfasst: 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, 1, 8 * ((Pos('1', bin) - 1) div 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 Kha: Delphi-Tags hinzugefügt
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 09.04.09 11:03
Ich muss doch hoffentlich auf diesen letzten Vorschlag nicht näher eingehen???  Außerdem geht es hier um "effiziente" Algorithmen, da fallen Strings GANZ selten als Mittel zum Zweck rein 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
pesi
      
Beiträge: 67
Erhaltene Danke: 1
|
Verfasst: 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
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Do 09.04.09 17:44
Stichwort: Population Count / Hamming weight
Branchless O(log(n)) implementation
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:
www.delphi-forum.de/viewtopic.php?t=74678
en.wikipedia.org/wiki/Hamming_weight
|
|
Reinhard Kern
      
Beiträge: 591
Erhaltene Danke: 14
|
Verfasst: Fr 10.04.09 10:30
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
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Reinhard Kern
      
Beiträge: 591
Erhaltene Danke: 14
|
Verfasst: Sa 11.04.09 01:05
BenBE hat folgendes geschrieben : | 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
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 12.04.09 17:06
Horst_H hat folgendes geschrieben : | Hallo,
ist das Thema jetzt beantwortet? |
Ja, ist beantwortet, hab schon den Fragenstatus angepasst.
Horst_H hat folgendes geschrieben : | 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.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 15.04.09 15:57
Hallo,
und jetzt willst Du uns dumm sterben lassen.....
Gruß Horst
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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).
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
|