Author: Dan Newman
Date: 00:27:16 04/19/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.
>
>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?
>
>Thanks in advance for any reply
>Flemming
The following is what I use in my program to find bit indices
(it works only with MSVC).
#pragma warning( push)
#pragma warning( disable: 4035)
inline int bsf( unsigned long bitpat)
{
__asm mov eax, bitpat
__asm bsf eax, eax
}
inline int bsr( unsigned long bitpat)
{
__asm mov eax, bitpat
__asm bsr eax, eax
}
#pragma warning( pop)
The functions bsf() and bsr() provide access to the BSF (bit scan
forward) and BSR (bit scan reverse) operations. The pragmas
are just there to get rid of the compiler's complaint that the
functions don't have any return statements... IIRC, BSF starts
at the low order bit and works towards the high order and BSR
starts at the high order bit. Both return the index of the first
1-bit encountered.
My function for extracting this index from a 64-bit bitboard is
a member function of my bitboard class which stores the board in
two 32-bit integers (members "lower" and "upper"):
class bitboard_t {
private:
unsigned long lower;
unsigned long upper;
public:
...
int next_one() {
if( lower ) {
int index = bsf( lower);
lower ^= (1ul << index);
return index;
} else { // Not testing upper since we won't run this on empty...
int index = bsf( upper);
upper ^= (1ul << index);
return index + 32;
}
}
...
};
As you can see, I also clear the bit with this function...
-Dan.
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.