mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik signbitsfunktion oder log2


Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,
Ich bin auf der Suche nach einer effizienten Funktion, die Nummer des 
höchsten belegten Bits ausgibt (log2), bzw oder die Anzahl an 
Vorzeichenbits.
Ist ja prinzipiell das selbe, nur das von der anderen Seite angefangen 
wird zu zählen

(einige kennen vielleicht die SIGNBITS - instruktion des Blackfin)


kennt jemand eine schöne kurze tricky methode zur implementierung in C?

Die Referenz-Implementierung ist einfach, aber natürlich sehr 
ineffizient.

int16_t signbits(int32_t x)
{  
  int32_t t;
  int32_t c;
  c = 0;
  t  = x & 0x80000000; //isolate highest bit
  for(;c<=31;c++){
    if(t!=(x & 0x80000000))
      break;
    x = x<<1;
  }
  return (int16_t)(c-1);
}

beispiel:

0000 0001 1111 0011 -> 7
¯¯¯¯¯¯¯¯
0000 1010 1111 0011 -> 4
¯¯¯¯
1111 1110 1111 0011 -> 7
¯¯¯¯¯¯¯¯

(wobei die Blackfin- SIGNBITS - Instruction eins abzieht)
ob das bit jetzt von oben oder von unten gezählt wird ist mir dabei 
egal, lässt sich ja leicht umrechnen.

Gruß,
vlad

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da fällt mit nur die "binäre Suche" ein.
Ob sie bei nur 32 iterationen wiklich schneller ist?
Wieviel Millionen mal must du den die Vorzeichenbits bestimmen?

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
glaube ich nicht.
enthält ja auch schleifen und sprünge.

Ich hab gehofft, dass jemand einen ähnlichen trick kennt wie für die 
ones-population-count.
unsigned int
ones32(register unsigned int x)
{
        /* 32-bit recursive reduction using SWAR...
     but first step is mapping 2-bit values
     into sum of 2 1-bit values in sneaky way
  */
        x -= ((x >> 1) & 0x55555555);
        x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
        x = (((x >> 4) + x) & 0x0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        return(x & 0x0000003f);
}

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jo Assembler Befehle BSR und BSL.

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
lustig, ich hatte grad nach der ones implementierung gesucht, da ich da 
noch ein charakteristisches Bitmuster kannte.

http://aggregate.org/MAGIC/


da gits glaub ich auch das, was ich suche.
Muss ich mir später mal genauer anschauen

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.