hallo.
gibt es einen schnellen algorithmus, um alle geraden und ungeraden bits eines bytes zu zählen?
z.b. sollte bei 0 1 0 1 1 1 1 0 rauskommen
gerade bits (1, 3, 5, 7): 2
ungerade bits (0, 2, 4, 6): 3
das byte nach rechts durchzuschieben und jedes mal das LSB zu „ungerade“ bzw. „gerade“ zu addieren ist doch gar zu plump - oder?
gruß
michael
Hallo,
das schnellste ist meist ein Array von 256 Bytes mit den Ergebnissen des Index (z.B. als high-nibble, low nibble, oder als 2 Arrays).
Ansonsten ist z.B. bei Pics Dein Verfahren ausgerollt sehr schnell.
shift right
skip wenn nicht carry flag
ungerade++
shift right
skip wenn nicht carry flag
gerade++
… und das ganze 4 mal oder while != 0
Bei einem FPGA gehts auch direkt, und mit ein bisschen optimieren könnte man die Tabellt auf einen Bruchteil reduzieren.
Gruß
achim
hallo.
das schnellste ist meist ein Array von 256 Bytes mit den
Ergebnissen des Index (z.B. als high-nibble, low nibble, oder
als 2 Arrays).
ja, eine LUT wäre natürlich das allerschnellste und für ein byte sicher die beste lösung.
lieber wäre mir aber etwas, das sich auch auf längere bitfolgen anwenden läßt, ohne den speicher zu sprengen 
Ansonsten ist z.B. bei Pics Dein Verfahren ausgerollt sehr
schnell.
ich müßte es „leider“ in C programmieren. mal schauen, was der compiler draus macht.
Bei einem FPGA gehts auch direkt,
wenn die dinger nur nicht so teuer wären…
danke & gruß
michael
Hallo Michael,
das schnellste ist meist ein Array von 256 Bytes mit den
Ergebnissen des Index (z.B. als high-nibble, low nibble, oder
als 2 Arrays).ja, eine LUT wäre natürlich das allerschnellste und für ein
byte sicher die beste lösung.
lieber wäre mir aber etwas, das sich auch auf längere
bitfolgen anwenden läßt, ohne den speicher zu sprengen
Du kannst eine LUT für ein Byte erstellen und dann die einzelnen Resultate addieren.
Für 32 Bit ergibt das 4 Zugriffe auf die LUT und 3 Additionen.
Wenn du die LUT mit 16-Bit Werten aufbaust und die Resultate je auf ein Byte verteilst, anstelle der Nibble, kannst du mit 16-Bit Additionen arbeiten und musst dann erst am Ende die beiden Hälften trennen.
MfG Peter(TOO)
in C wäre das ja trivial
Hallo Michael,
in C kannst Du es doch einfach direkt hinschreiben und dem Compiler jegliche optimierung überlassen.
\_\_inline int even\_bits(BYTE x) // inline und BYTE auf Dein System anpassen
{
int g = 0;
if(x & 1) g++;
if(x & 4) g++;
if(x & 16) g++;
if(x & 64) g++;
return g;
}
Und nur, wenn sich herausstellt dass diese Operation zu lange dauert, bezogen auf die Gesamtlaufzeit, nur dann kannst du über LUT oder Optimierung nachdenken. Vermutlich schaffst Du aber schwerlich einen Faktor 3.
Gruß
achim
hallo wilbert.
__inline int even_bits(BYTE x) // inline und BYTE auf Dein
System anpassen
{
int g = 0;if(x & 1) g++;
if(x & 4) g++;
if(x & 16) g++;
if(x & 64) g++;
return g;
}
jaaa… neeeeee!
ich müßte das ja dann noch für die ungeraden bits machen und schon isses doppelt so lang… allerdings wäre es sehr leicht erweiterbar.
gruß
michael
hallo peter.
Du kannst eine LUT für ein Byte erstellen und dann die
einzelnen Resultate addieren.
hab ich jetzt auch so gemacht eine 256-Byte LUT kann man bei 128kB Flash schon vertreten.
danke & gruß
michael
Hallo.
gibt es einen schnellen algorithmus, um alle geraden und
ungeraden bits eines bytes zu zählen?
z.b. sollte bei 0 1 0 1 1 1 1 0 rauskommen
gerade bits (1, 3, 5, 7): 2
ungerade bits (0, 2, 4, 6): 3
Hier gibts u.a. mehrere Algorithmen, die Bits zählen. Ein wenig angepasst wäre z.B. sowas möglich:
unsigned int input;
unsigned int odd = 0;
unsigned int even = 0;
unsigned int test = input & 0x55555555; //If input has more than 32 bit, adapt this
for (odd = 0; test; odd++)
{
test &= test - 1;
}
unsigned int test = input & 0xAAAAAAAA; //If input has more than 32 bit, adapt this
for (even = 0; test; even++)
{
test &= test - 1;
}
Sebastian.
hallo.
gibt es einen schnellen algorithmus, um alle geraden und
ungeraden bits eines bytes zu zählen?
z.b. sollte bei 0 1 0 1 1 1 1 0 rauskommen
gerade bits (1, 3, 5, 7): 2
ungerade bits (0, 2, 4, 6): 3Hier gibts u.a. mehrere Algorithmen, die Bits zählen. Ein
wenig angepasst wäre z.B. sowas möglich:
das ist in der tat ziemlich geschickt
eine LUT wird unterm strich wahrscheinlich trotzdem schneller sein, aber die seite wandert auf jeden fall in meine favoriten.
danke & gruß
michael
Hallo.
das ist in der tat ziemlich geschickt
eine LUT wird unterm strich wahrscheinlich trotzdem schneller
sein,
Ja, stimmt, da wirst du recht haben. Aber manchmal kommt es ja auch auf Speicherbedarf an…
aber die seite wandert auf jeden fall in meine
favoriten.
Immer wieder einen Blick wert, finde ich. Teilweise sehr ausgefallene Ideen, auf die man nicht so ohne weiteres kommt.
Sebastian.