Author: Gerd Isenberg
Date: 07:31:03 02/28/06
Go up one level in this thread
On February 28, 2006 at 02:57:37, Reinhard Scharnagl wrote:
>On February 27, 2006 at 15:56:14, Steffan Westcott wrote:
>
>>On February 27, 2006 at 13:36:52, Gerd Isenberg wrote:
>>
>>>Hi,
>>>
>>>while i indulge my current morbus knuth attack, which hits me so one, two times
>>>a year, i like to ask a question related to the "rotated" De Bruijn generator.
>>>
>>>I have a word "d" with a setwise interpretation ( a bitboard) and maximum
>>>cardinality of N (N bits set, let say 8). I like to enumerate all subsets,
>>>including the empty set and the original complete set. Looking for a smarter
>>>algorithm.
>>>
>>
>>Perhaps I missed something, but isn't this just a case of incrementing a number
>>and rippling a carry through the unwanted bits? Here is my answer, anyhow:
>>
>>void enumsets(const BitBoard d)
>>{
>> BitBoard n = 0;
>> do {
>> do_something_with_set(n);
>> n = (n-d) & d;
>> } while (n);
>>}
>>
>>
>>Cheers,
>>Steffan
>
>When I had been working with a 0x88 structure I used to iterate by:
>
>coor = ((coor | ~0x77) + 1) & 0x77;
>
>thus handling the coordinate bit combinations of 0x77;
>
>But your method above is indeed simpler and faster.
>
>Reinhard.
Hi Reinhard,
yes, your approach is indeed also a nice trick to ripple the carry through
unwanted bits:
1.) or with the complement of the original set to set all unwanted bits, so
that a possible overflow walks trough
2.) increment and ripple the carry through unwanted bits
3.) reset all unwanted bits by anding with the original set (d)
Shame that i did not found it by myself ;-(
n = ((n & ~d) + 1) & d;
Due to the definition of the Two's complement == One's complement plus one,
it becomes:
n = ((n & (-d-1)) + 1) & d;
Now it looks like the first "and" may be simply replaced by add
to get Steffan's expression ;-)
n = (n-d) & d;
Nice algebra!
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.