Autor Beitrag
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 467
Erhaltene Danke: 17

WIN 7
NQC, Basic, Delphi 2010
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 98
Erhaltene Danke: 8

Win 8, Win 7, Vista, Win XP
Delphi XE3, Delphi 2009, Delphi 2007, Delphi 5
BeitragVerfasst: 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

ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 08.04.09 23:15 
Hallo,

Dein Code springt mehr zu sehr nach nee und mehr.

ausblenden 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 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.
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 67
Erhaltene Danke: 1



BeitragVerfasst: 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:

ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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

_________________
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 67
Erhaltene Danke: 1



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 591
Erhaltene Danke: 14



BeitragVerfasst: 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
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


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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 591
Erhaltene Danke: 14



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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.

_________________
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 15.04.09 15:57 
Hallo,

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

Gruß Horst
BenBE Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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.