Suche das erste gesetzte Bit in einer Variable

Ok, das ist schnell.

Kriegt aber Punktabzug, wegen unerlaubten Verlassen des Spielfeldes.

Zur Strafe hier eine Lösung in einer Zeile C++:

unsigned int lowestBitSet(unsigned __int64 x)
{
  return  x ? unsigned int(log(double(x & - __int64(x)) / log(2.0))) + 1 : 0;
}

Wutz

Was ist daran C++?
Kriegt ebenso Minus in der B-Note, da durch __int64 nicht portabel.
Wenn schon MSVC, dann richtig:
_BitScanForward bzw. _BitScanForward64

Wutz schrieb:

Was ist daran C++?

Hab ich nur so geschrieben.

Aber, falls du auch etwas konstruktives beizutragen hast:

Ist die Konstruktorschreibweise double(irgendwas) in ANSI C denn erlaubt ?

Wutz schrieb:

da durch __int64 nicht portabel.

Das sollte nur zeigen, dass es auch mit 64 Bit geht.

Wenn man es so schreibt

int lowestBitSet(int x)
{
  return  x ? int(log(double(x & -x)) / log(2.0))) : -1;
}

könnte es auf Systemen, wo Fließkomma-Ops billig sind, fast so gut wie die DeBruijn-Folge abschneiden. Außerdem spart es die Tabelle.

Wutz

Dies hier ist strikt C89 und somit maximal portabel.
Die sehr übersichtlichen, wenigen Nicht-Fließkomma-Assembleroperationen sollten eigentlich nicht zu langsam sein, und inlinen kann man ja auch noch.
Mit 64-Bit compiliert, ist size_t 64 bittig, mit 32-Bit compiliert, ist size_t ...

unsigned char lsb(size_t i)
{
  register unsigned char r=1;
  while( i )
    if( i&1 )
      return r;
    else
      { ++r; i>>=1; }
  return 0;
}

Ach ja, das Ergebnis ist hier 1-basiert, 0 bedeutet "nichts gefunden".

Wutz schrieb:

Dies hier ist strikt C89 und somit maximal portabel.
Die sehr übersichtlichen, wenigen Nicht-Fließkomma-Assembleroperationen sollten eigentlich nicht zu langsam sein, und inlinen kann man ja auch noch.
Mit 64-Bit compiliert, ist size_t 64 bittig, mit 32-Bit compiliert, ist size_t ...
unsigned char lsb(size_t i)
{
  register unsigned char r=1;
  while( i )
    if( i&1 )
      return r;
    else
      { ++r; i>>=1; }
  return 0;
}
Ach ja, das Ergebnis ist hier 1-basiert, 0 bedeutet "nichts gefunden".

den code von nn hast nicht angeschaut oder hasts nicht verstanden?

nn schrieb:

Wie wäre es damit
unsigned int msb32(unsigned int x)
{
  x |= (x >> 1);
  x |= (x >> 2);
  x |= (x >> 4);
  x |= (x >> 8);
  x |= (x >> 16);
  return(x & ~(x >> 1));
}
Hab ich mal hier gefunden http://aggregate.org/MAGIC/

Es gibt noch mehr davon unter http://graphics.stanford.edu/~seander/bithacks.html ,aber irgendwie will die Seite im Moment nicht.

Wutz schrieb:

eigentlich nicht zu langsam sein

Zumindest ist es (im Mittel) die langsamste Lösung bisher. Auch langsamer als die des Fragestellers.

So, wenn man etwas Google bemüht, hier eine 64-Bit Variante

const int index64[64] = {
   63,  0, 58,  1, 59, 47, 53,  2,
   60, 39, 48, 27, 54, 33, 42,  3,
   61, 51, 37, 40, 49, 18, 28, 20,
   55, 30, 34, 11, 43, 14, 22,  4,
   62, 57, 46, 52, 38, 26, 32, 41,
   50, 36, 17, 19, 29, 10, 13, 21,
   56, 45, 25, 31, 35, 16,  9, 12,
   44, 24, 15,  8, 23,  7,  6,  5
};

/**
 * bitScanForward
 * @author Charles E. Leiserson
 *         Harald Prokop
 *         Keith H. Randall
 * "Using de Bruijn Sequences to Index a 1 in a Computer Word"
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x07EDD5E59A4E28C2);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

mngbd

Ich glaube, das wird mich weiter bringen.

Danke schön!

pointercrash**

... das bitweise geshifte ist selten wirklich schnell, ein Teil fliegt durch char - Zugriffe flach:

int TheLSBisAt(void *sometype, size_t size)
{
    int bitpos, charpos;
     unsigned char bit = 1;

    for (charpos = 0; (((unsigned char *)sometype)[charpos] == 0) && ((size_t)charpos < size); charpos++);
    if (charpos == size)
        return -1; // kein Bit gesetzt
    bitpos = charpos * 8; // Schwachpunkt, wenn char != 8 Bit

    while (bit)
    {
         if ((((char *)sometype)[charpos]) & bit)
            return bitpos;
        else
              { ++bitpos; bit<<=1; }
    }
  return -2; // they should never return
}

call:

{
    int i = 256;
    printf("Var i has its LSB at Bit:%d\n",TheLSBisAt((void *)&i, sizeof(i)) );
}

Dürfte stimmen und meist schneller sein ... wenn nicht, haut's mich :p