mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Effizientes Bitcount für 8, 16 u. 64 Bit?


Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Markus Kaufmann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Markus Kaufmann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nachtrag: Wenn Dein Microcontroller keine Division kann, dann gibts da
schnellere Wege als den Modulo-Operator.

Autor: Rainer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Markus: brauch's zwar eigentlich nicht, aber eine Erklärung der
Funktion wär schon interessant.. Hab keine Ahnung wie das funktionieren
soll :)

Autor: ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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++; }

Autor: Markus Kaufmann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ü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...
)

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 ;-)

Autor: Peter Dannegger (peda)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.).

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Steffen (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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) ;-)

Autor: Peter Dannegger (peda)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Steffen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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)?

Autor: Peter Dannegger (peda)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Steffen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.