Author: Dan Newman
Date: 13:24:18 04/19/00
Go up one level in this thread
On April 19, 2000 at 15:01:10, Heiner Marxen wrote:
>On April 19, 2000 at 14:32:33, Dan Newman wrote:
>
>>On April 18, 2000 at 23:39:31, Dann Corbit wrote:
>>
>>>On April 18, 2000 at 22:44:25, Flemming Rodler wrote:
>>>
>>>>Hi,
>>>>
>>>>I am trying to implement a bitboard based chess program on a Pentium or AMD
>>>>computer. I need to be able to find the following information fast:
>>>>
>>>>1) The position of the first and/or last bit in a sequence of 64 bits.
>>>>2) Count the number of bits that are 1 in a sequence of 64 bits.
>>>
>>>#2:
>>>
>>>static char nbits[256] =
>>>{
>>> 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
>>> 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
>>> 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
>>> 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
>>> 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
>>> 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
>>> 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
>>> 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
>>> 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
>>> 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
>>> 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
>>> 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
>>> 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
>>> 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
>>> 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
>>> 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
>>>};
>>>
>>>int CountBits(BitBoard d)
>>>{
>>> unsigned long *n = (unsigned long *) &d;
>>> return
>>> nbits[(unsigned char) n[0]] +
>>> nbits[(unsigned char) (n[0] >> 8)] +
>>> nbits[(unsigned char) (n[0] >> 16)] +
>>> nbits[(unsigned char) (n[0] >> 24)] +
>>> nbits[(unsigned char) n[1]] +
>>> nbits[(unsigned char) (n[1] >> 8)] +
>>> nbits[(unsigned char) (n[1] >> 16)] +
>>> nbits[(unsigned char) (n[1] >> 24)];
>>>}
>>>
>>
>>
>>Interesting. I hadn't thought about using a cast to clip off the higher
>>order bits--I use a mask (& 0xff). I wonder which is faster, or if there
>>is any difference... Also, assuming unsigned long is 32 bits, you don't
>>need the last cast since there are no higher bits to be clipped--not much
>>of an optimization of course...
>
>Since the table has size 256, the mask is correct. That an unsigned char
>contains no more than 8 bits is not guaranteed. The cast is a portability
>problem.
>
I wonder if there are any such machines still around (that don't have
8 bits to a char). I don't remember what the Cray does for bytes, but I
do still remember the DEC-10 with its 36-bit words. On that machine the
FORTRAN compiler stuffed 5 chars to a word with an extra bit left over for
various "clever" tricks--and what a pain it was to convert a bunch of
codes to work on a VAX. (The SOS text editor used that extra bit to
indicate line numbers...)
>>I also use a loop style bit counter for bitboards that I know are going
>>to be very sparse:
>>
>>class bitboard_t {
>> private:
>> unsigned long lower;
>> unsigned long upper;
>> public:
>> ...
>> int sparse_count() const {
>> int count = 0;
>> long b = lower;
>> while( b ) {
>> b &= ~(-b);
>> count++;
>> }
>> b = upper;
>> while( b ) {
>> b &= ~(-b);
>> count++;
>> }
>> return count;
>> }
>> ...
>>};
>
>Note please, that the above is not completely portable: on a 1-complement
>machine it would break, since -b == ~b. Better to stick to unsigned types
>when manipulating bits:
> unsigned long b = lower;
> while( b ) {
> b &= b - 1;
> count++;
> }
>
>AFAIK, that is as portable as it can be.
>
Thanks, that does look better :). Before I used the signed int trick I
had something like this: b &= ~(~b+1) and was just trying to save an op.
Are there any ones-complement machines around?
-Dan.
>>-Dan.
>>
>>
>>>For different machines/compilers, various methods may work better than others.
>>>Here is a list of bit counting techniques:
>>>ftp://38.168.214.175/pub/bitcount/BITC.ZIP
>>>
>>>>I know there is a method that works linear in the number of on-bits for
>>>>problem 2:
>>>>
>>>> for(count = 0; bitboard; count++, bitboard &= (bitboard -1));
>
>Sic!
>[snip]
>
>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.