Author: Gerd Isenberg
Date: 15:28:52 06/14/04
Go up one level in this thread
On June 14, 2004 at 16:33:26, Dieter Buerssner wrote:
>On June 13, 2004 at 13:48:01, Gerd Isenberg wrote:
>
>>On June 13, 2004 at 12:32:37, milix wrote:
>>>// omit this line to retain current LSB
>>>is this really correct? If we omit this line we have to change the next line to
>>>t64 ^= (bb & t64);
>>
>>
>>Yes, you are correct.
>>But rather than an additional "and" one may modify the table a bit ;-)
>
>Gerd, can you elaborate (and show the modified table) for people like me, who
>really cannot easily understand all those magic algorithms.
The original trailing "one"-sequence is lsb - 1 or (bb&-bb)-1.
The "errornous" trailing "one" sequence is (bb-1)^bb.
lsb
v
bb := 001001000...0000B
(bb&-bb)-1 := 000000111...1111B // exactly n = log2(LSB) trailing ones
(bb-1)^bb := 000001111...1111B // for n = log2(LSB)) n+1 trailing ones
So what Walter's (and also Matt's) routine perform with this traling n (0..63)or
n+1 (1..64) "ones" is a kind of popcount (or leading zero count).
Both do the 32-bit folding trick low32(ntrailingOnes)^high32(ntrailingOnes).
In both sequences that leaves zero for no bit set or all bit sets.
So it's simply a cyclic group rotate.
0000 0000 0000 0000 0000 0000 0000 0000 ; 0 or 64 bits
Folded 32-bit Sequences with 1 to 63 trailing bits look like this:
0000 0000 0000 0000 0000 0000 0000 0001 ; 1 bit
0000 0000 0000 0000 0000 0000 0000 0011 ; 2 bit
0000 0000 0000 0000 0000 0000 0000 0111 ; 3 bit
...
0001 1111 1111 1111 1111 1111 1111 1111 ; 29 bit
0011 1111 1111 1111 1111 1111 1111 1111 ; 30 bit
0111 1111 1111 1111 1111 1111 1111 1111 ; 31 bit
1111 1111 1111 1111 1111 1111 1111 1111 ; 32 bit
1111 1111 1111 1111 1111 1111 1111 1110 ; 33 bit
1111 1111 1111 1111 1111 1111 1111 1100 ; 34 bit
1111 1111 1111 1111 1111 1111 1111 1000 ; 35 bit
...
1110 0000 0000 0000 0000 0000 0000 0000 ; 61 bit
1100 0000 0000 0000 0000 0000 0000 0000 ; 62 bit
1000 0000 0000 0000 0000 0000 0000 0000 ; 63 bit
Then Walter's magic xor and further folding produces the same indicies for
LSB's. Only the values inside the table should be reduced by one mod 64.
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.