Author: Heiner Marxen
Date: 08:56:20 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.
>
>#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
From the above code I get:
right bit of 0 is 0
right bit of 1 is 0
right bit of 2 is 1
right bit of 4 is 2
right bit of 8 is 3
right bit of 16 is 4
right bit of 32 is 5
right bit of 64 is 6
right bit of 128 is 7
right bit of 256 is 8
right bit of 512 is 9
right bit of 1024 is 10
right bit of 2048 is 11
right bit of 4096 is 12
right bit of 8192 is 13
right bit of 16384 is 14
right bit of 32768 is 15
right bit of 65536 is 16
right bit of 131072 is 17
right bit of 262144 is 18
right bit of 524288 is 19
right bit of 1048576 is 20
right bit of 2097152 is 21
right bit of 4194304 is 22
right bit of 8388608 is 23
right bit of 16777216 is 24
right bit of 33554432 is 25
right bit of 67108864 is 26
right bit of 134217728 is 27
right bit of 268435456 is 28
right bit of 536870912 is 29
right bit of 1073741824 is 30
right bit of 2147483648 is 31
right bit of 4294967295 is 0
which appears to be perfect IMO.
The last number (UINT_MAX) has the low bit set, so 0 is ok.
What exactly don't you like, Dann?
Cheers,
Heiner
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.