Author: Gerd Isenberg
Date: 16:26:43 06/13/04
Go up one level in this thread
On June 13, 2004 at 10:26:55, Gerd Isenberg wrote:
>On June 13, 2004 at 09:52:57, Gerd Isenberg wrote:
>
>>
>>
>> 1 0x00000001 4-bit deBruijn found
>> 2 0x00000002 8-bit deBruijn found
>> 16 0x00000010 16-bit deBruijn found
>> 2048 0x00000800 32-bit deBruijn found
>>67108864 0x04000000 64-bit deBruijn found
>>
>
>Funny, seems in general for N-bit de Bruijn sequences, where N is power of two,
>the number of N-bit de Bruijn sequences is a power of two too:
>
> # N-bit deBruijn := 2**(N/2 - log2(N))
>
>Excuse my digressions ;-)
Sorry, after some more brain storming again on that tocip, i came to the
conclusion that this formula is only the half truth. There is one valid way to
shift/rotate the odd set left, to get exactly an even set with log2(N)-1 leading
zeros (minimum needed for wrap), instead the odd set with log2(N) leading binary
zeros.
0011(0) - 0,1,3,2
0110(0) - 1,3,2,0
-----^ the wrapped zero
therefore my next guess:
# N-bit deBruijn := 2**(N/2 - log2(N) + 1)
0x03f08c5392f756cd is reserved by Gian Carlo's BitScan!
If anybody else uses this constant with the associated table and an unique byte,
short or int sequence, it may be considerd as Deep Sjeng clone!
There are 2**27 - 1 others ;-)
Gerd
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.