Author: Russell Reagan
Date: 10:30:43 07/02/03
Go up one level in this thread
On July 02, 2003 at 07:59:39, Steve Maughan wrote:
>I currently use the routines shown at the bottom to locate the the first set
>bit. Many times I'm also clearing the same bit using the "a &= (a-1)". So the
>natural question is - has anyone developed efficient BSF and Clear assembler
>routines? Since BSF is easier than BSR to implement in 64 bit I'm only looking
>for a BSF and Clear and not the equivalent BSR.
>
>Ideally, the routine should take a pointer to the bitboard (unsigned 64 bit int)
>and return the index of the first bit as well as clearing it.
There was a discussion of this some time ago that involved Gerd Isenburg, Walter
Faxon, and others (myself, Sune Fischer, ...). The CCC search engine is being
slow at the moment, so I can't find it :(
>int bsr(bitboard a)
>{ __asm
> {
> bsf edx, dword ptr a
> mov eax, 63
> jnz l1
> bsf edx, dword ptr a+4
> mov eax, 31
> jnz l1
> mov edx, -33
> l1: sub eax, edx
> }
>}
I guess we have different ideas about what bsr should return, because I have a
bsr type function that returns the most significant bit, and yours seems to
return (63 - least_significant_bit), which means that you could write your bsr
like this:
int bsr (bitboard b)
{
return 63 - bsf(b);
}
It might be faster :)
Here are my equivalent functions to yours. You can uncomment the mov line in
each if you need a version that will work on empty bitboards.
int HighBit (bitboard b) {
_asm {
//mov eax, -1
bsr eax, dword ptr [b]
sub eax, 32
bsr eax, dword ptr [b + 4]
add eax, 32
}
}
int LowBit (bitboard b) {
_asm {
//mov eax, -33
bsf eax, dword ptr [b + 4]
add eax, 32
bsf eax, dword ptr [b]
}
}
Here is a comparison of what they return.
bitboard mask (int i)
{
return (bitboard)1 << i;
}
void main ()
{
int i;
for (i = 0; i < 64; ++i)
{
bitboard b = mask(i);
printf("bsf = %2d, LowBit = %2d, bsr = %2d, HighBit = %2d\n",
bsf(b), LowBit(b), bsr(b), HighBit(b));
}
}
Output:
bsf = 0, LowBit = 0, bsr = 63, HighBit = 0
bsf = 1, LowBit = 1, bsr = 62, HighBit = 1
bsf = 2, LowBit = 2, bsr = 61, HighBit = 2
bsf = 3, LowBit = 3, bsr = 60, HighBit = 3
bsf = 4, LowBit = 4, bsr = 59, HighBit = 4
bsf = 5, LowBit = 5, bsr = 58, HighBit = 5
bsf = 6, LowBit = 6, bsr = 57, HighBit = 6
bsf = 7, LowBit = 7, bsr = 56, HighBit = 7
bsf = 8, LowBit = 8, bsr = 55, HighBit = 8
bsf = 9, LowBit = 9, bsr = 54, HighBit = 9
bsf = 10, LowBit = 10, bsr = 53, HighBit = 10
bsf = 11, LowBit = 11, bsr = 52, HighBit = 11
bsf = 12, LowBit = 12, bsr = 51, HighBit = 12
bsf = 13, LowBit = 13, bsr = 50, HighBit = 13
bsf = 14, LowBit = 14, bsr = 49, HighBit = 14
bsf = 15, LowBit = 15, bsr = 48, HighBit = 15
bsf = 16, LowBit = 16, bsr = 47, HighBit = 16
bsf = 17, LowBit = 17, bsr = 46, HighBit = 17
bsf = 18, LowBit = 18, bsr = 45, HighBit = 18
bsf = 19, LowBit = 19, bsr = 44, HighBit = 19
bsf = 20, LowBit = 20, bsr = 43, HighBit = 20
bsf = 21, LowBit = 21, bsr = 42, HighBit = 21
bsf = 22, LowBit = 22, bsr = 41, HighBit = 22
bsf = 23, LowBit = 23, bsr = 40, HighBit = 23
bsf = 24, LowBit = 24, bsr = 39, HighBit = 24
bsf = 25, LowBit = 25, bsr = 38, HighBit = 25
bsf = 26, LowBit = 26, bsr = 37, HighBit = 26
bsf = 27, LowBit = 27, bsr = 36, HighBit = 27
bsf = 28, LowBit = 28, bsr = 35, HighBit = 28
bsf = 29, LowBit = 29, bsr = 34, HighBit = 29
bsf = 30, LowBit = 30, bsr = 33, HighBit = 30
bsf = 31, LowBit = 31, bsr = 32, HighBit = 31
bsf = 32, LowBit = 32, bsr = 31, HighBit = 32
bsf = 33, LowBit = 33, bsr = 30, HighBit = 33
bsf = 34, LowBit = 34, bsr = 29, HighBit = 34
bsf = 35, LowBit = 35, bsr = 28, HighBit = 35
bsf = 36, LowBit = 36, bsr = 27, HighBit = 36
bsf = 37, LowBit = 37, bsr = 26, HighBit = 37
bsf = 38, LowBit = 38, bsr = 25, HighBit = 38
bsf = 39, LowBit = 39, bsr = 24, HighBit = 39
bsf = 40, LowBit = 40, bsr = 23, HighBit = 40
bsf = 41, LowBit = 41, bsr = 22, HighBit = 41
bsf = 42, LowBit = 42, bsr = 21, HighBit = 42
bsf = 43, LowBit = 43, bsr = 20, HighBit = 43
bsf = 44, LowBit = 44, bsr = 19, HighBit = 44
bsf = 45, LowBit = 45, bsr = 18, HighBit = 45
bsf = 46, LowBit = 46, bsr = 17, HighBit = 46
bsf = 47, LowBit = 47, bsr = 16, HighBit = 47
bsf = 48, LowBit = 48, bsr = 15, HighBit = 48
bsf = 49, LowBit = 49, bsr = 14, HighBit = 49
bsf = 50, LowBit = 50, bsr = 13, HighBit = 50
bsf = 51, LowBit = 51, bsr = 12, HighBit = 51
bsf = 52, LowBit = 52, bsr = 11, HighBit = 52
bsf = 53, LowBit = 53, bsr = 10, HighBit = 53
bsf = 54, LowBit = 54, bsr = 9, HighBit = 54
bsf = 55, LowBit = 55, bsr = 8, HighBit = 55
bsf = 56, LowBit = 56, bsr = 7, HighBit = 56
bsf = 57, LowBit = 57, bsr = 6, HighBit = 57
bsf = 58, LowBit = 58, bsr = 5, HighBit = 58
bsf = 59, LowBit = 59, bsr = 4, HighBit = 59
bsf = 60, LowBit = 60, bsr = 3, HighBit = 60
bsf = 61, LowBit = 61, bsr = 2, HighBit = 61
bsf = 62, LowBit = 62, bsr = 1, HighBit = 62
bsf = 63, LowBit = 63, bsr = 0, HighBit = 63
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.