Author: Dan Newman
Date: 11:32:33 04/19/00
Go up one level in this thread
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...
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;
}
...
};
-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));
>>
>>
>>Is there anything faster, ie. such lookuptables or machine code intrutions?
>>
>>What about problem 1?
>Assembly instruction bsf
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.