Author: Dann Corbit
Date: 00:07:47 02/09/02
Go up one level in this thread
On February 08, 2002 at 17:17:26, Oliver Roese wrote:
>Hi!
>
>http://citeseer.nj.nec.com/338945.html
>Hope you find it interesting.
Unless I've screwed it up a bit, it doesn't quite work right at the endpoints.
#define debruijn32 0x077CB531UL
/* debruijn32 = 0000 0111 0111 1100 1011 0101 0011 0001 */
/* table to convert debruijn index to standard index */
static unsigned int index32[32];
/* routine to initialize index32 */
void setup(void)
{
unsigned i;
for (i = 0U; i < 32U; i++)
index32[(debruijn32 << i) >> 27U] = i;
}
/* compute index of rightmost 1 */
int rightmost_index(unsigned long b)
{
b &= -b;
b *= debruijn32;
b >>= 27U;
return index32[b];
}
#ifdef UNIT_TEST
#include <stdio.h>
#include <limits.h>
int main(void)
{
unsigned i;
int j;
setup();
j = rightmost_index(0);
printf("right bit of %u is %d\n", 0, j);
for (i = 1U; i < UINT_MAX && i > 0; i <<= 1U) {
int j = rightmost_index(i);
printf("right bit of %u is %d\n", i, j);
}
j = rightmost_index(UINT_MAX);
printf("right bit of %u is %d\n", UINT_MAX, j);
return 0;
}
#endif
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.