Author: Heiner Marxen
Date: 14:25:38 02/11/02
Go up one level in this thread
On February 11, 2002 at 12:06:19, Dann Corbit wrote:
>On February 09, 2002 at 11:56:20, Heiner Marxen wrote:
>
>>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?
>
>right bit of 0 is 0
>right bit of 1 is 0
The value for 1 is ok.
What to return for 0 is a question of definition.
You ask for the position of the rightmost one, while there is none.
What result do you expect? A blue screen?
A true zero should not be fed into this function, unless we have defined
what result is acceptable.
Every other implementation has the exact same problem.
>But I guess it does not matter for chess, since you will always have at least
>two kings on the board. Of course, you might be looking for a bishop position
>or something from a list of bishops.
Yes. :-)
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.