mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik binäre Quersumme einer Zahl ermitteln


Autor: Werner Hoch (Gast)
Datum:

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

Autor: Stefan Kleinwort (Gast)
Datum:

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

Autor: Simon Küppers (Gast)
Datum:

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

Autor: Gudrun Stender (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Simon: deshalb heißt der Thread auch binäre quersumme

Autor: A.K. (Gast)
Datum:

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

Autor: A.K. (Gast)
Datum:

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

Autor: Matthias (Gast)
Datum:

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

Autor: Hagen (Gast)
Datum:

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

Autor: A.K. (Gast)
Datum:

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

Autor: Hagen (Gast)
Datum:

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

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
direkt: 19 Worte
lookup: 18 Worte
mit GCC

Autor: A.K. (Gast)
Datum:

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

Autor: Werner Hoch (Gast)
Datum:

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

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.