binäre Quersumme einer Zahl ermitteln

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

@Simon: deshalb heißt der Thread auch binäre quersumme

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

direkt: 19 Worte
lookup: 18 Worte
mit GCC

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.