Suche das erste gesetzte Bit in einer Variable

mngbd

Ich will das niedrigste gesetzte Bit in einer Variablen finden. Im Moment mache ich das so (der Übersicht halber auf unsigned char vereinfacht):

int first_bit(unsigned char c)
{
   if (c & 0xf)
      if (c & 0x3)
         return c & 0x1 ? 0 : 1;
      else
         return c & 0x4 ? 2 : 3;
   else if (c & 0xf0)
      if (c & 0x30)
         return c & 0x10 ? 4 : 5;
      else
         return c & 0x40 ? 6 : 7;
   else
      return -1;
}

Das wird zB für ein 64-Bit-Wort recht lang. Dabei gehe ich davon aus, dass die Eingabewerte gleichförmig verteilt sind. Ich will keine Zugeständnisse an die Laufzeit machen, aber portabel bleiben.

Geht das besser?

SeppJ

Schleife?

mngbd

SeppJ schrieb:

Schleife?

Ist, fürchte ich, langsamer. Es geht hauptsächlich um 32 und 64 Bits in der Breite. Bei Breite 8 hat meine Variante das Ergebnis nach spätestens 4 Vergleichen, bei Breite 64 kommen noch 3 dazu, macht höchstens 7 Vergleiche. Nur sieht die Funktion dann schon recht ugly aus (weil fast 100 Zeilen lang), deshalb meine Frage.

Ideen, die nicht portabel sind, will ich nach genauerer Überlegung auch nicht ausschliessen.

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.

Ah, sorry du meinst das niedrigste.

Guggst du da: http://aggregate.org/MAGIC/#Least%20Significant%201%20Bit

Über Wikipedia findet sich das hier, müsste aber noch an 64-Bit angepasst werden:

const unsigned int MultiplyDeBruijnBitPosition[32] =
{
  // precomputed lookup table
  0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,
  31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
};

unsigned int lowestBitSet(unsigned int x)
{
  // leave only lowest bit
  x  &= -int(x);
  // DeBruijn constant
  x  *= 0x077CB531;
  // get upper 5 bits
  x >>= 27;
  // convert to actual position
  return MultiplyDeBruijnBitPosition[x];
}

mngbd schrieb:

Ideen, die nicht portabel sind, will ich nach genauerer Überlegung auch nicht ausschliessen.

// 32-Bit x86, Syntax mag bei deinem Compiler abweichen
int lowestBitSet (unsigned val)
{
    asm
    {
        BSF EAX, val
        JNZ @bitSet
        MOV EAX, 0xFFFFFFFF
    @bitSet:
    }
}

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