bit position ohnel log

[gert (Gast)]

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

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

danke

[Gerhard (Gast)]

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

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

Gerhard

[Jörg W. (dl8dtl) (Moderator)]

ffs()

[funky (Gast)]

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

[Peter (Gast)]

funky schrieb:
> Falls jemand eine schnellere Idee hat, dann nur her damit

lookup Tabelle.

pos = tbl[input];

schneller geht es vermutlich nicht.

[Sven P. (Gast)]

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

[Oliver (Gast)]

>lookup Tabelle.

>pos = tbl[input];

>schneller geht es vermutlich nicht.

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

Oliver

[Peter (Gast)]

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.

[Karl H. (kbuchegg)]

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

[Marcus H. (mharnisch)]

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

[Peter (Gast)]

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.

[Karl H. (kbuchegg)]

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)

[Peter (Gast)]

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.

[Marcus H. (mharnisch)]

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

[Marcus H. (mharnisch)]

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

[funky (Gast)]

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?

[Peter (Gast)]

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.

[Marcus H. (mharnisch)]

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

[Karl H. (kbuchegg)]

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

[Flo (Gast)]

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;

[Peter (Gast)]

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.

[Marcus H. (mharnisch)]

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