Als Bitcount-Funktion für 32 Bit habe ich diese C-Funktion als Makro:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
\
- (((x)>>2)&0x33333333)
\
- (((x)>>3)&0x11111111))
Aber wie sieht die Version für 8, 16 u. 64 Bit aus?
8 Bit:
#define BITCOUNT(x) ((BX_(x)+(BX_(x)>>4)) & 0x0F)
#define BX_(x) ((x) - (((x)>>1)&0x77) \
- (((x)>>2)&0x33) \
- (((x)>>3)&0x11))
16 Bit:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x7777) \
- (((x)>>2)&0x3333) \
- (((x)>>3)&0x1111))
64 Bit: (angenommen, es gibt einen 64-bit-Typen, ansonsten einfach 2x
die beiden 32Bit-Hälften auswerten und zusammenzählen)
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F0F0F0F0F) %
255)
#define BX_(x) ((x) - (((x)>>1)&0x7777777777777777) \
- (((x)>>2)&0x3333333333333333) \
- (((x)>>3)&0x1111111111111111))
Das Ganze ist jetzt nicht getestet sondern einfach so vom Verständnis
der Funktion her. Wenn Du willst kann ich Dir die Funktionsweise auch
noch erklären.
Markus
Nachtrag: Wenn Dein Microcontroller keine Division kann, dann gibts da schnellere Wege als den Modulo-Operator.
@Markus: brauch's zwar eigentlich nicht, aber eine Erklärung der Funktion wär schon interessant.. Hab keine Ahnung wie das funktionieren soll :)
ich ziehe meinen hut vor euch, ich kann aus den defines keinen
maschinencode für meinen zerebralen kortex erzeugen :-)
das soll wirklich die bits einer variable zählen?
ich mach das so:
bits = 0;
i = 8; // 8, 16, 32, 64, ...
while (i--) { if ( (x>>i)&(0x1) ) bits++; }
Ich hab' auch erst eine Weile gebraucht, bis ich die Funktion geblickt hab', es ist ja nicht so, daß man täglich damit zu tun hätte. Zuerst mal zum BX_: Grundsätzlich erstmal: Ob ich nun 75 - 32 rechne oder (70-30) + (5-2) macht keinen Unterschied. Deswegen kann man die Bits dort einzeln betrachten, man muß sich nicht mit allen möglichen Kombinationen rumschlagen. Betrachten wir einfach mal 4 Bit, dann gibt es da vier Fälle, nämlich die 4 Bitpositionen. Wir betrachten immer nur ein gesetztes Bit, die Mischkombinationen ergeben sich dann aus obigem automatisch. Fall A: 0001 Das gibt dann 1 - (1 >>1 = 0) - (1 >>2 = 0) - (1 >>3 = 0) = 1 Fall B: 0010 Das gibt dann 2 - (2 >>1 = 1) - (2 >>2 = 0) - (2 >>3 = 0) = 1 Fall C: 0100 Das gibt dann 4 - (4 >>1 = 2) - (4 >>2 = 1) - (4 >>3 = 0) = 1 Fall D: 1000 Das gibt dann 8 - (8 >>1 = 4) - (8 >>2 = 2) - (8 >>3 = 1) = 1 Sind mehrere Bits gesetzt, dann addiert sich das eben automatisch. Beispiel 13 (1011): 13 - (13 >>1 = 7) - (13 >>2 = 2) - (13 >>3 = 1) = 3 Jetzt haben wir erst 4 einzelne Bit betrachtet, im Original sind es aber 32 Bit. Hier arbeitet der Algorithmus parallel, d.h. er berechnet die 8 Nibbles (Nibble=4Bit) gleichzeitig. Schiebt man nun die Bits nach rechts, dann fallen die aber nicht einfach rechts weg wie im obigen Beispiel, sondern sie landen dann im nächsten Nibble und stören dort das Ergebnis. Deswegen werden sie vorher herausgefiltert. Schiebt man z.B. die ganze Zahl um 1 Bit nach rechts, dann ist das niederwertigste Bit von einem Nibble plötzlich das höchstwertige Bit des nächsten Nibbles. Deswegen wird dieses mit einem "& 7" zu 0 gemacht. Für alle 8 Nibbles gleichzeitig, deswegen eben "& 77777777". Kommen wir zum BITCOUNT: Hier werden immer zwei Nibble zusammengefaßt, und zwar indem man das Ergebnis von BX_ zweimal nimmt, einmal normal und einmal um einen Nibble nach rechts verschoben. Das Ergebnis sieht dann so aus: 1. Nibble, Summe 1.+2. Nibble, 3 Nibble, Summe 3.+4. Nibble usw. usf. Dann werden mit dem "& 0F0F0F0F" die Einzelwerte entfernt, so daß nur noch die Summen übrigbleiben. Jetzt bleiben also noch 4 Bytes, in denen jeweils die Bitzahlen der Originalbytes stehen. Diese werden zusammengezählt, dann hat man das Ergebnis. Bei einem Microcontroller ohne Division würde ich das mit einer Kombination aus Shift, And und Addition lösen. Hier hat man es aber mit einem Modulo 255 gelöst. Ich verstehe es selber nicht so ganz, aber es funktioniert tatsächlich. Es funktioniert auch nicht mit beliebigen Zahlen, z.B. gibt 0xffffffff % 255 natürlich 0 und nicht 0x03fc, aber bei den Zahlen die hier auftreten können funktioniert es wohl. Ich hoffe, das war soweit verständlich, wenn nicht, dann fragt genauer nach. Markus
Aha, danke.
Falls es interessiert: Hier ist ein effizientes Reverse für
32-Bit-Zahlen:
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
Damit wird Bit 0 zu Bit 31, Bit 1 zu Bit 30 usw..
Wie die Version für N statt 32 Bit aussieht, sollte klar sein.
Gibt´s eigentlich irgendwo online oder in Buchform eine Sammlung von
solchen kleinen und effizienten Algorithmen?
Nachtrag: Die obige 32-Bit-Version vom Bitcount ist getestet; die nur 2^(32) Möglichen Eingaben mal kurz alle durchzutesten ist ja kein Problem ;-)
Übrigens kommt das effiziente % 255 von der Modulo-Arithmetik: a(np + 1) mod p = (anp + a) mod p = a mod p ( http://speedy.et.unibw-muenchen.de/lonline/weiterb/e3/k03/krypver2/zusatz/restkoerper.html ) Mit 256 = 255 + 1 und der Berücksichtigung, dass das Byte n in dem Bitfeld den Wert <Byte> * n*256 hat, ist es ganz einfach ;-)
@Rolf, also zumindest beim AVR-GCC ist Deine obige Routine alles andere als effizient. Da werden massiv Divisionen ausgeführt und sowas dauert. Mein Test ergab 464 Byte an Code. Anbei eine einfache Loop, die braucht nur 164 Byte Code (=35%). Vielleicht kann man die auch als Macro schreiben, dann paßt sie sich automatisch an die Größe an. Peter
Aha, dann hängt das noch stark vom Prozessor-Typ ab, so dass es kaum allgemein effiziente kleinen Algorithmen geben kann. Da bleibt dann nur das Optimieren mit Assembler und Opcocde anhand des Instruction Set u. der Hardware (Register, ALU usw.).
Also ich habe das so gemacht: Tabelle mit 256 Byte angelegt, in denen für jeweils ein Byte die Anzahl der Bits drinsteht. Mit dem Byte indiziert auf die Tab zugreifen, je nach Zahlengröße mehrmals hintereinander. Braucht zwar etwas Platz, ist aber ungeschlagen schnell. Und bei Platzproblemen kann man auch ne 16-Byte Tab benutzen und pro Nibble die Bitanzahl addieren. Sollte immer noch ziemlich fix gehen. Stefan
Da sieht man mal wieder den Unterschied von C zu Assembler. Ich hab mal kurz ein Beispiel (Zählschleife wie bei Peter) mit 32-Bit für einen PIC reingehämmert. Summa Summarum 16 Byte Programmcode und Ausführungszeit 452 Maschinenzyklen (wenn ich mich nicht verrechnet habe). Das Beispiel ist nicht getestet, sollte aber funktionieren. Die Idee von Stefan mit der 16-Bit Tabelle ist aber auch nicht schlecht. Mit Sicherheit der beste Kompromiss zwischen Rechenzeit und Speicherplatzbedarf. Steffen
Ja, es kommt auf den Einzelfall an und auch welche Resourcen man hat. Meist verwende ich deshalb Bucketsort, denn damit hat Sortieren die Komplexität O(n). Es geht natürlich effizienter, wenn man die Datenstruktur geeignet aufbaut; dann ist nämlich gar nichts zu tun, also O(0) ;-)
@Steffen, "Summa Summarum 16 Byte Programmcode" Soweit ich weiß ist der PIC nicht Byte organisiert, sondern in Worten von 12, 14 oder 16 Bit. Also entsprechen 16 Worte dann doch 24..32 Byte. Wenn es aber um den kleinsten Code geht, braucht der 8051 dagegen nur 13 Byte (siehe Anhang). Die Zahl im Posting weiter oben (164Byte) ist auch ein komplettes Programm inklusive Startup-Code und Bibliotheken, ist also nicht direkt vergleichbar. Allgemein denke ich, daß die Funktion nicht extrem häufig benötigt wird. Daher sollte wohl die Optimierung auf kleinsten Code mit der Loop-Methode das sinnvollste sein. Peter
@Peter Das mit der Word-Organisation ist richtig. Ein 8051 mit 2K Programmspeicher hat 2048 Byte und ein PIC (14Bit) mit 2K Programmspeicher hat 3584 Byte. Obwohl die Byteweise Betrachtung eigentlich auch falsch ist. Wenn dann Bitweise. Was den Nutzer eigentlich nur interessiert ist wieviele Befehle er im Speicher unterbekommt. Wenn ich die Register über direkte und nicht über indirekte Adressierung anspreche wird der Code um 5 Words kleiner. Der einzigste Vorteil des PIC liegt darin, das ich bei logischen Operationen nicht über den Akku (bzw. W beim PIC) gehen muss. Der Nachteil liegt in dem Beispiel darin, das ich ein Register nicht direkt mit einer Konstanten laden kann sondern diese erst in W speichern muss. Bisher habe ich eigentlich so eine Funktion nur benötigt um die Parität festzustellen. Bei 8 Bit lohnt sich nicht einmal eine Schleife. Es kommt eben immer auf dei Anforderungen an. Steffen PS: Funktioniert der Code eigentlich? Fehlt da nicht ein Register zum Zählen der Einsen (r7 ist Teil der 32-Bit Variable und zählt gleichzeitig die Einsen)?
@Steffen, ja, der Code geht, ich habs simuliert um die Zyklen rauszukriegen. "xch a, r7" ist ein Vertauschen von ACC mit R7, d.h. das Byte aus R7 ist danach im Accu und ich kann jetzt R7 zum Zählen nehmen. Parity geht beim 8051 noch einfacher, das Parity-Flag zeigt immer die Parity des Accus. Für 32 Bit muß man nur alle 4 Bytes miteinander EXORen (siehe Anhang). Mit der Wortgröße gebe ich Dir recht. Leider werden beim AVR trotzdem die Bytes angegeben. Und als ich dann 1996 einen der ersten AT90S1200 in die Finger bekam, war ich doch mächtig enttäuscht, wie schnell man die nur 512 Worte voll hatte. Ich hab dann erstmal die Finger davon gelassen d.h. die Atmel Werbestrategen haben sich damit ein Eigentor geschossen. Erst jetzt, wo ein ATMega8 mit 4kWorten angemessene Größe zu einem angemessenen Preis bereitstellt, bin ich wieder dabei. Mit 16MHz ist er ja auch schon beinahe an den 1996 beworbenen 20MHz heran. Im Anhang ist auch die Parity auf dem AVR auf maximale Geschwindigkeit optimiert, d.h. ohne Loop. Peter
Das mit der Parity ist natürlich nicht verkehrt. Ein Parity-Flag gibt es beim PIC nicht (jedenfalls bei keinem mit 14-Bit Kern). Oben hab ich übrigens Mist geschrieben. In dem Beispiel brauche ich kein w aber für logische Opperationen brauche ich das W-Reg schon. Die Frage mit der Funktionsfähigkeit hat sich damit auch geklärt. Ich stecke eben zuwenig im 8051-ASM drin. Steffen
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.