Hallo zusammen, ich möchte die Quersumme, also die Anzahl von Einsen in einem Byte ermitteln. Gibt's dafür eine einfachere Möglichkeit als die Bits zu zählen? 01110000b --> 3 10010101b --> 4 Für so eine kurze Zahl gehts ja noch, aber wenn die Variablen größer werden, z.B. uint32_t oder gar uint64_t kann das zusammenzählen eine ganze Weile dauern. Bisherige Lösung: Zahl=0xaa; for (i=0x01, z=0; i; i=i<<1) if (i&Zahl) z++;
Schnellste Lösung, wenn Du Platz im Flash übrig hast: Ein Flash-Array mit der Anzahl der gesetzten Bits des Array-Index anlegen. Also z.B.: /* Index = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F .. uint8_t bitanz[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 .. Und dann zugreifen mit: z = bitanz[Zahl]; bei WINAVR natürlich mit der entsprechenden PROGMEM-Konstruktion. Viele Grüße, Stefan
ist 10010101b nich 149 dez? dann wäre die Quersumme 14 und nicht 4
Als Denkansatz - bei einem 8bit µC kann eine wiederholte 8bit Variante sinnvoller sein. int bitcount(unsigned long n) { /* works for 32-bit numbers only */ /* fix last line for 64-bit numbers */ unsigned long tmp; tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111); return ((tmp + (tmp >> 3)) & 030707070707) % 63; }
Das war die falsche Version, Divisionen sind bei µCs nicht so gut. Besser: int bitcount32 (unsigned long w) { w = (0x55555555 & w) + (0x55555555 & (w >> 1)); w = (0x33333333 & w) + (0x33333333 & (w >> 2)); w = (0x0f0f0f0f & w) + (0x0f0f0f0f & (w >> 4)); w = (0x00ff00ff & w) + (0x00ff00ff & (w >> 8)); w = (0x0000ffff & w) + (0x0000ffff & (w >>16)); return w; } oder int bitcount8 (byte w) { w = (byte)(0x55 & w) + (byte)(0x55 & (byte)(w >> 1)); w = (byte)(0x33 & w) + (byte)(0x33 & (byte)(w >> 2)); w = (byte)(0x0F & w) + (byte)(0x0F & (byte)(w >> 4)); return w; }
Hi ob das wohl schneller ist als? UInt8 bitcount8(UInt8 c) { const UInt8 lookup[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; UInt8 result; result = lookup[c&0xF]; result += lookup[(c>>4)&0xF]; return result; } Für die Quersumme aus einer 32-Bitzahl muß man das ganze dann halt 4 mal aufrufen. Matthias
nö, nicht schneller und wahrscheinlich braucht es sogar mehr Code als mit deiner kleinen Lookup Tabelle. Die gleiche Frage habe ich mir übrigens auch gestellt. Der Algo ansich ich nicht schlecht, aber nicht alles was auf zb. Intel CPU's effizient ist ist auch zwangsläufig auch auf AVR's effizient. Ich würde deine Methode vorziehen. Gruß Hagen
bitcount32 ist auf AVR sicher nicht ideal, aber bitcount8 ist ausgesprochen kompakt (die ganzen casts sind nicht umsonst da drin ;-). Die Lookup Table leidet ausserdem unter gewissen Portierungsproblemen. Oder an RAM-Speicherplatz - je nachdem ob der Compiler sie auch ohne brachiale Gewalt ins ROM packt ($$$) oder nicht (GNU).
bitcount8 kann auf AVR's nicht so kompakt sein. w = (byte)(0x55 & w) + (byte)(0x55 & (byte)(w >> 1)); w = (byte)(0x33 & w) + (byte)(0x33 & (byte)(w >> 2)); w = (byte)(0x0F & w) + (byte)(0x0F & (byte)(w >> 4)); return w; 6 * AND 3 * LSR 1 * SWAP 3 * ADD 4 * MOV 1 * RET ca. 18 Worte. Wobei letzte Zeile vereinfacht werden kann w = w + (w >> 4) & 0x0F; UInt8 bitcount8(UInt8 c) { const UInt8 lookup[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; UInt8 result; result = lookup[c&0xF]; result += lookup[(c>>4)&0xF]; return result; } 8 * Worte Lookup 2 * AND 1 * SWAP 1 * ADD 1 * RET 1 * ZH laden 2 * LPM ca. 16 Worte so Pi*Daumen. Mein Gefühl sagt mir das die Lookup Methode auf dem AVR kompakter und schneller ist. Muß man natürlich noch verifizieren. Gruß Hagen
PS: plus die Tabelle, natürlich. Nochmal 8 Worte extra für lookup.
Danke, danke, danke. Den ersten Vorschlag von A.K. hab ich nicht ganz verstanden. Den zweiten find ich genial. Auch die Lookuptabelle (entweder für Nibbles oder ganze Bytes) ist eine gute und einfache Möglichkeit.
Bitte 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.