bit position ohnel log

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

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

Gerhard

hmmm...habe das gleiche Problem.

Gibts was besonders effizientes?

1

if (input != 0x01){

2

  do{

3

    input = input >> 1;

4

    pos++;

5

  }

6

  while(!(input & 0x01));

7

}

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

Falls jemand eine schnellere Idee hat, dann nur her damit

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

lookup Tabelle.

pos = tbl[input];

schneller geht es vermutlich nicht.

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

>lookup Tabelle.

>pos = tbl[input];

>schneller geht es vermutlich nicht.

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

Oliver

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

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?

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.

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;

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.