www.mikrocontroller.net

Forum: Compiler & IDEs bit position ohnel log


Autor: gert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wie kann ich folgende umwandlung ohne log durchführen (bit position 
ermitteln):

input -> output
0x08  -> 4
0x04  -> 3
0x02  -> 2
0x01  -> 1

danke

Autor: Gerhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn's nur für die 4 aufgeführten Inputs notwendig ist (Pseudo Code):

Output = (Output / 2) + 1;
if (Output == 5) Output--;

Gerhard

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ffs()

Autor: funky (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hmmm...habe das gleiche Problem.

Gibts was besonders effizientes?
if (input != 0x01){
  do{
    input = input >> 1;
    pos++;
  }
  while(!(input & 0x01));
}

ich zähle wie oft ich schieben muss, bis ich 0x01 erhalte.

Falls jemand eine schnellere Idee hat, dann nur her damit

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
funky schrieb:
> Falls jemand eine schnellere Idee hat, dann nur her damit

lookup Tabelle.

pos = tbl[input];

schneller geht es vermutlich nicht.

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>lookup Tabelle.

>pos = tbl[input];

>schneller geht es vermutlich nicht.

Hm. Das würde ich erst einmal mit einem switch/case vergleichen.

Oliver

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oliver schrieb:
> Hm. Das würde ich erst einmal mit einem switch/case vergleichen.

wenn der compiler ein jump Table draus macht, könnte es 1-2 Takte 
schneller sein (weil der die tabellenvariable nicht laden muss), wenn 
nicht es es langsamer.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter schrieb:
> Oliver schrieb:
>> Hm. Das würde ich erst einmal mit einem switch/case vergleichen.
>
> wenn der compiler ein jump Table draus macht, könnte es 1-2 Takte
> schneller sein (weil der die tabellenvariable nicht laden muss)

 Hmm

 Register mit PC laden
 Offset addieren
 Dort über das Register hinspringen
 Konstante in Register laden


gegen
 Startadresse Array laden
 Offset addieren
 Register von dieser Adresse laden

Ich würde sagen: das schenkt sich nichts ausser dass der jump eine 
eventuell vorhandene Prefetch Queue durcheinander bringt

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter schrieb:
> lookup Tabelle.
>
> schneller geht es vermutlich nicht.

Kommt auf die CPU an. Falls CLZ (count leading zeros) vorhanden ist, 
dann hat man das in zwei Instruktionen erledigt.

pos =  31 - __clz(input);

--
Marcus

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Register mit PC laden
> Offset addieren
> Dort über das Register hinspringen
> Konstante in Register laden

je nach CPU, wenn es eine relativen Sprung gibt dann kann man gleich 
springen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter schrieb:
> Karl heinz Buchegger schrieb:
>> Register mit PC laden
>> Offset addieren
>> Dort über das Register hinspringen
>> Konstante in Register laden
>
> je nach CPU, wenn es eine relativen Sprung gibt dann kann man gleich
> springen.

Hilf mir auf die Sprünge
Welche CPU hat einen relativ jump dessen Offset aus einem Register 
kommen kann. (Zugegeben ich kenn nicht viele CPU Architekturen. Is nur 
aus Interesse)

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Hilf mir auf die Sprünge
> Welche CPU hat einen relativ jump dessen Offset aus einem Register
> kommen kann. (Zugegeben ich kenn nicht viele CPU Architekturen. Is nur
> aus Interesse)
Stimmt, wenn du so fragst, denn kenn ich auch keine. Der Relative sprung 
inc. der Weite steht ja im dem Upcode und nicht im Register. Wäre doch 
mal was neues und es bringt ja scheinbar extrem viel optimierung wenn es 
soetwas gibt.

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Hilf mir auf die Sprünge
> Welche CPU hat einen relativ jump dessen Offset aus einem Register
> kommen kann. (Zugegeben ich kenn nicht viele CPU Architekturen. Is nur
> aus Interesse)

ARM
ADD pc, pc, r0, LSL #2

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Marcus Harnisch schrieb:
> pos =  31 - __clz(input);

Mein Beispiel bezog sich natürlich auf den Beitrag des OP. `funky' hat 
ja nach den trailing zeros gefragt. Das geht dann auf einer 32 
Architektur so:
pos = __clz(__rev(input << 24));

--
Marcus

Autor: funky (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die Tips.

clz gibts auf meinem Mikrocontroller nicht.

Ich habe es jetzt mal mit einem switch-case gemacht. Mal schauen was 
mein Compiler daraus bastelt. Aber schneller als meine Variante ist es 
sicherlich.

Und kann mir mal jemand bei der Lookup-Tabelle auf die Sprünge helfen? 
Sehe ich das richtig das ich da eine Tabelle mit 128 Werten für brauche, 
welche effektiv nur 8 Werte enthält und der Rest Datenmüll ist? (da 0x80 
der größte "Index" ist, der auftreten kann) , oder hab ich gerade ein 
Brett vorm Kopf?

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
funky schrieb:
> Und kann mir mal jemand bei der Lookup-Tabelle auf die Sprünge helfen?
> Sehe ich das richtig das ich da eine Tabelle mit 128 Werten für brauche,
> welche effektiv nur 8 Werte enthält und der Rest Datenmüll ist? (da 0x80
> der größte "Index" ist, der auftreten kann) , oder hab ich gerade ein
> Brett vorm Kopf?

ja so ist es, es wurde ja nur nach schnell und nicht nach resourcen 
schonend gefragt.

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Marcus Harnisch schrieb:
> pos = __clz(__rev(input << 24));

Quatsch.

pos = __clz(__rbit(input));

Das Abarbeiten eines Baumes scheint übrigens nicht so effizient. Da kann 
man zumindest für kurze Datenworte gleich bei der Schleife bleiben.

Mann, was Langeweile so anrichten kann ;-)

--
Marcus

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Marcus Harnisch schrieb:
> Karl heinz Buchegger schrieb:
>> Hilf mir auf die Sprünge
>> Welche CPU hat einen relativ jump dessen Offset aus einem Register
>> kommen kann. (Zugegeben ich kenn nicht viele CPU Architekturen. Is nur
>> aus Interesse)
>
> ARM
>
> ADD pc, pc, r0, LSL #2
> 

Geil.
Da kann man den PC wie ein ganz normales Register ansprechen?

Vielen Dank

Autor: Flo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
AVRs können auch über ijmp zur Addresse im Z-Register springen.

Würde die Festlegung der Bitposition allerdings über ne Schleife machen, 
das sie fast keinen Speicherplatz verbraucht und doch recht schnell ist:


//ist der Wert mit einer binären 1

uint8_t count;
for(count=0;data;count++)
  data = data>>1;

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Flo schrieb:
> AVRs können auch über ijmp zur Addresse im Z-Register springen.

dafür muss man aber erst das Z-Register auf die aktuellen PC setzen und 
dann noch den wert addieren. Danach noch den Sprung ausführen. Es ging 
um die Optimierung und das ist das zu langsam.

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
>> ARM
>
> Da kann man den PC wie ein ganz normales Register ansprechen?

Ja. Allerdings nur im ARM state. In Thumb ist das nur einigen 
Instruktionen erlaubt.

--
Marcus

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.