Author: Heiner Marxen
Date: 12:01:10 04/19/00
Go up one level in this thread
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 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.
>-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.01 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.