Author: Dann Corbit
Date: 20:39:31 04/18/00
Go up one level in this thread
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)];
}
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.