Algorithmus Suche: Find-Last-Bit

[ArneS]

Moin,

ich suche einen Algorithmus, der mir den Index des höchstwertig gesetzten Bits in einem 32bit unsigned long liefert.
Mit einer Schleife geht das zwar mit O(n), aber ich möchte gerne einen O(1) Algorithmus.
Für das Ermitteln des Indexes für das niederwertigst gesetzte Bit gibt es so einen Algorithmus (habe ich bisher nur in ARM-Assembler gesehen, daher habe ich ihn in C umgeschrieben):

static const unsigned char kFindFirstBitTable[] = {  0,  1,  2, 13,  3,  7,  0, 14,	/*  0 -  7	*/
													 4,  0,  8,  0,  0,  0,  0, 15,	/*  8 - 15	*/
													11,  5,  0,  0,  9,  0,  0, 26,	/* 16 - 23	*/
													 0,  0,  0,  0,  0, 22, 28, 16,	/* 24 - 31	*/
													32, 12,  6,  0,  0,  0,  0,  0,	/* 32 - 39	*/
													10,  0,  0, 25,  0,  0, 21, 27,	/* 40 - 47	*/
													31,  0,  0,  0,  0, 24,  0, 20,	/* 48 - 55	*/
													30,  0, 23, 19, 29, 18, 17,  0 	/* 56 - 63	*/
};

extern unsigned long FindFirstBit(unsigned long inBitPattern)
{
	unsigned long	myResult = 0;

	inBitPattern &= ~inBitPattern + 1;

	if(inBitPattern != 0) {
		inBitPattern |= inBitPattern << 4u;
		inBitPattern |= inBitPattern << 6u;
		inBitPattern = (inBitPattern << 16u) - inBitPattern;
		inBitPattern >>= 26u;
		myResult = kFindFirstBitTable[inBitPattern];
	}
	return myResult;
}

Gruß, Arne

[Apeman]

oder so:

unsigned long ffb (unsigned long x)
{
    return 1 + log(x & (~x+1))/0.693147;
}