signbitsfunktion oder log2

[Vlad T. (vlad_tepesch)]

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

[Volker Z. (vza)]

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?

[Vlad T. (vlad_tepesch)]

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);
}

[Hagen R. (hagen)]

Jo Assembler Befehle BSR und BSL.

[Vlad T. (vlad_tepesch)]

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