binäre Quersumme einer Zahl ermitteln

[Werner Hoch (Gast)]

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

[Stefan Kleinwort (Gast)]

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

[Simon Küppers (Gast)]

ist 10010101b nich 149 dez? dann wäre die Quersumme 14 und nicht 4

[Gudrun Stender (Gast)]

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

[A.K. (Gast)]

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

[A.K. (Gast)]

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

[Matthias (Gast)]

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

[Hagen (Gast)]

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

[A.K. (Gast)]

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

[Hagen (Gast)]

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

[A.K. (Gast)]

direkt: 19 Worte
lookup: 18 Worte
mit GCC

[A.K. (Gast)]

PS: plus die Tabelle, natürlich. Nochmal 8 Worte extra für lookup.

[Werner Hoch (Gast)]

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.