Author: Ricardo Gibert
Date: 09:14:22 02/09/02
Go up one level in this thread
On February 09, 2002 at 03:07:47, Dann Corbit wrote:
>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.
If you take the trouble of understanding the *idea* of the algorithm, you would
realize that the idea is sound even if a particular incarnation in code may not
be.
>
>#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.